图论初步-连通图

大家好，欢迎来到IT知识分享网。

C++是一种功能强大的编程语言，广泛应用于系统软件、游戏开发、嵌入式系统、高性能计算等领域。在图论中，连通图是一个重要的概念，它指的是图中任意两个顶点之间都存在至少一条路径的图。

连通图的概念

定义

在无向图中，如果任意两个顶点之间都存在一条路径，那么这个图被称为连通图。在有向图中，如果任意两个顶点之间都存在一条有向路径，则称为强连通图。

属性

• 连通性：任意两个顶点之间都是连通的。
• 顶点数：连通图至少包含两个顶点。
• 边数：在无向图中，边数至少为顶点数减一（n-1），以保证连通性。

类型

• 完全图：图中的每对顶点之间都有边相连。
• 生成树：连通图中的最小连通子图，包含所有顶点，且边数为顶点数减一。
• 连通分量：在非连通图中，最大的连通子图称为连通分量。

思路

我们可以从任意一点(我这里用的是1)用DFS或BFS遍历图，遍历到点$i$的时候将$vis[i]$设为$true$,在遍历之后检查是否所有的$vis[i](i==1,2,\dots ,n)$都为1=$true$,这样就表示所有点都被遍历过了，也就是整张图都连通。

实现

以下是使用邻接表(BFS)实现连通图检测的一个简单示例：

//bfs实现判断连通块  //设一共有n个点,编号为1~n //vis[i]表示之前是否遍历过点i  void bfs() { 
    memset(vis,false,sizeof(vis)); queue<int> q; q.push(1); vis[1]=false; while (!q.empty()) { 
    int u=q.front(); q.pop(); int len=g[u].size(); for (int i=0;i<len;i++) { 
    int v=g[u][i].first; int w=g[u][i].second; if (vis[v]) continue; vis[v]=true; } } } bool check() { 
    bfs(); for (int i=1;i<=n;i++) if (!vis[i]) return false; //要是bfs没有遍历到这个点，说明图并不连通  return true; } 

当然，我们也可以用DFS解决这个问题

//dfs实现判断连通块 //设一共有n个点,编号为1~n //vis[i]表示之前是否遍历过点i void dfs(int u) { int len=g[u].size(); for (int i=0;i<len;i++) { int v=g[u][i].first; int w=g[u][i].second; if (vis[v]) continue; vis[v]=1; dfs(v); } } bool check() { memset(vis,false,sizeof(vis)); dfs(1); for (int i=1;i<=n;i++) if (!vis[i]) return false; //要是dfs没有遍历到这个点，说明图并不连通 return true; } 

总结

连通图是图论中的一个重要概念，它在网络、通信、交通等领域有着广泛的应用。在C++中，我们可以通过邻接矩阵、邻接表等数据结构来实现图的存储和操作，并利用深度优先搜索（DFS）或广度优先搜索（BFS）等算法来检测图的连通性。上述代码示例展示了如何使用邻接表和BFS来检测一个图是否是连通的。