C++实现图的存储和遍历

前言

        许多新手友友在初学算法和数据结构时，会被图论支配过。我这里整理了一下图论常见的存储和遍历方式，仅供参考。如有问题，欢迎大佬们批评指正。

        存储我将提到四种方式：邻接矩阵、vector实现邻接表、数组模拟单链表实现的前向星实现邻接表、结构体数组直接存储边。遍历我将提到三种方式：dfs、bfs、按照边的权重值大小遍历输出。

一、邻接矩阵

#include <iostream>
#include <cstring>
#include <queue>
#include <functional>
constexpr int MAX_N = 1e3+5;
int g[MAX_N][MAX_N];
bool vis[MAX_N];
int main(){//取消同步流，加快输入输出 std::cin.tie(nullptr)->sync_with_stdio(false);//图的存储方式 1：邻接矩阵int n;std::cin >> n;for(int i = 1;i<=n;++i){for(int j = 1;j<=n;++j){std::cin >> g[i][j];}}//邻接矩阵的 dfs遍历memset(vis,false,sizeof vis);vis[1] = true;using Dfs = std::function<void(int)>;//目的是为了让 dfs函数可以进行递归 Dfs dfs = [&](int u)->void{//lambda表达式（函数） std::cout << u << ' ';for(int i = 1;i<=n;++i){if(!vis[i]&&g[u][i]){vis[i]=true;dfs(i);}}};dfs(1);std::cout << '\n';//邻接矩阵的 bfs遍历auto bfs = [&]()->void{memset(vis,false,sizeof vis);std::queue<int> q;q.emplace(1);//emplace取代 push，可以加快运行速度 vis[1] = true;while(!q.empty()){auto t = q.front();q.pop();std::cout << t << ' ';for(int i = 1;i<=n;++i){if(!vis[i]&&g[t][i]){vis[i] = true;q.emplace(i);}}}};bfs();std::cout << '\n';return 0;
}

        测试

二、 vector实现邻接表

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
constexpr int MAX_N = 1e3+5,MAX_M = 1e6+5;
std::vector<std::pair<int,int>> edges[MAX_N];
bool vis[MAX_N];
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);//图的存储方式 2：vector实现邻接表 int n,m;std::cin >> n >> m;while(m--){int x,y,w;std::cin >> x >> y >> w;//假设没有重边，无向边需要加两条边edges[x].emplace_back(y,w);edges[y].emplace_back(x,w);}//vector实现邻接表的 dfs遍历memset(vis,false,sizeof vis);vis[1] = true;using Dfs = std::function<void(int)>;Dfs dfs = [&](int u)->void{std::cout << u << ' ';for(int i = 0;i<edges[u].size();++i){if(!vis[edges[u][i].first]){vis[edges[u][i].first]=true;dfs(edges[u][i].first);}}};dfs(1);std::cout << '\n';//vector实现邻接表的 bfs遍历auto bfs = [&]()->void{memset(vis,false,sizeof vis);std::queue<int> q;q.emplace(1);vis[1] = true;while(!q.empty()){auto t = q.front();q.pop();std::cout << t << ' ';for(int i = 0;i<edges[t].size();++i){if(!vis[edges[t][i].first]){vis[edges[t][i].first] = true;q.emplace(edges[t][i].first);}}}};bfs();std::cout << '\n';return 0;
}

        测试

三、 数组模拟单链表实现的前向星实现邻接表

