连通图的判断（并查集， DFS， BFS）

 首先要明确什么是连通图？？？

连通图：对于一个图来说，图中的任意一个点都能访问到所有的点，则说明该图连通

 

很明显，如果要判断一个图是否连通，则必须要从任意一个搜索一遍，判断是否到达了所有的点，则很快会想到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）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。