NO.91十六届蓝桥杯备战|图论根本-图的存储和遍历|毗邻矩阵|vector|链式前向星(C++)
图的基本概念图的界说
图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中边的条数。
图是较线性表和树更为复杂的数据结构。
[*]线性表中，除第⼀个和最后⼀个元素外，每个元素只有⼀个唯⼀的前驱和唯⼀的后继结点，元素和元素之间是⼀对⼀的关系；
[*]在树形结构中，数据元素之间有着显着的层次关系，每个元素有唯⼀的双亲，但可能有多个孩⼦，元素和元素之间是⼀对多的关系；
[*]⽽图形结构中，元素和元素之间的关系更加复杂，结点和结点之间的关系是任意的，任意两个结点之间都可能相干，图中元素和元素之间是多对多的关系
https://i-blog.csdnimg.cn/direct/9de5377be3c94518856a537d0072339c.png
有向图和⽆向图
图根据边的类型，可以分为⽆向图和有向图
https://i-blog.csdnimg.cn/direct/e378942babaf40709ffee7c92312da68.png
在图相干的算法中，我们可以将⽆向图中的边看成两条⽅向相反的有向边，从⽽将⽆向图转化为有向图
https://i-blog.csdnimg.cn/direct/af286ca3d0c841c1bc920ea91a26080f.png
简单图与多重图
⾃环：⾃⼰指向⾃⼰的⼀条边
https://i-blog.csdnimg.cn/direct/308659a9db9347c2b66d6f4b63f19c5d.png
重边：图中存在两个或两个以上完全雷同的边
https://i-blog.csdnimg.cn/direct/b8afcd550cf64bdfbdc120b5a7fed69e.png
简单图：若图中没有重边和⾃环，为简单图。
多重图：若图中存在重边或⾃环，为多重图。
https://i-blog.csdnimg.cn/direct/1b07faafb3f3409dbb1cefce3f6d63e3.png
稠密图和希罕图
有很少条边(如e < nlog2 n )的图称为希罕图，反之称为稠密图
https://i-blog.csdnimg.cn/direct/9cb34f8f6969488eac5b753e1092b0a9.png
顶点的度
顶点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)
https://i-blog.csdnimg.cn/direct/9eaaf94fc0f84dfe83ac624ec119e28f.png
路径
在图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的路径。
注意：两个顶点间的路径可能不唯⼀
https://i-blog.csdnimg.cn/direct/c7f20d62cb0842d8a51c129446e08193.png
简单路径与回路
若路径上各顶点 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雷同，则称这样的路径为回路或环
https://i-blog.csdnimg.cn/direct/6b0962006aed4c2e908ffc43c666f7b1.png
路径⻓度和带权路径⻓度
某些图的边具有与它相干的数值，称其为该边的权值。这些权值可以表⽰两个顶点间的距离、泯灭的代价、所需的时间等。⼀般将该种带权图称为⽹络
https://i-blog.csdnimg.cn/direct/7bce4a2595484cfc86f204bddaeefdac.png
对于不带权的图，⼀条路径的路径⻓度是指该路径上的边的条数。
对于带权的图，⼀条路径的路径⻓度是指该路径上各个边权值的总和。
https://i-blog.csdnimg.cn/direct/760b0a55b0894fd49f7c0a842ccf5eac.png
⼦图
设图 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的⽣成⼦图。
相当于就是在原来图的根本上，拿出来⼀些顶点和边，组成⼀个新的图。但是要注意，拿出来的点和边要能构成⼀个图才⾏
https://i-blog.csdnimg.cn/direct/a0e225dd0ac249439c9870f556e68b66.png
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，那么此图⼀定是⾮连通图。
[*]极⼤联通⼦图：⽆向图中，拿出⼀个⼦图，这个⼦图包含尽可能多的点和边。
[*]连通分量：⽆向图中的极⼤连通⼦图称为连通分量
https://i-blog.csdnimg.cn/direct/121f99cbb7f64160a094563a7398d522.png
⽣成树
连通图的⽣成树是包含图中全部顶点的⼀个极⼩连通⼦图。若图中顶点数为n，则它的⽣成树含有n-1条边。对⽣成树⽽⾔，若砍去⼀条边，则会酿成⾮连通图，若加上⼀条边则会形成⼀个回路
https://i-blog.csdnimg.cn/direct/aeec37dd1e97426c80268a1080070e00.png
图的存储和遍历
图的存储有两种：毗邻矩阵和毗邻表：
[*]其中，毗邻表的存储⽅式与树的孩⼦表⽰法完全⼀样。因此，⽤vector数组以及链式前向星就能实现。
[*]⽽毗邻矩阵就是⽤⼀个⼆维数组，其中edges存储顶点 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 之间有边相连
https://i-blog.csdnimg.cn/direct/de7fc6638d7049759f48ec3bddca9a54.png
矩阵中元素个数为nxn，即空间复杂度为O(n^2) ，n为顶点个数，和实际边的条数⽆关，适合存储稠密图
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int edges;
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 = c;
// 如果是⽆向边，需要反过来再存⼀下
edges = c;
}
return 0;
}
vector数组
和树的存储⼀模⼀样，只不外如果存在边权的话，我们的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;
int main()
{
cin >> n >> m; // 读⼊结点个数以及边的个数
for(int i = 1; i <= m; i++)
{
int a, b, c; cin >> a >> b >> c;
// a 和 b 之间有⼀条边，权值为 c
edges.push_back({b, c});
// 如果是⽆向边，需要反过来再存⼀下
edges.push_back({a, c});
}
return 0;
}
链式前向星
和树的存储⼀模⼀样，只不外如果存在边权的话，我们多创建⼀维数组，⽤来存储边的权值即可
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
// 链式前向星
int h, e, ne, w, id;
int n, m;
// 其实就是把 b 头插到 a 所在的链表后⾯
void add(int a, int b, int c)
{
id++;
e = b;
w = c; // 多存⼀个权值信息
ne = h;
h = 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;
}
DFS
和树的遍历⽅式⼀模⼀样，⼀条路⾛到⿊
[*]⽤毗邻矩阵的⽅式存储
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010;
int n, m;
int edges;
bool st; // 标记哪些点已经访问过
void dfs(int u)
{
cout << u << endl;
st = true;
// 遍历所有孩⼦
for(int v = 1; v <= n; v++)
{
// 如果存在 u->v 的边，并且没有遍历过
if(edges != -1 && !st)
{
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 = c;
// 如果是⽆向边，需要反过来再存⼀下
edges = c;
}
return 0;
}
[*]⽤vector数组的⽅式存储
#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;
bool st; // 标记哪些点已经访问过
void dfs(int u)
{
cout << u << endl;
st = true;
// 遍历所有孩⼦
for(auto& t : edges)
{
// u->v 的⼀条边，权值为 w
int v = t.first, w = t.second;
if(!st)
{
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.push_back({b, c});
// 如果是⽆向边，需要反过来再存⼀下
edges.push_back({a, c});
}
return 0;
}
[*]⽤链式前向星的⽅式存储
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
// 链式前向星
int h, e, ne, w, id;
int n, m;
// 其实就是把 b 头插到 a 所在的链表后⾯
void add(int a, int b, int c)
{
id++;
e = b;
w = c; // 多存⼀个权值信息
ne = h;
h = id;
}
bool st;
void dfs(int u)
{
cout << u << endl;
st = true;
// 遍历所有的孩⼦
for(int i = h; i; i = ne)
{
// u->v 的⼀条边
int v = e;
if(!st)
{
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;
}
BFS
[*]⽤毗邻矩阵的⽅式存储
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010;
int n, m;
int edges;
bool st; // 标记哪些点已经访问过
void bfs(int u)
{
queue<int> q;
q.push(u);
st = true;
while(q.size())
{
auto a = q.front(); q.pop();
cout << a << endl;
for(int b = 1; b <= n; b++)
{
if(edges != -1 && !st)
{
q.push(b);
st = 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 = c;
// 如果是⽆向边，需要反过来再存⼀下
edges = c;
}
return 0;
}
[*]⽤vector数组的⽅式存储
#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;
bool st; // 标记哪些点已经访问过
void bfs(int u)
{
queue<int> q;
q.push(u);
st = true;
while(q.size())
{
auto a = q.front(); q.pop();
cout << a << endl;
for(auto& t : edges)
{
int b = t.first, c = t.second;
if(!st)
{
q.push(b);
st = 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.push_back({b, c});
// 如果是⽆向边，需要反过来再存⼀下
edges.push_back({a, c});
}
return 0;
}
[*]⽤链式前向星的⽅式存储
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
// 链式前向星
int h, e, ne, w, id;
int n, m;
// 其实就是把 b 头插到 a 所在的链表后⾯
void add(int a, int b, int c)
{
id++;
e = b;
w = c; // 多存⼀个权值信息
ne = h;
h = id;
}
bool st;
void bfs(int u)
{
queue<int> q;
q.push(u);
st = true;
while(q.size()
{
auto a = q.front(); q.pop();
cout << a << endl;
for(int i = h; i; i = ne)
{
int b = e, c = w;
if(!st)
{
q.push(b);
st = 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;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]