图的遍历（BFS与DFS） - 数据结构与算法-学习笔记-上海佼艾

一、概述

图（Graph）是最灵活、最强大的数据结构之一，广泛应用于社交网络、地图导航、网页爬虫、编译器依赖分析等场景。而图的遍历（Graph Traversal）是图算法的基础——几乎所有高级图算法都是在遍历的框架下构建的。所谓图的遍历，就是从图中的某个顶点出发，沿着边系统地访问图中的每一个顶点，且每个顶点仅被访问一次。

图的两种最核心的遍历策略是深度优先搜索（Depth-First Search, DFS）和广度优先搜索（Breadth-First Search, BFS）。DFS 模仿"走迷宫"——沿着一条路走到底，走不通再回头；BFS 则像"水波扩散"——从起点一层一层向外扩展。理解这两种遍历方式，是掌握图论算法的第一步，也是面试中的高频考点。

前置知识：递归与栈的基本概念、队列的基本操作、图的基本术语（顶点 Vertex、边 Edge、邻接表 Adjacency List、邻接矩阵 Adjacency Matrix）。

二、图的表示方法

在编写遍历代码之前，首先需要确定图在内存中的存储方式。最常用的两种表示方法是邻接表和邻接矩阵。

2.1 邻接表（Adjacency List）

邻接表为每个顶点维护一个列表，存储与该顶点直接相连的所有邻居顶点。对于稀疏图（边数远小于顶点数的平方），邻接表在空间和时间上都具有明显优势，是实际工程中最主流的选择。

# 用邻接表表示无向图
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1, 5],
    5: [2, 4]
}

# 用邻接表表示有向图
digraph = {
    0: [1, 2],
    1: [3],
    2: [5],
    3: [],
    4: [1],
    5: [4]
}

2.2 邻接矩阵（Adjacency Matrix）

邻接矩阵使用一个 V × V 的二维数组存储图的信息，matrix[i][j] = 1 表示顶点 i 到 j 存在边（有权图中则存储权值）。邻接矩阵的优点是判断任意两点之间是否有边只需 O(1) 时间，但空间复杂度为 O(V²)，不适合存储稀疏图。

# 用邻接矩阵表示无向图（5个顶点）
adj_matrix = [
    [0, 1, 1, 0, 0],  # 顶点 0 与 1, 2 相连
    [1, 0, 0, 1, 1],  # 顶点 1 与 0, 3, 4 相连
    [1, 0, 0, 0, 1],  # 顶点 2 与 0, 4 相连
    [0, 1, 0, 0, 0],  # 顶点 3 与 1 相连
    [0, 1, 1, 0, 0]   # 顶点 4 与 1, 2 相连
]

2.3 图的构建辅助函数

为了方便后续示例的统一调用，我们预先定义一个从边列表构建邻接表的工具函数：

def build_graph(n, edges, directed=False):
    """构建邻接表表示的有向图或无向图"""
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

# 示例：5个顶点，4条边的无向图
edges = [(0, 1), (0, 2), (1, 3), (1, 4)]
g = build_graph(5, edges)
# g = [[1, 2], [0, 3, 4], [0], [1], [1]]

选择建议：绝大多数算法问题中，邻接表是默认选择。仅当图的稠密度很高（边数接近 V²）或需要频繁判断边是否存在时，再考虑邻接矩阵。

三、深度优先搜索（DFS）

深度优先搜索的核心思路是回溯：从起始顶点出发，沿着一条路径尽可能深地探索，直到没有未访问的邻居为止，然后回溯到上一个顶点，继续探索其他分支。DFS 可以天然地利用递归实现，也可以用显式的栈来模拟。

3.1 递归实现

递归是最直观的 DFS 写法。我们用一个 visited 数组（或集合）记录已访问顶点，防止重复访问和无限循环。

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')  # 前序访问
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    # 后序位置：离开顶点时执行的操作
    return visited

# 用例
graph = {0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1, 5], 5: [2, 4]}
dfs_recursive(graph, 0)
# 输出: 0 1 3 4 5 2

3.2 迭代实现（显式栈）

