前言

??????? 許多新手友友在初學(xué)算法和數(shù)據(jù)結(jié)構(gòu)時(shí)，會(huì)被圖論支配過。我這里整理了一下圖論常見的存儲(chǔ)和遍歷方式，僅供參考。如有問題，歡迎大佬們批評(píng)指正。

??????? 存儲(chǔ)我將提到四種方式：鄰接矩陣、vector實(shí)現(xiàn)鄰接表、數(shù)組模擬單鏈表實(shí)現(xiàn)的前向星實(shí)現(xiàn)鄰接表、結(jié)構(gòu)體數(shù)組直接存儲(chǔ)邊。遍歷我將提到三種方式：dfs、bfs、按照邊的權(quán)重值大小遍歷輸出。

一、鄰接矩陣

#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);//圖的存儲(chǔ)方式 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函數(shù)可以進(jìn)行遞歸 Dfs dfs = [&](int u)->void{//lambda表達(dá)式（函數(shù)） 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，可以加快運(yùn)行速度 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實(shí)現(xiàn)鄰接表

#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);//圖的存儲(chǔ)方式 2：vector實(shí)現(xiàn)鄰接表 int n,m;std::cin >> n >> m;while(m--){int x,y,w;std::cin >> x >> y >> w;//假設(shè)沒有重邊，無向邊需要加兩條邊edges[x].emplace_back(y,w);edges[y].emplace_back(x,w);}//vector實(shí)現(xiàn)鄰接表的 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實(shí)現(xià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 = 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;
}

??????? 測試

三、 數(shù)組模擬單鏈表實(shí)現(xiàn)的前向星實(shí)現(xiàn)鄰接表

#include <iostream>
#include <cstring>
#include <queue>
#include <functional>
constexpr int MAX_N = 1e3+5,MAX_M = 1e6+5;
//h數(shù)組為頭節(jié)點(diǎn)，值表示下一個(gè)節(jié)點(diǎn)的下標(biāo)，值為 -1則表示指向 NULL(nullptr)
//有 idx到 e[idx]的邊，權(quán)值為 w[idx]，ne[idx]是 idx的下一個(gè)節(jié)點(diǎn)的下標(biāo) 
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);//圖的存儲(chǔ)方式 3：前向星實(shí)現(xiàn)鄰接表//采用數(shù)組模擬單鏈表來實(shí)現(xiàn)前向星auto init = [&]()->void{memset(h,-1,sizeof h);//頭結(jié)點(diǎn)初始值為 -1，表示 next指向 NULL(nullptr) idx = 0;//下標(biāo)從 0開始 };//注意這里是頭插法，遍歷的時(shí)候順序是反的//但是大多數(shù)時(shí)候求最短路或者最小生成樹不關(guān)注這個(gè)順序 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);}//前向星實(shí)現(xiàn)鄰接表的 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';//前向星實(shí)現(xià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;
}

??????? 測試

四、 結(jié)構(gòu)體數(shù)組直接存儲(chǔ)邊

#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;//重載 <符號(hào)，方便后續(xù)的sort()排序 bool operator < (const edge& W) {return w<W.w;}//寫構(gòu)造函數(shù)，方便后續(xù)直接 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);//圖的存儲(chǔ)方式 4：結(jié)構(gòu)體數(shù)組直接存儲(chǔ)邊int n,m;std::cin >> n >> m;while(m--){int x,y,w;std::cin >> x >> y >> w;edges.emplace_back(x,y,w);}//如果要實(shí)現(xiàn) dfs和 bfs，只需把這種存邊方式轉(zhuǎn)換成第2或第3種即可//若要轉(zhuǎn)換成第二種： for(auto &t:edges){new_edges[t.x].emplace_back(t.y,t.w);}//若要轉(zhuǎn)換成第三種：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);}//再使用任意一種方式進(jìn)行 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';//按照邊的權(quán)重值大小遍歷輸出std::sort(edges.begin(),edges.end());for(auto &t:edges){std::cout << t.x << ' ' << t.y << ' ' << t.w << '\n';}return 0;
}

????????測試