跳到主要内容

图的遍历 (Traversal)

图的遍历是所有图论算法的基础。通过深度优先搜索 (DFS) 或广度优先搜索 (BFS)，我们能系统地探测图的拓扑结构，发现连通块，并寻找特定路径。

一、 深度优先搜索 (DFS)​

1. 原理与哲学​

DFS 遵循“不撞南墙不回头”的贪心策略。它递归地访问每一个邻接点，直到到达叶子节点或已访问过的节点，然后回溯尝试其他分支。

2. 特性分析​

算法复杂度比较

观察输入规模 $n$ 增加时，不同复杂度的增长趋势

规模 $n$:10
O(1)
常数级
1
O(log n)
对数级
3
O(n)
线性级
10
O(n log n)
线性对数级
33
O(n²)
平方级
100
  • 典型应用：Tarjan 算法、拓扑排序（后序遍历）、连通分量计数、2-SAT。

二、 广度优先搜索 (BFS)​

1. 原理与扩张​

BFS 遵循“逐层波及”的策略。从起点开始，先访问距离为 1 的所有点，再访问距离为 2 的所有点。通常借助于队列 (Queue) 实现。

2. 最短路性质 (Optimal Property)​

定理：在无权图（或等权图）中，BFS 首次到达某个节点 vv 时，路径即为从起点到 vv 的最短路径。

3. 特性分析​

算法复杂度比较

观察输入规模 $n$ 增加时，不同复杂度的增长趋势

规模 $n$:10
O(1)
常数级
1
O(log n)
对数级
3
O(n)
线性级
10
O(n log n)
线性对数级
33
O(n²)
平方级
100

三、 工业级 C++ 实现​

#include <vector>
#include <queue>

using namespace std;

// DFS 递归版本
void dfs(int u, const vector<vector<int>>& adj, vector<bool>& vis) {
    vis[u] = true;
    for (int v : adj[u]) {
        if (!vis[v]) dfs(v, adj, vis);
    }
}

// BFS 迭代版本
void bfs(int start, const vector<vector<int>>& adj, vector<bool>& vis) {
    queue<int> q;
    q.push(start);
    vis[start] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

四、 选型对比​

特性DFSBFS
辅助结构栈 (递归栈)队列
空间优势路径深而窄时较优路径浅而宽时较优
寻找最短路不适合无权图首选
状态回溯极易实现较难实现

配套练习 (折叠解答)​

练习 1：连通分量计数​

如何使用遍历算法求一个无向图中的连通分量个数？

点击查看解析

方案：

  1. 维护 count = 0。
  2. 遍历所有节点 i∈[1,n]i \in [1, n]：
    • 若 ii 未被访问过，执行 dfs(i) 或 bfs(i)，且 count++。
  3. 最终 count 即为连通分量数。

练习 2：判定是否为二分图​

如何利用 BFS 判定一个图是否为二分图？

点击查看解析

方案：二染色法

  1. 为节点标记颜色（0, 1, 2，其中 0 代表未染色）。
  2. 在 BFS 过程中，若当前点 uu 的颜色为 CC，则其所有未染色的邻居 vv 染为 3−C3-C。
  3. 若遇到已染色的邻居 vv 且颜色与 uu 相同，则说明存在奇环，不是二分图。

练习 3：寻找环​

如何使用 DFS 寻找有向图中的环？

点击查看解析

方案：三色标记法

  1. 为节点设置三种状态：0（未访问）、1（正在访问）、2（访问完毕）。
  2. 在 DFS 过程中，若访问到状态为 1 的节点，则说明存在回指祖先的边，即存在环。
  3. 完成子树访问后，将节点状态由 1 改为 2。