?首先要明確什么是連通圖？？？

連通圖：對于一個圖來說，圖中的任意一個點都能訪問到所有的點，則說明該圖連通

?

很明顯，如果要判斷一個圖是否連通，則必須要從任意一個搜索一遍，判斷是否到達了所有的點，則很快會想到DFS和BFS。但是用并查集去判斷是否連通，這種思想去確實沒有想到。

如果用并查集來判斷確實可以加快速度。讓自己對并查集又有了新的認識。同時并查集還可以判斷一個圖是否形成自回路。

用一道題來說明連通圖的判斷：

給定一個無向圖和其中的所有邊，判斷這個圖是否所有頂點都是連通的。
輸入：每組數據的第一行是兩個整數n 和m（0< n <=1000）。n 表示圖的頂點
數目，m 表示圖中邊的數目。如果n 為0 表示輸入結束。隨后有m 行數據，每
行有兩個值x 和y（0<x, y <=n），表示頂點x 和y 相連，頂點的編號從1 開始計
算。輸入不保證這些邊是否重復。
輸出：對于每組輸入數據，如果所有頂點都是連通的，輸出 ’YES’ ，否則輸
出 ’NO’。
===樣例輸入===
4 3
1 2
2 3
3 2
3 2
1 2
2 3
0 0
===樣例輸出===
NO

YES

?

?

并查集：首先任選一點，判斷他是否可以到達其他各點，利用路徑壓縮，使得并查集更高效。

以圖為例：

?

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<vector>using namespace std;const int maxn = 1e6+5; int pre[maxn];int n, m;int find(int x){if(pre[x] == x) return x;else return pre[x] = find(pre[x]); }int main() {for(int i = 1; i <= maxn; i++) pre[i] = i;scanf("%d%d", &n, &m);for(int i = 0; i < m; i++){int u, v;scanf("%d%d", &u, &v);int fx = find(u), fy = find(v);pre[fx] = fy;}int cnt = 0;for(int i = 1; i <= n; i++){if(pre[i] == i) cnt++;}if(cnt == 1) printf("Yes\n");else printf("No\n");return 0; }

?

用DFS進行搜索，在搜索的時候邊搜索邊把已搜過的路刪掉

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<vector>using namespace std;const int maxn = 1e6+5;vector<int>G[maxn]; bool vis[maxn];int n, m;void dfs(int x){vis[x] = true;for(int i = 0; i < G[x].size(); i++){if(vis[G[x][i]]) G[x].erase(G[x].begin() + i);else dfs(G[x][i]); } }bool pan(){for(int i = 1; i <= n; i++){if(!vis[i]){return false;}}return true; } int main() {scanf("%d%d", &n, &m);for(int i = 0; i < m; i++){int u, v;scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}memset(vis, false, sizeof(vis));dfs(1); //從第一個點開始搜if(pan()) printf("Yes\n");else printf("No\n");return 0; }

?

?用BFS進行遍歷，用到隊列，對這一部分還應加強學習

?

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<vector>using namespace std; const int maxn = 1e6+5;vector<int>G[maxn]; int vis[maxn];int n, m;void bfs(int x){queue<int>Q;Q.push(x);while(!Q.empty()){int t = Q.front();Q.pop();vis[t] = true;for(int i = 0; i < G[t].size(); i++){if(vis[G[t][i]]) G[t].erase(G[t].begin() + i);else Q.push(G[t][i]);}} } bool pan(){for(int i = 1; i <= n; i++){if(!vis[i]) return false; }return true; }int main() {scanf("%d%d", &n, &m);for(int i = 0; i < m; i++){int u, v;scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u); }memset(vis, false, sizeof(vis));bfs(1);if(pan()) printf("Yes\n");else printf("No\n");return 0; }

?

總結

以上是生活随笔為你收集整理的连通图的判断（并查集， DFS， BFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。