Schwertlilien
As a recoder: notes and ideas.

2023.3.27

2023.3.27–图のreview

今天早上修复了blog:

原先出现的问题是:在上传文件后对文件进行了修改,可能导致CSS渲染文件或者js文件出错。然后hexo寄了。

修复的方法是:Hexo的安装及重置恢复_怪异收集者的博客-CSDN博客。所以change一个主题,然后就好啦!但是需要自己 改一下config.yml(也可以把之前的copy一下放到新的主题文件夹内),但是我干脆就换了一个了。

看看现在的:

图的概念

简单图:无自环,无重边。

子图:边的子集,以及相关联的点集。

度(Degree)

在无向图中,顶点的度是其邻接点的数目。

在有向图中。**(入度)指向这个顶点的弧的数目(出度)此顶点指向其他顶点的弧的数目**。该顶点的度=出度+入度。

邻接与路径

在无向图中,存在一条边(u,v):则称u和v邻接。

在有向图中,存在一条边<u,v>:则v是u的邻接点。

路径:图上一个顶点序列,其中序列上任意相邻两点都邻接。

简单路径:顶点和边==不重复出现==。

:除了顶点和终点相同外没有重复顶点的路径。

连通和连通分量

**连通(connected)**:如果无向图中任意两点都有路径,则图是连通的;否则是非连通的。

非连通图有多个连通分量。==连通与非连通是无向图上的概念,有向图是强连通和弱连通。==

强连通图:有向图中任意两点都有相互可达的路径。

相互可达的子图属于同一个强连通分量(scc)。

树(连通无向无环图)

==树可以 以任意点作为根==。

下面是一些定理:

  • G上有V个点,有V-1条边,还是一个无环图,那么它一定是连通的。

    反过来也成立:G上有V个点,有V-1条边,还是连通的,那么它一定是无环图。

  • G连通,但认一删除一条边后不连通。

    G无环,但任意添加一条边后包含环。

  • 任意两点只有唯一的简单路径。

    简单路径:顶点和边==不重复出现==。

稀疏图与稠密图

如何划分稀疏图与稠密图?假设考虑有向图:G=<V,E>那么$E=V^2$数量级是稠密图。

  • 稀疏图:边数E和$\frac {V(V-1)}{2}$相比非常少(V,E同数量级)
  • 时间复杂度为$O(ElogE)$和$O(V^2)$的算法:对稀疏图来说前者好,对稠密图来说后者好。

欧拉路径与欧拉回路

欧拉路径:只通过每条边一次的路径。

欧拉回路:如果这条路径的起点和终点是同一点。

一笔画问题。

  • 对无向图:图G有一条欧拉路径,当且仅当G是连通的,且有0 or 2 个奇度数节点。当所有节点都是偶度数时欧拉回路七点可以是任意点。
  • 对有向图:存在欧拉路径的条件:图连通,所有点出度=入度,or 有一个终点的入度-出度=1,一个起点的出度-入度=1。当所有点出度=入度是任意点可作为起点,而后者必须以出度-入度=1的点作为起点,入度-出度=1的点作为终点。

图的存储

边列表

基本上题目给出的就是这种形式,但是这种形式并不是很好处理。

邻接矩阵

1
int G[2005][2005];//G[u][v]:u->v的边

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//====================[vector实现]==================================//
//由于起点知道,所以只存储终点。
struct Edge{//1->2->5:1与2,1与5之间存在边。
int end;
int weight;
Edge(int v,int w):end(v),weight(w){}//构造函数
};

vector<Edge> adj[N+5];//N:点的个数

//Input
for(int i=1;i<=M;i++){
int u,v,w;
cin>>u>>v>>w;
adj[u].push_back(Edge(v,w));
adj[v].push_back(Edge(u,w));//如果是无向图需要双向建边。
}

//====================[链表实现--链式前向星]===========================//
const int maxN=5e5+5;

struct Edge{
int to;
int weight;
Edge* next;
};

Edge pool[maxN*2];
int heads[maxN];
int nn;

void addEdge(int from,int to,int weight){
pool[++nn].to=to;
pool[nn].weight=weight;
pool[nn].next=heads[from];
heads[from]=nn;
}

前向星

以储存边的方式来存储图。构造方法如下:读入每条边的信息,将边存放在数组中,把数组中的边按照起点顺序排序(可以使用基数排序,如下面例程),前向星就构造完了。通常用在点的数目太多,或两点之间有多条弧的时候。

一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外,前向星几乎是完美的。

