图论算法基础：表示、遍历与拓扑排序
High Contrast
Dark Mode
Light Mode
Sepia
Forest
13 min read2,623 words

图论算法基础：表示、遍历与拓扑排序

简介

图论是计算机科学中用于建模对象间复杂关系的强大工具，广泛应用于社交网络、路径规划、任务调度、编译器优化等领域。掌握图论算法是解决众多高级算法问题的基石。本章将深入探讨图论的基础知识，包括图的两种核心表示方法——邻接表和邻接矩阵，这是所有图算法得以实现的前提。在此基础上，我们将详细解析图的两种基本遍历策略：深度优先遍历和广度优先遍历，它们是探索图结构的通用范式。最后，我们将聚焦于有向无环图的一个重要应用——拓扑排序，并介绍其两种经典算法：基于入度的Kahn算法和基于深度优先搜索的后序遍历方法。本章内容将通过“课程表”、“克隆图”、“岛屿的最大面积”等经典例题进行实战演练，帮助读者从理论到实践，全面构建图论算法的知识体系。

核心概念

图（Graph）由顶点（Vertex）和边（Edge）组成。根据边是否有方向，可分为有向图和无向图。根据边是否带有权重，可分为无权图和有权图。理解图的表示方法是实现算法的第一步。

邻接表 是一种空间效率较高的表示方法，特别适用于稀疏图。它为图中的每个顶点维护一个列表，记录所有与该顶点直接相连的邻接顶点。在无向图中，一条边会被存储两次（分别在两个顶点的邻接表中）；在有向图中，则只存储一次（在起点的邻接表中）。邻接表的优点是能快速找到一个顶点的所有邻居，空间复杂度为 O(V+E)，其中V是顶点数，E是边数。

邻接矩阵 是一个 V x V 的二维数组。对于无权图，matrix[u][v] = 1 表示存在从顶点 u 到顶点 v 的边，否则为0。对于有权图，该位置存储边的权重。邻接矩阵的优点是可以在 O(1) 时间内判断任意两个顶点间是否有边相连，但其空间复杂度为 O(V²)，因此更适用于稠密图。

图的遍历 是系统访问图中所有顶点的过程。深度优先遍历 沿着一条路径尽可能深地探索，直到无法继续，然后回溯到上一个分叉点。它通常使用递归或栈来实现，适合解决连通性、环检测、拓扑排序等问题。广度优先遍历 则按“层次”进行，先访问起始顶点的所有邻居，再访问邻居的邻居。它通常使用队列来实现，适合求解最短路径（在无权图中）、层级扩散等问题。

拓扑排序 是针对有向无环图的一种线性顶点排序，使得对于图中的每一条有向边 (u, v)，顶点 u 在排序中都出现在顶点 v 之前。它本质上是图的一种特定遍历顺序，常用于解决具有依赖关系的任务调度问题，如课程安排、构建系统等。

下图展示了从图的基本表示到拓扑排序结果的核心流程：