递归的 DFS 受限于系统调用栈的深度，当图规模很大时可能发生栈溢出。此时可以用显式的栈（Stack）代替递归：

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            print(vertex, end=' ')
            visited.add(vertex)
            # 逆序压栈，保持与递归一致的遍历顺序
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited

dfs_iterative(graph, 0)
# 输出: 0 1 3 4 5 2

关键理解：递归实现中，我们在 for 循环之前访问顶点（前序），在 for 循环之后回到该顶点（后序）。后序位置是 DFS 最强大的特性——在从子问题返回的时机执行操作，这正是拓扑排序和许多 DP 问题的基础。

3.3 DFS 树与边的分类

对图执行 DFS 时，所有被遍历的边和顶点可以构成一棵 DFS 树（森林）。在此基础上，原图中的边可以分为四种类型：

树边（Tree Edge）：DFS 树中的边，即第一次访问某个顶点时所经过的边。
回边（Back Edge）：指向 DFS 树中祖先顶点的边，用于检测环。
前向边（Forward Edge）：指向 DFS 树中后代顶点的边（仅在有向图中存在）。
横叉边（Cross Edge）：连接不同子树顶点的边（仅在有向图中存在）。

通过引入 entry_time（首次访问时间）和 exit_time（离开时间）两个时间戳，可以在 DFS 过程中唯一地判断每条边的类型，为环检测、强连通分量等高级算法奠定基础。

def dfs_with_timestamps(graph, start):
    visited = set()
    entry = {}
    def _dfs(v, time):
        visited.add(v)
        entry[v] = time
        for n in graph[v]:
            if n not in visited:
                time = _dfs(n, time + 1)
        exit_time[v] = time + 1
        return time + 1
    exit_time = {}
    _dfs(start, 0)
    return entry, exit_time

四、广度优先搜索（BFS）

广度优先搜索的核心思想是按层遍历：从起始顶点出发，先访问所有距离为 1 的邻居，再访问所有距离为 2 的邻居，依此类推。BFS 天然地借助队列（Queue）实现，保证先入队的顶点先被处理。

4.1 队列实现

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        vertex = queue.popleft()  # O(1) 出队
        print(vertex, end=' ')
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

graph = {0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1, 5], 5: [2, 4]}
bfs(graph, 0)
# 输出: 0 1 2 3 4 5

4.2 层序遍历与最短路径

BFS 最重要的性质是：在无权图中，首次访问到某个顶点所经过的路径就是最短路径。利用这一性质，我们可以在 BFS 过程中记录每个顶点的距离和前驱节点，从而重构完整的最短路径。

def bfs_shortest_path(graph, start, target):
    """返回从 start 到 target 的最短路径（无权图）"""
    visited = set([start])
    queue = deque([(start, [start])])
    while queue:
        vertex, path = queue.popleft()
        if vertex == target:
            return path
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None  # 不可达

# 计算从 0 到 5 的最短路径
print(bfs_shortest_path(graph, 0, 5))
# 输出: [0, 2, 5]

4.3 按层输出的 BFS

在某些场景（如"二叉树的层序遍历"、"单词接龙"）中，我们需要知道 BFS 的当前层数。这时可以用双重循环来区分每一层：

def bfs_level_order(graph, start):
    visited = set([start])
    queue = deque([start])
    level = 0
    while queue:
        level_size = len(queue)
        print(f"第 {level} 层: ", end='')
        for _ in range(level_size):
            vertex = queue.popleft()
            print(vertex, end=' ')
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        print()  # 换行
        level += 1

最短路径性质证明（简述）：BFS 按层访问顶点——距离起点为 k 的顶点一定在第 k 层被首次访问。这是因为从起点到任意顶点的最短路径上，前驱顶点到起点的距离一定比当前顶点少 1，而 BFS 队列的 FIFO 特性保证了按距离递增的顺序处理顶点。这一性质使 BFS 成为无权图最短路径问题的标准解法。

五、连通分量计数

在无向图中，如果从顶点 u 可以通过若干条边到达顶点 v，则称 u 和 v 连通。连通分量（Connected Component）是图的最大连通子图。统计连通分量数量是图遍历的典型应用——只需对每个未访问的顶点启动一次 DFS 或 BFS，启动的次数就是连通分量的个数。

