第 41 课 - 拓扑排序

学习目标

完成本课后，你将能够：

理解拓扑排序的定义及其在有向无环图（DAG）中的应用。
解释Kahn算法（基于入度的BFS方法）的核心思想与步骤。
使用Kahn算法实现拓扑排序。
识别并处理图中存在环的情况，以正确进行拓扑排序。

核心概念

什么是拓扑排序？ 想象一下，你在规划一个学习计划，但有些课程必须先修其他课程。比如，学“数据结构”之前要先学“程序设计基础”，学“算法”之前要先学“数据结构”。这些课程之间的依赖关系可以构成一个有向无环图。 拓扑排序就是将图中所有顶点排成一个线性序列，使得对于图中任意一条有向边 (u, v)，u 在序列中都出现在 v 的前面。简单说，就是把“顺序”给理清楚。

前提：图必须是有向无环图。如果有环（比如A依赖B，B又依赖A），则无法进行拓扑排序。
结果不唯一：一个图的拓扑排序结果可能不止一种。

Kahn 算法 (基于入度的BFS) 这是实现拓扑排序最直观、最常用的方法。它的核心思想是：不断从图中移除入度为0的顶点。

入度：指向某个顶点的边的数量。
算法步骤：
1. 计算图中所有顶点的入度。
2. 找出所有入度为0的顶点，将它们放入一个队列（或列表）中。
3. 从队列中取出一个顶点 u，将其加入拓扑排序的结果列表。
4. 遍历 u 的所有邻接点 v，将 v 的入度减1（相当于“删除”了从 u 到 v 的边）。
5. 如果 v 的入度变为0，则将其加入队列。
6. 重复步骤3-5，直到队列为空。
7. 最后，检查结果列表的长度是否等于图中顶点的数量。如果相等，排序成功；否则，说明图中存在环。

代码示例

下面是一个完整的、使用 Kahn 算法进行拓扑排序的 Python 示例，并包含环检测。

from collections import deque, defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)  # 邻接表
        self.V = vertices  # 顶点总数
        self.in_degree = [0] * self.V  # 存储每个顶点的入度

    def add_edge(self, u, v):
        """添加一条从u指向v的有向边"""
        self.graph[u].append(v)
        self.in_degree[v] += 1  # v的入度加1

    def topological_sort_kahn(self):
        """使用Kahn算法进行拓扑排序"""
        # 1. 将所有入度为0的顶点加入队列
        queue = deque()
        for i in range(self.V):
            if self.in_degree[i] == 0:
                queue.append(i)

        topo_order = []  # 存储拓扑排序结果
        visited_count = 0  # 记录已处理的顶点数

        # 2. 处理队列中的顶点
        while queue:
            # 取出一个入度为0的顶点
            u = queue.popleft()
            topo_order.append(u)
            visited_count += 1

            # 3. 遍历u的所有邻接点，将其入度减1
            for v in self.graph[u]:
                self.in_degree[v] -= 1
                # 如果邻接点的入度变为0，则加入队列
                if self.in_degree[v] == 0:
                    queue.append(v)

        # 4. 检测环：如果所有顶点都被访问，则无环
        if visited_count == self.V:
            return topo_order
        else:
            print("图中存在环，无法进行拓扑排序！")
            return []

# 创建一个示例图并测试
# 图结构: 0->1, 0->2, 1->3, 2->3
# 期望拓扑序: [0, 1, 2, 3] 或 [0, 2, 1, 3]
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)

result = g.topological_sort_kahn()
print("拓扑排序结果:", result)

# 测试一个有环的图
# 图结构: 0->1, 1->2, 2->0 (形成环)
g_with_cycle = Graph(3)
g_with_cycle.add_edge(0, 1)
g_with_cycle.add_edge(1, 2)
g_with_cycle.add_edge(2, 0)  # 创建环
result_with_cycle = g_with_cycle.topological_sort_kahn()
print("有环图的排序结果:", result_with_cycle)

代码输出示例：

拓扑排序结果: [0, 1, 2, 3]
图中存在环，无法进行拓扑排序！
有环图的排序结果: []

实践练习

练习1（基础）：手动排序 给定以下课程依赖关系：[("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]。

画出对应的有向图。
写出至少两种不同的合法拓扑排序序列。

练习2（编码 - 环检测）： 修改上面的代码，在检测到环时，不仅打印消息，还要尝试输出环中的一个顶点（提示：可以在BFS结束后，检查哪些顶点的入度仍然大于0）。

练习3（应用）： 假设你要规划一个包含以下任务的项目：需求分析(R)、设计(D)、编码(C)、测试(T)、部署(P)。依赖关系是：R->D, R->C, D->C, C->T, T->P, D->P。

使用Kahn算法计算任务的执行顺序。
思考：如果“设计(D)”和“测试(T)”之间新增了一个依赖 T->D，排序结果会怎样变化？这合理吗？

常见错误

忽略环检测：实现算法时，只输出排序序列而不检查结果长度，导致在有环的图上输出一个不完整的、错误的序列。
混淆入度与出度：在计算初始入度或更新邻接点入度时出错。牢记：入度是“指向自己的边”，在添加边 (u, v) 时，是 v 的入度增加。
队列/栈选择错误：Kahn算法本质上是一种广度优先搜索，通常使用队列。如果错误地使用栈（深度优先），虽然也能得到一个合法序列，但逻辑和实现上与算法描述不符。
图表示错误：使用邻接矩阵时，对不存在的边没有正确处理，导致计算入度时出错。

小结

本节课，我们学习了处理有向无环图依赖关系的强大工具——拓扑排序。关键要点包括：

定义：拓扑排序是将DAG的顶点排成线性序列，使得所有边的方向都从序列前面的顶点指向后面的顶点。
Kahn算法：其核心是反复取出并删除入度为0的顶点。这是一种基于BFS的、直观高效的算法。
环检测：算法结束时，如果已排序的顶点数少于总顶点数，则图中必然存在环。
时间复杂度：Kahn算法的时间复杂度为 O(V+E)，其中V是顶点数，E是边数，与BFS相同。拓扑排序在编译顺序、任务调度、课程规划等场景中有广泛应用。理解它将为你解决更复杂的图论问题打下坚实基础。

练习编辑器

rust