graph TD A["原始有向图"] --> B{选择表示方法} B --> C["邻接表
（空间高效）"] B --> D["邻接矩阵
（查询快速）"] C --> E["执行遍历算法"] D --> E E --> F{遍历目标？} F --> G["深度优先遍历
（DFS）"] F --> H["广度优先遍历
（BFS）"] G --> I["检测环 / 后序DFS"] H --> J["计算最短路径"] I --> K["生成拓扑序列"] J --> L["得到BFS层级"] K --> M["最终结果：
拓扑排序"]

实战示例

下面我们通过解决 LeetCode 207题“课程表”来演示拓扑排序的 Kahn 算法实现。问题描述：你需要选修 numCourses 门课程，记为 0 到 numCourses-1。给定一个数组 prerequisites，其中 prerequisites[i] = [ai, bi] 表示要学习课程 ai 必须先完成课程 bi。判断是否可能完成所有课程的学习（即判断图是否有环）。

from collections import deque
from typing import List
def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
"""
使用Kahn算法（基于BFS的拓扑排序）判断课程安排图是否是有向无环图(DAG)。
参数:
numCourses: 课程总数（顶点数）
prerequisites: 先修关系列表，每个元素 [ai, bi] 表示 ai 依赖于 bi
返回:
bool: 如果可以完成所有课程（无环）返回True，否则返回False
"""
# 1. 初始化邻接表和入度数组
# 邻接表：记录每个顶点的后继顶点（出边）
adj_list = [[] for _ in range(numCourses)]
# 入度数组：记录每个顶点的入度（有多少条边指向它）
in_degree = [0] * numCourses
# 2. 构建图：填充邻接表和入度数组
for course, pre in prerequisites:
# 添加一条从 pre 指向 course 的边
adj_list[pre].append(course)
# course 的入度加1
in_degree[course] += 1
# 3. 初始化队列：将所有入度为0的顶点加入队列
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
# 4. 拓扑排序过程
visited_count = 0  # 记录已排序（访问）的顶点数量
while queue:
# 从队列中取出一个入度为0的顶点
current = queue.popleft()
visited_count += 1
# 遍历当前顶点的所有后继顶点
for neighbor in adj_list[current]:
# “移除”从 current 到 neighbor 的边：将后继顶点的入度减1
in_degree[neighbor] -= 1
# 如果后继顶点的入度变为0，则加入队列
if in_degree[neighbor] == 0:
queue.append(neighbor)
# 5. 判断结果：如果访问过的顶点数等于总顶点数，说明拓扑排序成功（无环）
return visited_count == numCourses
# 测试用例
if __name__ == "__main__":
# 示例 1: 可以完成，图无环
numCourses1 = 2
prerequisites1 = [[1, 0]]
print(f"测试1 - 能否完成课程？ {canFinish(numCourses1, prerequisites1)}")  # 应输出 True
# 示例 2: 无法完成，图有环 (0->1, 1->0)
numCourses2 = 2
prerequisites2 = [[1, 0], [0, 1]]
print(f"测试2 - 能否完成课程？ {canFinish(numCourses2, prerequisites2)}")  # 应输出 False
# 示例 3: 多门课程，复杂依赖
numCourses3 = 4
prerequisites3 = [[1, 0], [2, 1], [3, 2]]
print(f"测试3 - 能否完成课程？ {canFinish(numCourses3, prerequisites3)}")  # 应输出 True

对比分析

下表详细对比了图的两种表示方法、两种遍历方式以及两种拓扑排序算法：

方案 优势 劣势 适用场景
邻接表 1. 空间复杂度低，为 O(V+E)，适合稀疏图。
2. 能高效地遍历一个顶点的所有邻居。
3. 动态增删边较为方便。		 1. 判断任意两个顶点间是否有边需要 O(degree(V)) 时间。
2. 存储结构相对复杂。		 绝大多数算法题和实际应用，如图遍历、最短路径（Dijkstra, SPFA）、拓扑排序等。
邻接矩阵 1. 判断任意两顶点间是否有边仅需 O(1) 时间。
2. 结构简单直观，易于理解和实现。
3. 适合表示稠密图。		 1. 空间复杂度高，为 O(V²)，浪费大量空间用于稀疏图。
2. 遍历一个顶点的所有邻居需要 O(V) 时间。		 顶点数较少（V < 1000）的稠密图，或需要频繁进行边存在性查询的场景。
深度优先遍历 (DFS) 1. 实现简洁，常使用递归。
2. 天然适合处理“探索到尽头”的问题，如找环、连通分量。
3. 在回溯过程中方便记录路径信息。		 1. 递归实现可能导致栈溢出（对于极深图）。
2. 不保证找到的是最短路径。		 拓扑排序（DFS后序逆序）、寻找连通分量、检测图中环、回溯问题（如迷宫）。
广度优先遍历 (BFS) 1. 保证在无权图中找到的是起点到各点的最短路径。
2. 使用队列，无栈溢出风险。
3. 按“层级”扩散，适合计算最短距离。		 1. 通常需要更多内存来维护队列。
2. 代码相比递归DFS稍显复杂。		 无权图最短路径、层级遍历（如克隆图）、拓扑排序（Kahn算法）、扩散类问题（如岛屿面积）。
拓扑排序 (Kahn算法) 1. 基于BFS，直观反映了“从入度为0的顶点开始”的过程。
2. 易于检测环：若最终排序顶点数小于总数，则存在环。
3. 可以方便地输出排序序列。		 1. 需要额外维护入度数组。
2. 需要预先计算所有顶点的入度。		 大多数需要拓扑排序的场景，尤其是需要同时检测环和获取排序结果时。
拓扑排序 (DFS方法) 1. 基于标准的DFS，代码与DFS遍历高度统一。
2. 在DFS过程中可以同时完成环检测和排序。
3. 有时更节省空间（递归栈）。		 1. 最终得到的是逆后序序列，需要反转。
2. 递归深度可能受限于图深度。
3. 逻辑上不如Kahn算法直观。		 已经需要进行DFS遍历的图，或者问题本身需要深度优先的特性（如强连通分量分解中的第一步）。

最佳实践

  1. 根据图密度选择表示法：面对算法问题时，首先评估图的稀疏性。如果边数 E 远小于 V²，优先使用邻接表。这是LeetCode图论题中最常见的做法。只有在题目明确给出稠密图或顶点数极少时，才考虑邻接矩阵。

  2. 使用访问标记数组防止重复访问：无论是DFS还是BFS，在遍历时都必须使用一个 visited 数组（或集合）来记录已访问过的顶点，避免陷入无限循环或重复计算。对于无环图或树，有时可以通过判断当前节点是否为其父节点来替代 visited 数组，但使用 visited 数组是最稳妥通用的做法。

  3. 拓扑排序优先考虑Kahn算法：对于典型的任务调度、课程安排问题，Kahn算法（基于BFS）通常是更优选择。它的逻辑清晰（不断移除入度为0的节点），并且能在排序过程中直接判断图中是否有环（排序结果包含所有顶点），代码模板化程度高，易于记忆和实现。

  4. DFS遍历时注意递归深度：Python默认递归深度有限（约1000层）。如果问题中的图可能非常深（例如一条长链），使用递归DFS可能导致 RecursionError。此时应使用显式栈（list 模拟栈）来实现迭代DFS，或者转而使用BFS。

  5. 灵活运用遍历框架解决变体问题：许多图论问题本质上是遍历的变体。例如，“克隆图”是在BFS/DFS遍历的同时复制节点和边；“岛屿的最大面积”是在网格上进行DFS或BFS，并累加连通分量的大小。掌握遍历的核心框架后，应学会识别问题本质，并通过添加计数、记录路径、修改访问逻辑等方式进行适配。

小结

本章系统性地讲解了图论算法的基础核心：邻接表与邻接矩阵为图提供了两种互补的表示方法，是算法实现的物理基础；深度优先遍历和广度优先遍历是探索图结构的两种基本策略，构成了众多高级算法的骨架；拓扑排序作为有向无环图的重要应用，其Kahn算法和DFS方法分别从入度管理和后序遍历的角度提供了解决方案。通过“课程表”等例题的实战，我们巩固了从图构建、遍历到结果判定的完整思维链条。掌握这些基础，是进一步攻克最短路径、最小生成树、网络流等复杂图论问题的必经之路。

下一节：高级数据结构与算法