def count_connected_components(graph):
    n = len(graph)
    visited = set()
    count = 0

    def dfs(v):
        visited.add(v)
        for neighbor in graph[v]:
            if neighbor not in visited:
                dfs(neighbor)

    for v in range(n):
        if v not in visited:
            count += 1
            dfs(v)  # 也可替换为 BFS

    return count

# 示例：三个连通分量
g = {0: [1], 1: [0], 2: [3], 3: [2], 4: []}
print(count_connected_components(g))
# 输出: 3  （{0,1}、{2,3}、{4}）

应用场景：社交网络中的"朋友圈"计数、图像处理中的连通区域标记、地图中的岛屿数量统计（LeetCode 200. 岛屿数量）等。

六、二分图检测

二分图（Bipartite Graph）是指可以将所有顶点划分为两个互不相交的集合，使得图中每条边都连接不同集合的顶点。等价地，二分图中不存在奇数长度的环。检测二分图可以通过 DFS 或 BFS 为每个顶点染色（0 或 1），如果相邻顶点出现了相同颜色，则不是二分图。

6.1 基于 BFS 的染色法

from collections import deque

def is_bipartite(graph):
    n = len(graph)
    color = [-1] * n  # -1: 未染色, 0/1: 两种颜色

    def bfs_check(start):
        queue = deque([start])
        color[start] = 0
        while queue:
            v = queue.popleft()
            for nb in graph[v]:
                if color[nb] == -1:
                    color[nb] = 1 - color[v]  # 染为相反色
                    queue.append(nb)
                elif color[nb] == color[v]:
                    return False  # 冲突，不是二分图
        return True

    for v in range(n):
        if color[v] == -1:
            if not bfs_check(v):
                return False
    return True

# 测试
print(is_bipartite({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}))  # True（偶环）
print(is_bipartite({0: [1, 2], 1: [0, 2], 2: [0, 1]}))           # False（三角环）

6.2 基于 DFS 的染色法

def is_bipartite_dfs(graph):
    n = len(graph)
    color = [-1] * n

    def dfs(v, c):
        color[v] = c
        for nb in graph[v]:
            if color[nb] == -1:
                if not dfs(nb, 1 - c):
                    return False
            elif color[nb] == c:
                return False
        return True

    for v in range(n):
        if color[v] == -1:
            if not dfs(v, 0):
                return False
    return True

二分图应用：匹配问题（如"匈牙利算法"）、任务分配（如"将工人分配到互斥的工作"）、电影推荐系统中的用户-物品二部图建模等。

七、图的环检测

检测图中是否存在环（Cycle）是图遍历的又一经典应用。有向图和无向图的环检测策略略有不同。

7.1 无向图的环检测

在无向图中，如果在 DFS 过程中发现一个已访问过的邻居，且该邻居不是当前顶点的直接前驱（parent），则说明存在环。实现时只需在递归中额外传递父顶点参数即可。

def has_cycle_undirected(graph):
    n = len(graph)
    visited = [False] * n

    def dfs(v, parent):
        visited[v] = True
        for nb in graph[v]:
            if not visited[nb]:
                if dfs(nb, v):
                    return True
            elif nb != parent:  # 已访问且不是父节点 → 有环
                return True
        return False

    for v in range(n):
        if not visited[v]:
            if dfs(v, -1):
                return True
    return False

# 测试
print(has_cycle_undirected({0: [1], 1: [0, 2], 2: [1]}))         # False（链）
print(has_cycle_undirected({0: [1, 2], 1: [0, 2], 2: [0, 1]}))  # True（三角形）

7.2 有向图的环检测

有向图中的环检测需要追踪递归调用栈上当前的活跃顶点。如果在 DFS 过程中遇到了当前调用栈上还标记着的顶点，则说明存在有向环。我们通常使用三种状态来标记顶点：0 = 未访问，1 = 正在访问（在递归栈上），2 = 已访问完毕。

