一、课上练习

编程练习

1. 判断连通图: L3331

二、知识总结

✨ 核心思想

在图论中，连通性是一个描述图中顶点之间路径存在与否的概念。根据图是无向的还是有向的，连通性的定义和应用会有所不同。

✨ 路径相关术语

途径

途径（Walk），也称为链（Chain），是边和点的交错序列：

• 记作：v(0), e(1), v(1), e(2), v(2)
• 边的数量 k 被称作这条途径的长度

迹

对于一条途径 w，若 w 中所有边互不相同，则称 w 是一条迹（Trail）。

简单路径

对于一条迹 w，除起点和终点允许相同外，其他所有点各不相同，则称 w 是一条简单路径（Simple Path）。

回路

起点和终点相同的迹，被称为回路（Circuit）。

环/圈

起点和终点相同的简单路径，被称为环/圈（Cycle），又称简单回路（Simple Circuit）。

✨ 无向图的连通性

对于无向图，连通性通常指的是任意两个顶点间是否存在路径。

• 连通图：如果图中每一对顶点间都至少存在一条路径，则称该图为连通图。
• 不连通图：如果图中存在至少一对顶点间没有路径相连，则该图为不连通图。不连通的图可以分解为几个连通的子图，这些子图被称为连通分量。

✨ 有向图的连通性

有向图的连通性稍微复杂一些，因为路径的方向影响了可达性。

• 强连通图：如果有向图中每一对顶点 u 和 v 都满足从 u 到 v 以及从 v 到 u 都存在一条路径，则该图为强连通图。
• 弱连通图：如果将有向图中所有的有向边替换为无向边之后，图变成连通图，那么原来的有向图称为弱连通图。
• 强连通分量：有向图的最大强连通子图称为强连通分量。即图中的一个最大子图，其中的每一对顶点都是互相可达的。

✨ 执行示例

下面通过具体的例子，展示如何判断图的连通性。

无向图连通性判断示例

图： 6 个顶点，4 条边

0 -- 1 -- 2     3 -- 4
                  |
                  5

边：(0,1), (1,2), (3,4), (3,5)

判断过程（使用 DFS）：

从顶点 0 开始 DFS：

• 第 1 步：访问 0，标记 visited[0]=true
• 第 2 步：从 0 到 1，访问 1，标记 visited[1]=true
• 第 3 步：从 1 到 2，访问 2，标记 visited[2]=true
• 第 4 步：2 没有未访问的邻居，回溯到 1，再回溯到 0
• DFS 结束，visited = [true, true, true, false, false, false]

检查发现 3, 4, 5 未被访问，说明图不连通。

从顶点 3 再次 DFS：

• 访问 3 -> 4 -> 回溯 -> 5 -> 回溯
• visited = [true, true, true, true, true, true]

结论： 该图有 2 个连通分量：{0, 1, 2} 和 {3, 4, 5}

连通分量计数算法：

1count = 0
2for 每个顶点 v:
3    if v 未被访问:
4        count++
5        DFS(v)  // 标记所有可达顶点
6输出 count

有向图连通性判断示例

图： 4 个顶点

0 --> 1
^     |
|     v
3 <-- 2

边：(0,1), (1,2), (2,3), (3,0)

强连通性判断： 从任意顶点出发，能否到达所有其他顶点，且从所有其他顶点也能回到该顶点？

• 从 0 出发：0->1->2->3->0，可以回到起点，且经过了所有顶点
• 这是一个强连通图

如果去掉边 (3,0)： 从 0 可以到达 1, 2, 3，但从 3 无法回到 0。不再是强连通图。但将所有有向边变为无向边后仍然连通，所以是弱连通图。

✨ 解题步骤详解

以"判断连通图"为例：

问题： 给定一个无向图，判断它是否是连通图。

解题步骤：

1. 建图：读入顶点数 n 和边数 m，用邻接表存储图。
2. DFS/BFS 遍历：从顶点 0（或任意顶点）开始，进行一次 DFS 或 BFS，标记所有访问到的顶点。
3. 检查：遍历 visited 数组，如果所有顶点都被访问过，则图是连通的；否则不连通。

代码框架：

1void dfs(int v, vector<vector<int>>& adj, vector<bool>& visited) {
2    visited[v] = true;
3    for (int u : adj[v]) {
4        if (!visited[u]) dfs(u, adj, visited);
5    }
6}
7
8// 判断连通性
9vector<bool> visited(n, false);
10dfs(0, adj, visited);
11bool connected = true;
12for (int i = 0; i < n; i++) {
13    if (!visited[i]) { connected = false; break; }
14}

✨ 常见错误

1. 只做了一次 DFS 就判断连通：一次 DFS 只能访问一个连通分量中的所有顶点。如果要统计连通分量数，需要对所有未访问的顶点都进行 DFS。
2. 混淆强连通和弱连通：强连通要求任意两点互相可达（考虑方向），弱连通只要求忽略方向后连通。
3. 有向图中用无向图的方法判断连通性：有向图需要区分可达方向，不能简单地把有向边当无向边处理。
4. 忘记初始化 visited 数组：每次调用 DFS/BFS 前，确保 visited 数组正确初始化为 false。
5. 孤立顶点的处理：没有任何边的顶点也是一个独立的连通分量，不能忽略它。

三、课后练习

编程练习

1. 刻录光盘: L3332