把边集数组终得每一条边按照起点大小排序,如果起点相同就按照终点从小到大排序。并记录下以i为起点的起始位置和以i为起点的边数(i的出度)。

  • head[i]:记录以i为边集在数组终得第一个存储位置。

  • len[i]:记录所有以i为起点的边在数组终得存储长度。

链式前向星–静态邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Edge{
int next; //与第i条边同起点的下一条边的存储位置
int to; //第i条边的终点
int w; //边权
};

void addEdge(int u,int v,int w){
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];//以u为起点的最后一条边的编号
head[u]=cnt++; //更新以u为起点的上一条边的编号=head[u]=cnt;cnt++;
}//实际上是模拟的邻接表的将新节点从head插入:next=head[u];
//head[]:表示以i为起点的第一条边存储的位置

P5318

小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个(也有可能没有)参考文献的链接指向别的博客文章。小K 求知欲旺盛,如果他看了某篇文章,那么他一定会去看这篇文章的参考文献(如果他之前已经看过这篇参考文献的话就不用再看它了)。

假设洛谷博客里面一共有 $n(n\le10^5)$ 篇文章(编号为 1 到 $n$)以及 $m(m\le10^6)$ 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章,请帮助小 K 设计一种方法,使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图,其中,文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。

请对这个图分别进行 DFS 和 BFS,并输出遍历结果。如果有很多篇文章可以参阅,请先看编号较小的那篇(因此你可能需要先排序)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# include<bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 5;
const int maxM = 1e6 + 5;
int n, m, cnt;
vector<int> adj[maxN];
bool vis_dfs[maxN] = {0};

bool vis_bfs[maxN] = {0};

void dfs(int x) {
vis_dfs[x] = true;
cout << x << " ";

for (int i = 0; i < adj[x].size(); i++) {
int node = adj[x][i];
if (!vis_dfs[node])
dfs(node);
}

}

void bfs(int x) {//广搜需要借助队列
queue<int>q;
q.push(x);
cout << endl << x << " ";
vis_bfs[x] = true;

while (!q.empty()) {
int node = q.front();
for (int i = 0; i < adj[node].size(); i++) {
int end_node = adj[node][i];
if (!vis_bfs[end_node]) {
vis_bfs[end_node] = true;
q.push(end_node);
cout << end_node << " ";
}
}
q.pop();
}
}


int main() {
int u, v;

cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> u >> v;
adj[u].push_back(v);
}

for (int i = 1; i <= n; i++) {
sort(adj[i].begin(), adj[i].end());
}

dfs(1);//我对这个地方有点疑问:1号点一定会有edge吗?
bfs(1);
return 0;
}

P3916

给出 $N$ 个点,$M$ 条边的有向图,对于每个点 $v$,求 $A(v)$ 表示从点 $v$ 出发,能到达的编号最大的点。

好吧,看这个题并不是很难,所以速速的就完了。但是T了一个点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# include<bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 5;
int n, m, cnt;
vector<int> adj[maxN];
bool vis_dfs[maxN] = {0};

void dfs(int x) {
vis_dfs[x] = true;
if (x > cnt)
cnt = x;
for (int i = 0; i < adj[x].size(); i++) {
int node = adj[x][i];
if (!vis_dfs[node])
dfs(node);
}
}

int main() {
int u, v;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> u >> v;
adj[u].push_back(v);
}

for (int i = 1; i <= n; i++) {
cnt = 0;
memset(vis_dfs, 0, sizeof(vis_dfs));
dfs(i);
cout << cnt << " ";
}
}

看了看题解,主要的思路是反向建边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# include<bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 5;
int n, m, cnt;
vector<int> adj[maxN];
int vis[maxN] = {0};

void dfs(int x, int d) {
if (vis[x]) //--|
return; // |--主要就是这里:由于是从最大开始遍历,那么直接赋值就是max,那么可以直接返回。
vis[x] = d; //--|
for (int i = 0; i < adj[x].size(); i++) {
int node = adj[x][i];
if (!vis[node])
dfs(node, d);
}
}

int main() {
int u, v;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> u >> v;
adj[v].push_back(u);//反向建边--主要是配合上面的步骤
}

for (int i = n; i ; i--) {
dfs(i, i);
}

for (int i = 1; i <= n; i++)
cout << vis[i] << " ";
}

P1807

设 $G$ 为有 $n$ 个顶点的带权有向无环图,$G$ 中各顶点的编号为 $1$ 到 $n$,请设计算法,计算图 $G$ 中 $1, n$ 间的最长路径。

乐,没写完,明天再说。

搜索
匹配结果数:
未搜索到匹配的文章。