def has_cycle_directed(graph):
    n = len(graph)
    state = [0] * n  # 0: 未访问, 1: 在栈上, 2: 已结束

    def dfs(v):
        if state[v] == 1:   # 遇到在栈上的顶点 → 有环
            return True
        if state[v] == 2:   # 已处理完毕，无需重复
            return False

        state[v] = 1  # 标记为正在访问
        for nb in graph[v]:
            if dfs(nb):
                return True
        state[v] = 2  # 标记为已结束
        return False

    for v in range(n):
        if dfs(v):
            return True
    return False

# 测试
dag = {0: [1], 1: [2], 2: [], 3: [4], 4: []}
cyclic = {0: [1], 1: [2], 2: [0]}
print(has_cycle_directed(dag))     # False
print(has_cycle_directed(cyclic))  # True

八、拓扑排序的 DFS 实现

拓扑排序（Topological Sort）是有向无环图（DAG）的一种线性排序，使得对任意有向边 u → v，u 在排序中都出现在 v 之前。拓扑排序在编译器（依赖分析）、任务调度、课程安排等问题中有广泛的应用。

8.1 基于 DFS 的拓扑排序

DFS 后序遍历天然适合拓扑排序：递归处理完一个顶点的所有邻居后，将该顶点压入栈中，最后从栈顶到栈底依次弹出即为拓扑序。本质上，当我们离开一个顶点时，该顶点的所有后继都已处理完毕，因此它可以安全地插入到结果的最前面。

def topological_sort(graph):
    n = len(graph)
    visited = [False] * n
    result = []  # 模拟栈

    def dfs(v):
        visited[v] = True
        for nb in graph[v]:
            if not visited[nb]:
                dfs(nb)
        result.append(v)  # 后序位置：所有依赖已处理完

    for v in range(n):
        if not visited[v]:
            dfs(v)

    result.reverse()  # 反转得到拓扑序
    return result

# 示例：课程依赖关系
# 学习 A 需要先学 B 和 C，学习 B 需要先学 D
courses = {0: [], 1: [], 2: [3], 3: [1], 4: [0, 1], 5: [0, 2]}
print(topological_sort(courses))
# 可能的输出: [0, 1, 3, 2, 4, 5]
# 解释: 0 和 1 无依赖，3 依赖于 1，2 依赖于 3，4 依赖于 0,1，5 依赖于 0,2

8.2 带环检测的拓扑排序

实际工程中，我们往往需要在排序前先确保图是 DAG。可以结合 7.2 节的环检测，在 DFS 过程中发现环时立即报错：

def topological_sort_safe(graph):
    n = len(graph)
    state = [0] * n  # 0:未访问, 1:在栈上, 2:已结束
    result = []

    def dfs(v):
        if state[v] == 1:
            raise ValueError("图中存在环，无法拓扑排序")
        if state[v] == 2:
            return
        state[v] = 1
        for nb in graph[v]:
            dfs(nb)
        state[v] = 2
        result.append(v)

    for v in range(n):
        if state[v] == 0:
            dfs(v)

    result.reverse()
    return result

拓扑排序 vs DFS 后序：拓扑排序的核心思想正是 DFS 的后序遍历——在离开一个顶点时将其加入结果，再整体反转。这背后的原理是：只有在所有后继都处理完毕后，当前顶点才能被"完成"，因此后序列表天然满足"后继在前，前驱在后"的关系，反转后即得到拓扑序。

九、BFS vs DFS 对比全面分析

理解了两种遍历方法之后，我们来系统对比它们的特点，以便在不同的场景中做出合适的选择。

对比维度	DFS（深度优先搜索）	BFS（广度优先搜索）
核心数据结构	栈（Stack，递归或显式）	队列（Queue）
时间复杂度	O(V + E)（邻接表）	O(V + E)（邻接表）
空间复杂度	O(V) — 最坏栈深度等于顶点数	O(V) — 最坏队列宽度等于顶点数
访问顺序	先深后广，一条路走到底	按层扩展，逐层推进
最短路径	不保证最短路径	无权图必然得到最短路径
递归友好	天然适合递归实现	通常用迭代实现
路径枚举	适合枚举所有路径	通常只求最短路径
隐含特性	后序遍历可用于拓扑排序	层序遍历可用于"距离"计算

