\title{"理解并实现基本的拓扑排序算法"}
\author{"杨其臻"}
\date{"Apr 02, 2025"}
\maketitle
在计算机科学中，拓扑排序是一种解决依赖关系问题的关键算法。想象这样一个场景：大学选课时，某些课程需要先修课程。例如，学习「数据结构」前必须先修「程序设计基础」，这种依赖关系构成一个有向无环图（DAG）。拓扑排序的作用正是为这类依赖关系找到一种合理的执行顺序。本文将深入解析拓扑排序的核心原理，并通过 Python 代码实现两种经典算法。\par
\chapter{拓扑排序基础概念}
拓扑排序的定义是：对 DAG 的顶点进行线性排序，使得对于任意有向边 $u \to v$，顶点 $u$ 在排序中都出现在顶点 $v$ 之前。例如，若图中存在边 $A \to B$ 和 $B \to C$，则可能的排序之一是 $[A, B, C]$。\par
拓扑排序有两个关键特性：\par
\begin{itemize}
\item \textbf{无环性}：若图中存在环（例如 $A \to B \to C \to A$），则无法进行拓扑排序。可通过深度优先搜索（DFS）检测环的存在。
\item \textbf{不唯一性}：同一 DAG 可能有多种有效排序。例如，若图中有两个无依赖关系的节点 $A$ 和 $B$，则 $[A, B]$ 和 $[B, A]$ 均为合法结果。
\end{itemize}
\chapter{拓扑排序算法原理}
\section{Kahn 算法（基于入度）}
Kahn 算法的核心思想是不断移除入度为 0 的节点，直到所有节点被处理。具体步骤如下：\par
\begin{itemize}
\item 初始化所有节点的入度表。
\item 将入度为 0 的节点加入队列。
\item 依次处理队列中的节点，将其邻接节点的入度减 1。若邻接节点入度变为 0，则加入队列。
\item 若最终处理的节点数等于总节点数，则排序成功；否则说明图中存在环。
\end{itemize}
该算法依赖队列数据结构，时间复杂度为 $O(V + E)$，其中 $V$ 是节点数，$E$ 是边数。\par
\section{DFS 后序遍历法}
DFS 算法通过深度优先遍历图，并按递归完成时间的逆序得到拓扑排序。具体步骤如下：\par
\begin{itemize}
\item 从任意未访问节点开始递归 DFS。
\item 将当前节点标记为已访问。
\item 递归处理所有邻接节点。
\item 递归结束后将当前节点压入栈中。
\item 最终栈顶到栈底的顺序即为拓扑排序结果。
\end{itemize}
DFS 算法同样具有 $O(V + E)$ 的时间复杂度，但需要额外的栈空间存储结果。\par
\section{算法对比}
\begin{enumerate}
\item \textbf{Kahn 算法}：显式利用入度信息，适合动态调整入度的场景（如动态图）。
\item \textbf{DFS 算法}：代码简洁，但难以处理动态变化的图。
\end{enumerate}
\chapter{代码实现（以 Python 为例）}
\section{图的表示}
使用邻接表表示图，例如节点 0 的邻接节点为 [1, 2]：\par
\begin{lstlisting}[language=python]
graph = {
    0: [1, 2],
    1: [3],
    2: [3],
    3: []
}
\end{lstlisting}
\section{Kahn 算法实现}
\begin{lstlisting}[language=python]
from collections import deque

def topological_sort_kahn(graph, n):
    # 初始化入度表
    in_degree = {i: 0 for i in range(n)}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    # 将入度为 0 的节点加入队列
    queue = deque([u for u in in_degree if in_degree[u] == 0])
    result = []

    while queue:
        u = queue.popleft()
        result.append(u)
        # 更新邻接节点的入度
        for v in graph.get(u, []):
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    # 检查是否存在环
    if len(result) != n:
        return []  # 存在环
    return result
\end{lstlisting}
\textbf{代码解读}：\par
\begin{enumerate}
\item \verb!in_degree! 字典记录每个节点的入度。
\item 队列 \verb!queue! 维护当前入度为 0 的节点。
\item 每次从队列取出节点后，将其邻接节点的入度减 1。若邻接节点入度变为 0，则加入队列。
\item 最终若结果列表长度不等于节点总数，则说明存在环。
\end{enumerate}
\section{DFS 算法实现}
\begin{lstlisting}[language=python]
def topological_sort_dfs(graph):
    visited = set()
    stack = []

    def dfs(u):
        if u in visited:
            return
        visited.add(u)
        # 递归访问所有邻接节点
        for v in graph.get(u, []):
            dfs(v)
        # 递归结束后压入栈
        stack.append(u)

    for u in graph:
        if u not in visited:
            dfs(u)
    # 逆序输出栈
    return stack[::-1]
\end{lstlisting}
\textbf{代码解读}：\par
\begin{enumerate}
\item \verb!visited! 集合记录已访问的节点。
\item \verb!dfs! 函数递归访问邻接节点，完成后将当前节点压入栈。
\item 最终栈的逆序即为拓扑排序结果（后进先出的栈结构需要反转）。
\end{enumerate}
\chapter{实例演示与测试}
假设有以下 DAG：\par
\begin{lstlisting}
5 → 0 ← 4
↓   ↓   ↓
2 → 3 → 1
\end{lstlisting}
\textbf{手动推导}：可能的拓扑排序为 \verb![5, 4, 2, 0, 3, 1]!。
\textbf{代码测试}：\par
\begin{enumerate}
\item 输入图的邻接表表示：
\end{enumerate}
\begin{lstlisting}[language=python]
graph = {
    5: [0, 2],
    4: [0, 1],
    2: [3],
    0: [3],
    3: [1],
    1: []
}
n = 6
\end{lstlisting}
\begin{enumerate}
\item 运行 \verb!topological_sort_kahn(graph, 6)! 应返回长度为 6 的合法排序。
\item 若图中存在环（例如添加边 \verb!1 → 5!），两种算法均返回空列表。
\end{enumerate}
\chapter{复杂度与优化}
两种算法的时间复杂度均为 $O(V + E)$，空间复杂度为 $O(V)$。
\textbf{优化技巧}：若需要字典序最小的排序，可将 Kahn 算法中的队列替换为优先队列（最小堆）。\par
\chapter{实际应用场景}
\begin{itemize}
\item \textbf{编译器构建}：确定源代码文件的编译顺序。
\item \textbf{课程安排}：解决 LeetCode 210 题「课程表 II」的依赖问题。
\item \textbf{任务调度}：管理具有前后依赖关系的任务执行顺序。
\end{itemize}
拓扑排序是处理依赖关系的核心算法。通过 Kahn 算法和 DFS 算法的对比，可根据实际需求选择实现方式。进一步学习可探索：\par
\begin{enumerate}
\item \textbf{强连通分量}：使用 Tarjan 算法识别图中的环。
\item \textbf{动态拓扑排序}：在频繁增删边的场景下维护排序结果。
\item \textbf{练习题}：LeetCode 207（判断能否完成课程）、310（最小高度树）等。
\end{enumerate}
\chapter{参考资源}
\begin{enumerate}
\item 《算法导论》第 22.4 章「拓扑排序」。
\item VisuAlgo 的可视化工具：https://visualgo.net/zh/graphds
\end{enumerate}
