图的基本概念
图的界说
图G是由顶点集V和边集E组成，记为G = (V, E)，其中V(G)表⽰图G中顶点的有限⾮空集；E(G)表⽰图G中顶点之间的关系（边）集合。若 V = { v 1 , v 2 , … , v n } V = \left\{ v_{1},v_{2},\dots,v_{n} \right\} V={v1,v2,…,vn}，则⽤ ∣ V ∣ |V| ∣V∣表
⽰图G中顶点的个数，也称图G的阶， E = ( u , v ) ∣ u ∈ V , v ∈ V E = {(u,v)|u \in V, v \in V} E=(u,v)∣u∈V,v∈V，⽤ ∣ E ∣ |E| ∣E∣表⽰图G中边的条数。
图是较线性表和树更为复杂的数据结构。
- 线性表中，除第⼀个和最后⼀个元素外，每个元素只有⼀个唯⼀的前驱和唯⼀的后继结点，元素和元素之间是⼀对⼀的关系；
- 在树形结构中，数据元素之间有着显着的层次关系，每个元素有唯⼀的双亲，但可能有多个孩⼦，元素和元素之间是⼀对多的关系；
- ⽽图形结构中，元素和元素之间的关系更加复杂，结点和结点之间的关系是任意的，任意两个结点之间都可能相干，图中元素和元素之间是多对多的关系
有向图和⽆向图
图根据边的类型，可以分为⽆向图和有向图
在图相干的算法中，我们可以将⽆向图中的边看成两条⽅向相反的有向边，从⽽将⽆向图转化为有向图
简单图与多重图
⾃环：⾃⼰指向⾃⼰的⼀条边
重边：图中存在两个或两个以上完全雷同的边
简单图：若图中没有重边和⾃环，为简单图。
多重图：若图中存在重边或⾃环，为多重图。
稠密图和希罕图
有很少条边(如e < nlog2 n )的图称为希罕图，反之称为稠密图
顶点的度
顶点v的度是指与它相干联的边的条数，记作deg(v)。由该顶点发出的边称为顶点的出度，到达该顶点的边称为顶点的⼊度。
- ⽆向图中，顶点的度即是该顶点的⼊度(indev)和出度(outdev)，即deg(v)=indeg(v)=outdeg(v)。
- 有向图中，顶点的度即是该顶点的⼊度与出度之和，其中顶点v的⼊度indeg(v)是以v为终点的有向边的条数，顶点v的出度outdeg(v)是以v为起始点的有向边的条数，deg(v)=indeg(v)+outdeg(v)
路径
在图G=(V，E)中，若从顶点 v i v_{i} vi出发，沿⼀些边颠末某些顶点 v p 1 , v p 2 , … , v p m v_{p1},v_{p2},\dots,v_{pm} vp1,vp2,…,vpm，到达顶点 v j v_{j} vj。则称顶点序列 ( v i , v p 1 , v p 2 , … , v p m , v j ) (v_{i},v_{p1},v_{p2},\dots,v_{pm},v_{j}) (vi,vp1,vp2,…,vpm,vj)为从顶点 v i v_{i} vi到顶点 v j v_{j} vj的路径。
注意：两个顶点间的路径可能不唯⼀
简单路径与回路
若路径上各顶点 v 1 , v 2 , … , v m v_{1},v_{2},\dots,v_{m} v1,v2,…,vm均不重复，则称这样的路径为简单路径。若路径上第⼀个顶点 v 1 v_{1} v1和最后⼀个顶点 v m v_{m} vm雷同，则称这样的路径为回路或环
路径⻓度和带权路径⻓度
某些图的边具有与它相干的数值，称其为该边的权值。这些权值可以表⽰两个顶点间的距离、泯灭的代价、所需的时间等。⼀般将该种带权图称为⽹络
对于不带权的图，⼀条路径的路径⻓度是指该路径上的边的条数。
对于带权的图，⼀条路径的路径⻓度是指该路径上各个边权值的总和。
⼦图
设图 G = { V , E } G = \left\{ V, E\right\} G={V,E}和图 G ′ = { V ′ , E ′ } G' = \left\{ V',E' \right\} G′={V′,E′}，若 V ′ ∈ V V'\in V V′∈V 且 E ′ ∈ E E'\in E E′∈E，则称 G ′ G' G′是 G G G的⼦图。如有 V ( G ′ ) = V ( G ) V(G')=V(G) V(G′)=V(G)的⼦图 G ′ G' G′，则称 G ′ G' G′为 G G G的⽣成⼦图。
相当于就是在原来图的根本上，拿出来⼀些顶点和边，组成⼀个新的图。但是要注意，拿出来的点和边要能构成⼀个图才⾏
G1_1和G1_2为⽆向图G1的⼦图，G1_1为G1的⽣成⼦图。
G2_1和G2_2为有向图G2的⼦图，G2_1为G2的⽣成⼦图。
连通图与连通分量
在⽆向图中，若从顶点 v 1 v_{1} v1到顶点 v 2 v_{2} v2有路径，则称顶点 v 1 v_{1} v1与顶点 v 2 v_{2} v2是连通的。如果图G中任意⼀对顶点都是连通的，则图G称为连通图，否则称为⾮连通图。
- 假设⼀个图有n个顶点，如果边数⼩于n-1，那么此图⼀定是⾮连通图。
- 极⼤联通⼦图：⽆向图中，拿出⼀个⼦图，这个⼦图包含尽可能多的点和边。
- 连通分量：⽆向图中的极⼤连通⼦图称为连通分量
⽣成树
连通图的⽣成树是包含图中全部顶点的⼀个极⼩连通⼦图。若图中顶点数为n，则它的⽣成树含有n-1条边。对⽣成树⽽⾔，若砍去⼀条边，则会酿成⾮连通图，若加上⼀条边则会形成⼀个回路
图的存储和遍历
图的存储有两种：毗邻矩阵和毗邻表：
- 其中，毗邻表的存储⽅式与树的孩⼦表⽰法完全⼀样。因此，⽤vector数组以及链式前向星就能实现。
- ⽽毗邻矩阵就是⽤⼀个⼆维数组，其中edges[j]存储顶点 i 与顶点 j 之间，边的信息。
图的遍历分两种：DFS和BFS，和树的遍历⽅式以及实现⽅式完全⼀样。因此，可以仿照树这个数据结构来学习
毗邻矩阵
毗邻矩阵，指⽤⼀个矩阵(即⼆维数组)存储图中边的信息(即各个顶点之间的毗邻关系)，存储顶点之间毗邻关系的矩阵称为毗邻矩阵。
对于带权图⽽⾔，若顶点 v i v_{i} vi和 v j v_{j} vj之间有边相连，则毗邻矩阵中对应项存放着该边对应的权值，若顶点 v i v_{i} vi和 v j v_{j} vj不相连，则⽤ ∞ \infty ∞来代表这两个顶点之间不存在边。
对于不带权的图，可以创建⼀个⼆维的bool类型的数组，来标记顶点vi 和vj 之间有边相连
矩阵中元素个数为nxn，即空间复杂度为O(n^2) ，n为顶点个数，和实际边的条数⽆关，适合存储稠密图
- #include <iostream>
- #include <cstring>
- using namespace std;
- const int N = 1010;
- int n, m;
- int edges[N][N];
- int main()
- {
- memset(edges, -1, sizeof edges);
- cin >> n >> m; // 读⼊结点个数以及边的个数
- for(int i = 1; i <= m; i++)
- {
- int a, b, c; cin >> a >> b >> c;
- // a - b 有⼀条边，权值为 c
- edges[a][b] = c;
- // 如果是⽆向边，需要反过来再存⼀下
- edges[b][a] = c;
- }
- return 0;
- }
和树的存储⼀模⼀样，只不外如果存在边权的话，我们的vector数组⾥⾯放⼀个结构体大概是pair即可。
- #include <iostream>
- #include <vector>
- using namespace std;
- typedef pair<int, int> PII;
- const int N = 1e5 + 10;
- int n, m;
- vector<PII> edges[N];
- int main()
- {
- cin >> n >> m; // 读⼊结点个数以及边的个数
- for(int i = 1; i <= m; i++)
- {
- int a, b, c; cin >> a >> b >> c;
- // a 和 b 之间有⼀条边，权值为 c
- edges[a].push_back({b, c});
- // 如果是⽆向边，需要反过来再存⼀下
- edges[b].push_back({a, c});
- }
- return 0;
- }
和树的存储⼀模⼀样，只不外如果存在边权的话，我们多创建⼀维数组，⽤来存储边的权值即可
- #include <iostream>
- using namespace std;
- const int N = 1e5 + 10;
- // 链式前向星
- int h[N], e[N * 2], ne[N * 2], w[N * 2], id;
- int n, m;
- // 其实就是把 b 头插到 a 所在的链表后⾯
- void add(int a, int b, int c)
- {
- id++;
- e[id] = b;
- w[id] = c; // 多存⼀个权值信息
- ne[id] = h[a];
- h[a] = id;
- }
- int main()
- {
- cin >> n >> m; // 读⼊结点个数以及边的个数
- for(int i = 1; i <= m; i++)
- {
- int a, b, c; cin >> a >> b >> c;
- // a 和 b 之间有⼀条边，权值为 c
- add(a, b, c); add(b, a, c);
- }
- return 0;
- }
和树的遍历⽅式⼀模⼀样，⼀条路⾛到⿊
- #include <iostream>
- #include <cstring>
- #include <queue>
- using namespace std;
- const int N = 1010;
- int n, m;
- int edges[N][N];
- bool st[N]; // 标记哪些点已经访问过
- void dfs(int u)
- {
- cout << u << endl;
- st[u] = true;
- // 遍历所有孩⼦
- for(int v = 1; v <= n; v++)
- {
- // 如果存在 u->v 的边，并且没有遍历过
- if(edges[u][v] != -1 && !st[v])
- {
- dfs(v);
- }
- }
- }
- int main()
- {
- memset(edges, -1, sizeof edges);
- cin >> n >> m; // 读⼊结点个数以及边的个数
- for(int i = 1; i <= m; i++)
- {
- int a, b, c; cin >> a >> b >> c;
- // a - b 有⼀条边，权值为 c
- edges[a][b] = c;
- // 如果是⽆向边，需要反过来再存⼀下
- edges[b][a] = c;
- }
- return 0;
- }
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- typedef pair<int, int> PII;
- const int N = 1e5 + 10;
- int n, m;
- vector<PII> edges[N];
- bool st[N]; // 标记哪些点已经访问过
- void dfs(int u)
- {
- cout << u << endl;
- st[u] = true;
- // 遍历所有孩⼦
- for(auto& t : edges[u])
- {
- // u->v 的⼀条边，权值为 w
- int v = t.first, w = t.second;
- if(!st[v])
- {
- dfs(v);
- }
- }
- }
- int main()
- {
- cin >> n >> m; // 读⼊结点个数以及边的个数
- for(int i = 1; i <= m; i++)
- {
- int a, b, c; cin >> a >> b >> c;
- // a 和 b 之间有⼀条边，权值为 c
- edges[a].push_back({b, c});
- // 如果是⽆向边，需要反过来再存⼀下
- edges[b].push_back({a, c});
- }
- return 0;
- }
- #include <iostream>
- #include <queue>
- using namespace std;
- const int N = 1e5 + 10;
- // 链式前向星
- int h[N], e[N * 2], ne[N * 2], w[N * 2], id;
- int n, m;
- // 其实就是把 b 头插到 a 所在的链表后⾯
- void add(int a, int b, int c)
- {
- id++;
- e[id] = b;
- w[id] = c; // 多存⼀个权值信息
- ne[id] = h[a];
- h[a] = id;
- }
- bool st[N];
- void dfs(int u)
- {
- cout << u << endl;
- st[u] = true;
- // 遍历所有的孩⼦
- for(int i = h[u]; i; i = ne[i])
- {
- // u->v 的⼀条边
- int v = e[i];
- if(!st[v])
- {
- dfs(v);
- }
- }
- }
- int main()
- {
- cin >> n >> m; // 读⼊结点个数以及边的个数
- for(int i = 1; i <= m; i++)
- {
- int a, b, c; cin >> a >> b >> c;
- // a 和 b 之间有⼀条边，权值为 c
- add(a, b, c); add(b, a, c);
- }
- return 0;
- }
- #include <iostream>
- #include <cstring>
- #include <queue>
- using namespace std;
- const int N = 1010;
- int n, m;
- int edges[N][N];
- bool st[N]; // 标记哪些点已经访问过
- void bfs(int u)
- {
- queue<int> q;
- q.push(u);
- st[u] = true;
- while(q.size())
- {
- auto a = q.front(); q.pop();
- cout << a << endl;
- for(int b = 1; b <= n; b++)
- {
- if(edges[a][b] != -1 && !st[b])
- {
- q.push(b);
- st[b] = true;
- }
- }
- }
- }
- int main()
- {
- memset(edges, -1, sizeof edges);
- cin >> n >> m; // 读⼊结点个数以及边的个数
- for(int i = 1; i <= m; i++)
- {
- int a, b, c; cin >> a >> b >> c;
- // a - b 有⼀条边，权值为 c
- edges[a][b] = c;
- // 如果是⽆向边，需要反过来再存⼀下
- edges[b][a] = c;
- }
- return 0;
- }
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- typedef pair<int, int> PII;
- const int N = 1e5 + 10;
- int n, m;
- vector<PII> edges[N];
- bool st[N]; // 标记哪些点已经访问过
- void bfs(int u)
- {
- queue<int> q;
- q.push(u);
- st[u] = true;
- while(q.size())
- {
- auto a = q.front(); q.pop();
- cout << a << endl;
- for(auto& t : edges[a])
- {
- int b = t.first, c = t.second;
- if(!st[b])
- {
- q.push(b);
- st[b] = true;
- }
- }
- }
- }
- int main()
- {
- cin >> n >> m; // 读⼊结点个数以及边的个数
- for(int i = 1; i <= m; i++)
- {
- int a, b, c; cin >> a >> b >> c;
- // a 和 b 之间有⼀条边，权值为 c
- edges[a].push_back({b, c});
- // 如果是⽆向边，需要反过来再存⼀下
- edges[b].push_back({a, c});
- }
- return 0;
- }
- #include <iostream>
- #include <queue>
- using namespace std;
- const int N = 1e5 + 10;
- // 链式前向星
- int h[N], e[N * 2], ne[N * 2], w[N * 2], id;
- int n, m;
- // 其实就是把 b 头插到 a 所在的链表后⾯
- void add(int a, int b, int c)
- {
- id++;
- e[id] = b;
- w[id] = c; // 多存⼀个权值信息
- ne[id] = h[a];
- h[a] = id;
- }
- bool st[N];
- void bfs(int u)
- {
- queue<int> q;
- q.push(u);
- st[u] = true;
- while(q.size()
- {
- auto a = q.front(); q.pop();
- cout << a << endl;
- for(int i = h[a]; i; i = ne[i])
- {
- int b = e[i], c = w[i];
- if(!st[b])
- {
- q.push(b);
- st[b] = true;
- }
- }
- }
- }
- int main()
- {
- cin >> n >> m; // 读⼊结点个数以及边的个数
- for(int i = 1; i <= m; i++)
- {
- int a, b, c; cin >> a >> b >> c;
- // a 和 b 之间有⼀条边，权值为 c
- add(a, b, c); add(b, a, c);
- }
- return 0;
- }
|