DFS 擅长场景

连通分量统计
环检测（有向 / 无向）
拓扑排序
二分图检测（DFS 染色）
路径搜索 / 回溯问题（如迷宫求解）
强连通分量（Tarjan / Kosaraju 算法）

BFS 擅长场景

无权图最短路径
层序遍历 / 按距离分组
二分图检测（BFS 染色）
单词接龙（Word Ladder）
社交网络中的"关系度数"
网络爬虫的"礼貌抓取"策略

注意：当图非常大（上亿顶点）且树形较深时，递归 DFS 可能导致调用栈溢出，此时应优先考虑迭代式 DFS 或 BFS。

十、核心要点总结

DFS 核心：递归（或显式栈）+ visited 标记。前序位置（进入时操作）和后序位置（离开时操作）分别对应不同的处理时机。后序位置是拓扑排序和许多树形 DP 的基础。
BFS 核心：队列 + visited 标记（在入队时标记可避免重复入队）。BFS 的层序遍历天然适用于无权图最短路径问题。
visited 的三种状态：未访问（0）、在栈上（1，用于有向图环检测）、已处理完毕（2）。使用三种状态而非布尔值的两状态，可以在一次 DFS 中同时完成环检测和拓扑排序。
时间复杂度 O(V+E)：无论 BFS 还是 DFS，每个顶点和每条边都恰好处理一次，因此在邻接表表示下两者时间复杂度相同。空间复杂度在最坏情况下也都是 O(V)。
选择策略：需要最短路径选 BFS；需要利用后序信息（拓扑排序、连通分量、环检测）选 DFS。两者都可以用于二分图检测和连通分量计数。
通用模板：学会 BFS 和 DFS 的框架后，只需在遍历过程中增加少量状态记录，就能解决大量图算法问题。请务必熟练掌握本笔记中给出的所有代码模板。

十一、进一步思考

11.1 大数据量下的图遍历

当图规模达到千万级顶点时，递归 DFS 可能因系统调用栈溢出而崩溃。迭代式 DFS 和 BFS 虽然可以避免这个问题，但 Python 中 list 和 deque 的入栈/入队操作本身也有内存开销。在大数据场景下，可以考虑使用生成器（yield）惰性遍历，或借助数据库/图计算框架（如 Neo4j、Spark GraphX）进行分布式处理。

11.2 从遍历到高级算法

BFS 和 DFS 是图算法大厦的基石，许多高级算法都是在遍历框架上叠加额外的数据结构或状态信息构建的：

Tarjan 算法：在 DFS 上增加 low-link 值，求解强连通分量和割点/桥。
Dijkstra 算法：将 BFS 的普通队列替换为优先队列，用于加权图最短路径。
A* 搜索：在 Dijkstra 基础上加入启发式函数，加速目标导向的搜索。
双向 BFS：从起点和终点同时 BFS，当两个搜索前沿相遇时即找到最短路径，可将搜索空间从 b^d 缩小到约 2 * b^(d/2)。
迭代加深 DFS（IDDFS）：结合 DFS 的空间优势和 BFS 的最短路径保证，通过不断增加深度限制来重复执行 DFS。

11.3 刷题心法

在 LeetCode 等刷题平台上，遇到图相关题目时可以参考以下思路来快速选择算法：

先判断是否连通图：用 DFS/BFS 做连通分量判断。
需要最短路径？→ BFS（无权图）或 Dijkstra（加权图）。
需要所有路径或排列？→ DFS + 回溯 + 剪枝。
有依赖关系？→ 拓扑排序（DFS 后序或 Kahn 算法）。
需要分组（染色）？→ BFS/DFS 二分图检测。
判断是否有环？→ DFS 三色标记法。

"图遍历是图算法的灵魂——学会了 BFS 和 DFS，就等于拿到了打开图论大门的钥匙。真正的高手不在于记住多少算法模板，而在于理解遍历过程中顶点状态的变化时机，并利用这些时机来解决具体问题。"