#include <iostream>
#include <cstring>
#include <queue>
#include <functional>
constexpr int MAX_N = 1e3+5,MAX_M = 1e6+5;
//h数组为头节点，值表示下一个节点的下标，值为 -1则表示指向 NULL(nullptr)
//有 idx到 e[idx]的边，权值为 w[idx]，ne[idx]是 idx的下一个节点的下标 
int h[MAX_N],e[MAX_M],w[MAX_M],ne[MAX_M],idx;
bool vis[MAX_N];
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);//图的存储方式 3：前向星实现邻接表//采用数组模拟单链表来实现前向星auto init = [&]()->void{memset(h,-1,sizeof h);//头结点初始值为 -1，表示 next指向 NULL(nullptr) idx = 0;//下标从 0开始 };//注意这里是头插法，遍历的时候顺序是反的//但是大多数时候求最短路或者最小生成树不关注这个顺序 auto add = [&](int x,int y,int z)->void{//先勾右链，再勾左链e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;};init();int n,m;std::cin >> n >> m;while(m--){int x,y,z;std::cin >> x >> y >> z;add(x,y,z),add(y,x,z);}//前向星实现邻接表的 dfs遍历memset(vis,false,sizeof vis);vis[1] = true;using Dfs = std::function<void(int)>;Dfs dfs = [&](int u)->void{std::cout << u << ' ';for(int i = h[u];~i;i=ne[i]){int j = e[i];if(!vis[j]){vis[j] = true;dfs(j);}} };dfs(1);std::cout << '\n';//前向星实现邻接表的 bfs遍历auto bfs = [&]()->void{memset(vis,false,sizeof vis);std::queue<int> q;q.emplace(1);vis[1] = true;while(!q.empty()){auto t = q.front();q.pop();std::cout << t << ' ';for(int i = h[t];~i;i=ne[i]){int j = e[i];if(!vis[j]){vis[j] = true;q.emplace(j);}}}};bfs();std::cout << '\n';return 0;
}

        测试

四、 结构体数组直接存储边

#include <iostream>
#include <vector> 
#include <cstring>
#include <queue>
#include <algorithm>
#include <functional>
constexpr int MAX_N = 1e3+5,MAX_M = 1e6+5;
struct edge{int x,y,w;//重载 <符号，方便后续的sort()排序 bool operator < (const edge& W) {return w<W.w;}//写构造函数，方便后续直接 emplace_backedge(int _x,int _y,int _w):x(_x),y(_y),w(_w){}
};
std::vector<edge> edges;
std::vector<std::pair<int,int>> new_edges[MAX_N];
int h[MAX_N],e[MAX_M],w[MAX_M],ne[MAX_M],idx;
bool vis[MAX_N];
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);//图的存储方式 4：结构体数组直接存储边int n,m;std::cin >> n >> m;while(m--){int x,y,w;std::cin >> x >> y >> w;edges.emplace_back(x,y,w);}//如果要实现 dfs和 bfs，只需把这种存边方式转换成第2或第3种即可//若要转换成第二种： for(auto &t:edges){new_edges[t.x].emplace_back(t.y,t.w);}//若要转换成第三种：auto init = [&]()->void{memset(h,-1,sizeof h);idx = 0;};auto add = [&](int x,int y,int z)->void{e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;};init();for(auto &t:edges){add(t.x,t.y,t.w),add(t.y,t.x,t.w);}//再使用任意一种方式进行 dfs或者 bfs遍历//这里以第三种存图方式为例，dfs遍历 memset(vis,false,sizeof vis);vis[1] = true;using Dfs = std::function<void(int)>;Dfs dfs = [&](int u)->void{std::cout << u << ' ';for(int i = h[u];~i;i=ne[i]){int j = e[i];if(!vis[j]){vis[j] = true;dfs(j);}} };dfs(1);std::cout << '\n';//bfs遍历auto bfs = [&]()->void{memset(vis,false,sizeof vis);std::queue<int> q;q.emplace(1);vis[1] = true;while(!q.empty()){auto t = q.front();q.pop();std::cout << t << ' ';for(int i = h[t];~i;i=ne[i]){int j = e[i];if(!vis[j]){vis[j] = true;q.emplace(j);}}}};bfs();std::cout << '\n';//按照边的权重值大小遍历输出std::sort(edges.begin(),edges.end());for(auto &t:edges){std::cout << t.x << ' ' << t.y << ' ' << t.w << '\n';}return 0;
}

        测试