图论|判断图连通性的三种方法（并查集/dfs/bfs） bfs|算法|dfs

首先要了解什么是连通图，这是百度百科百度百科——连通图
1.并查集
【图论|判断图连通性的三种方法（并查集/dfs/bfs）】首先统计连通分量的个数，如果一个图中连通分量个数大于1则肯定不是连通图，等于1则是连通图。

int n,m,f[N]; int find(int x) { if(f[x]!=x) f[x]=find(f[x]); return f[x]; } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) f[i]=i; for(int i=1; i<=m; i++) { int x,y; scanf("%d%d",&x,&y); int r1=find(x); int r2=find(y); f[r2]=r1; } int k=0; for(int i=1; i<=n; i++) if(f[i]==i) k++; if(k==1) printf("yes\n"); else printf("no\n"); return 0; }

2.dfs（邻接表/链式前向星）
如果一个图是连通的那么从任意一个点出发都能到达其它任何一个点，也就是只有一个连通分量。
邻接表版本

int vis[N],n,m; vectorg[N]; void dfs(int s) { vis[s]=1; for(int i=0; i<(int)g[s].size(); i++) { int v=g[s][i]; if(!vis[v]) dfs(v); } } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } dfs(1); int flag=1; for(int i=1; i<=n; i++) { if(!vis[i]) { flag=0; break; } } if(flag) printf("yes\n"); else printf("no\n"); return 0; }

链式前向星版本

int vis[N],n,m; struct edge { int to,next; }e[N]; int head[N],cnt; void addedge(int u,int v) { e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt; } void dfs(int s) { vis[s]=1; for(int i=head[s]; i; i=e[i].next) { int to=e[i].to; if(!vis[to]) dfs(to); } } int main() { scanf("%d%d",&n,&m); cnt=0; for(int i=1; i<=m; i++) { int x,y; scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } dfs(1); int flag=1; for(int i=1; i<=n; i++) { if(!vis[i]) { flag=0; break; } } if(flag) printf("yes\n"); else printf("no\n"); return 0; }

3.bfs
原理同dfs，改为队列即可。

int vis[N],n,m; struct edge { int to,next; }e[N]; int head[N],cnt; void addedge(int u,int v) { e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt; } void bfs(int s) { queueq; q.push(s); while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=1; for(int i=head[now]; i; i=e[i].next) { int to=e[i].to; if(!vis[to]) q.push(to); } } } int main() { scanf("%d%d",&n,&m); cnt=0; for(int i=1; i<=m; i++) { int x,y; scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } bfs(1); int flag=1; for(int i=1; i<=n; i++) { if(!vis[i]) { flag=0; break; } } if(flag) printf("yes\n"); else printf("no\n"); return 0; }