C++如何处理图的存储方式
博主介绍
邻接矩阵
邻接表
链式前向星
1、AcWing方式（纯数组）
Acwing图的存储方式
案例
复杂度
应用
邻接表
代码实现
数据定义
插入边
遍历
深度优先遍历
广度优先遍历
复杂度
应用
实现案例
2、 结构体+数组
3、 结构体+数组(2)
💫点击直接资料领取💫
博主介绍
🌊 作者主页：苏州程序大白
🌊 作者简介：🏆CSDN人工智能域优质创作者🥇，苏州市凯捷智能科技有限公司创立人，目前合作公司富士康、歌尔等几家公司
💬如果文章对你有帮助，欢迎关注、点赞、收藏（一键三连）和C#、Halcon、python+opencv、VUE、各大公司面试等一些订阅专栏哦
💅 有任何问题欢迎私信，看到会及时回复
邻接矩阵
适用：
稠密图，就是说点数的平方与边数接近的情况，换句话说就是边特别多。
不适用：
稀疏图，就是点数的平方与边数差的特别多，边数少，但点数多，就不行了，因为空间占用太大了。
实现代码
#include <bits/stdc++.h> using namespace std; const int N = 1010; //图的最大点数量 int n; int v[N][N]; //邻接矩阵 /** * 测试数据 4 0 5 2 3 5 0 0 1 2 0 0 4 3 1 4 0 */ int main() { cin >> n; //读入到邻接矩阵 for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> v[i][j]; //下面的代码将找到与点i有直接连接的每一个点以及那条边的长度 for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (v[i][j]) cout << "edge from point " << i << " to point " << j << " with length " << v[i][j] << endl; return 0; }
邻接表
#include <bits/stdc++.h> using namespace std; const int N = 1010; //图的最大点数量 struct Edge { //记录边的终点，边权的结构体 int to; //终点 int value; //边权 }; int n, m; //表示图中有n个点，m条边 vector<Edge> p[N]; //使用vector的邻接表 /** * 测试数据 4 6 2 1 1 1 3 2 4 1 4 2 4 6 4 2 3 3 4 5 */ int main() { cin >> n >> m; //m条边 for (int i = 1; i <= m; i++) { int u, v, l; //点u到点v有一条权值为l的边 cin >> u >> v >> l; p[u].push_back({v, l}); } //输出 for (int i = 1; i <= n; i++) { printf("出发点：%d ", i); for (int j = 0; j < p[i].size(); j++) printf(" 目标点：%d,权值：%d;", p[i][j].to, p[i][j].value); puts(""); } return 0; }
链式前向星
链式前向星是邻接表存图的第二种方法，它自己还有两种写法，比 用向量存图的那种邻接表要快 。
它是一种以边为主的存图方式，idxidx表示最后一条边的预存入的房间号,$head[i$]表示以$i$为起点第一条边的房间号。
每条边有三个属性：
从$head[i]$出发到哪个结点的边？
这条边的边权是多少？
这条边的下一条边是谁？（下一条边的房间号）
链式前向星有三种变形，需要同学们都掌握，找一种自己最喜欢的背下来，其它两种要求能看懂，因为其它人写题解，可能使用了其它方式。
1、AcWing方式（纯数组）
#include <bits/stdc++.h> using namespace std; const int N = 1010; //点数最大值 int n, m; //n个点，m条边 //idx是新结点加入的数据内索引号 //h[N]表示有N条单链表的头,e[M]代表每个节点的值,ne[M]代表每个节点的下一个节点号 int h[N], e[N << 1], ne[N << 1], w[N << 1], idx; //链式前向星 void add(int a, int b, int l) { e[idx] = b, ne[idx] = h[a], w[idx] = l, h[a] = idx++; } /** * 测试数据 4 6 2 1 1 1 3 2 4 1 4 2 4 6 4 2 3 3 4 5 */ int main() { cin >> n >> m; //初始化为-1,每个头节点写成-1 memset(h, -1, sizeof h); //m条边 for (int i = 1; i <= m; i++) { int u, v, l; //点u到点v有一条权值为l的边 cin >> u >> v >> l; //加入到链式前向星 add(u, v, l); } //遍历每个结点 for (int i = 1; i <= n; i++) { printf("出发点：%d ", i); for (int j = h[i]; j != -1; j = ne[j]) printf(" 目标点：%d,权值：%d;", e[j], w[j]); puts(""); } return 0; }
Acwing图的存储方式
方法：使用一个二维数组 g 来存边，其中 g[u][v] 为 1 表示存在 到的边，为 0 表示不存在。如果是带边权的图，可以在 g[u][v] 中存储到的边的边权。
案例
最短距离Dijkstra
从s到t的最短距离算法流程：
b[]表示当前已经确定最短距离的点。 dis[s] = 0, dis[其他] = +∞ for (int i = 1; i <= n; i ++) t：不在b中的最短距离的点 将t加入b[] 使用t更新其他未被确定的点的距离
代码实现
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 510; int n, m; int w[N][N]; int dis[N]; bool b[N]; int dijkstra() { memset(dis, 0x3f, sizeof dis); dis[1] = 0; for (int i = 0; i < n; i ++) { int k = -1; for (int j = 1; j <= n; j ++) if (!b[j] && (k == -1 || dis[k] > dis[j])) k = j; b[k] = true; for (int j = 1; j <= n; j ++) { dis[j] = min(dis[j], dis[k] + w[k][j]); } } if (dis[n] == 0x3f3f3f3f) return -1; else return dis[n]; } int main() { scanf("%d %d", &n, &m); memset(w, 0x3f, sizeof w); while (m --) { int i, j, k; scanf("%d %d %d", &i, &j, &k); w[i][j] = min(w[i][j], k); } int t = dijkstra(); printf("%d", t); return 0; }
复杂度
应用
邻接矩阵只适用于没有重边（或重边可以忽略）的情况。
其最显著的优点是可以查询一条边是否存在。
由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。
邻接表
使用一个支持动态增加元素的数据结构构成的数组，如 vector g[n + 1] 来存边，其中 g[u] 存储的是点的所有出边的相关信息（终点、边权等）。
代码实现
数据定义
int h[N], e[M], ne[M], idx; bool st[N];
插入边
插入一条a指向b的边
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }
遍历
深度优先遍历
void dfs(int u) { st[u] = true; // 标记已经被遍历过了 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) dfs(j); } }
广度优先遍历
void bfs() { int q[N]; // 定义队列 int hh = 0, tt = 0; // 头和尾指针 memset(st, 0, sizeof st); q[0] = 1; while (hh <= tt) { int t = q[hh ++]; st[t] = true; cout << t << ' '; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { q[++ tt] = j; } } } }
复杂度
应用
存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。
尤其适用于需要对一个点的所有出边进行排序的场合。
实现案例
#include <iostream> #include <cstring> using namespace std; const int N = 1e5 + 10, M = N * 2; // h是n个链表的链表头, e存的是每一个节点的值, ne存的是 next指针是多少。 int h[N], e[M], ne[M], idx; bool st[N]; int n; // n条边 // 插入一条a指向b的边 void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++; } // 深度优先遍历 void dfs(int u) { cout << u << ' '; st[u] = true; // 标记已经被遍历过了 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) dfs(j); } } // 广度优先遍历 void bfs() { int q[N]; // 定义队列 int hh = 0, tt = 0; // 头和尾指针 memset(st, 0, sizeof st); q[0] = 1; while (hh <= tt) { int t = q[hh ++]; st[t] = true; cout << t << ' '; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { q[++ tt] = j; } } } } int main () { memset(h, -1, sizeof h); cin >> n; for (int i = 1; i <= n; i ++) { int a, b; cin >> a >> b; add(a, b); add(b, a); } cout << "深度优先遍历："; dfs(1); cout << endl; cout << "广度优先遍历："; bfs(); return 0; }
2、 结构体+数组
#include <bits/stdc++.h> using namespace std; const int N = 1010; //点数最大值 int n, m, idx; //n个点，m条边,idx是新结点加入的数据内索引号 //链式前向星 struct Edge { int to; //到哪个结点 int value; //边权 int next; //同起点的下一条边的编号 } edge[N << 1]; //同起点的边的集合 N<<1就是2*N，一般的题目，边的数量通常是小于2*N的，这个看具体的题目要求 int head[N]; //以i为起点的边的集合入口处 //加入一条边，x起点，y终点，value边权 void add_edge(int x, int y, int value) { edge[++idx].to = y; //终点 edge[idx].value = value; //权值 edge[idx].next = head[x]; //以x为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号 head[x] = idx; //更新以x为起点上一条边的编号 } /** * 测试数据 4 6 2 1 1 1 3 2 4 1 4 2 4 6 4 2 3 3 4 5 */ int main() { cin >> n >> m; //m条边 for (int i = 1; i <= m; i++) { int u, v, l; //点u到点v有一条权值为l的边 cin >> u >> v >> l; //加入到链式前向星 add_edge(u, v, l); } //遍历每个结点 for (int i = 1; i <= n; i++) { printf("出发点：%d ", i); for (int j = head[i]; j; j = edge[j].next) //遍历每个结点的每一条边 printf(" 目标点：%d,权值：%d;", edge[j].to, edge[j].value); puts(""); } return 0; }
3、 结构体+数组(2)
为什么链式前向星有两种实现方法呢？这其实是看用不用的问题，如果它用了，那么就是在加边的最后需要++，如果不用，进来就++。
第二个变化就是如果用了，那么就不能用做默认值了，所以需要初始化memset(head,-1 ,sizeof head);
第三个变化就是遍历时的条件变了，成了j!=-1,而不用的就是j就行了，我个人还是喜欢用不带的那个，就是上面的。是因为网上好多网友喜欢这种方式，如果我们看其它人的题解时，可能看不懂，所以也要了解一下。
#include <bits/stdc++.h> using namespace std; const int N = 1010; //点数最大值 int n, m, idx; //n个点，m条边,idx是新结点加入的数据内索引号 //链式前向星 struct Edge { int to; //到哪个结点 int value; //边权 int next; //同起点的下一条边的编号 } edge[N << 1]; //同起点的边的集合 N<<1就是2*N，一般的题目，边的数量通常是小于2*N的，这个看具体的题目要求 int head[N]; //以i为起点的边的集合入口处 //加入一条边，x起点，y终点，value边权 void add_edge(int x, int y, int value) { edge[idx].to = y; //终点 edge[idx].value = value; //权值 edge[idx].next = head[x]; //以x为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号 head[x] = idx++; //更新以x为起点上一条边的编号 } /** * 测试数据 4 6 2 1 1 1 3 2 4 1 4 2 4 6 4 2 3 3 4 5 */ int main() { cin >> n >> m; //初始化head数组 memset(head, -1, sizeof head); //m条边 for (int i = 1; i <= m; i++) { int u, v, l; //点u到点v有一条权值为l的边 cin >> u >> v >> l; //加入到链式前向星 add_edge(u, v, l); } //遍历每个结点 for (int i = 1; i <= n; i++) { printf("出发点：%d ", i); for (int j = head[i]; j != -1; j = edge[j].next) //遍历每个结点的每一条边 printf(" 目标点：%d,权值：%d;", edge[j].to, edge[j].value); puts(""); } return 0; }
