# 拓扑排序算法

# 概述

拓扑排序是一种用于有向无环图（DAG）的算法，它将图中的所有顶点排序，使得所有的有向边都从排序靠前的顶点指向排序靠后的顶点。本文介绍两种实现拓扑排序的方法：Kahn算法和DFS算法。

# Kahn算法

# 算法原理

Kahn算法基于顶点的入度，每次选择入度为0的顶点，将其加入结果序列，并移除其相关的边。

# 算法步骤

计算图中每个顶点的入度
将所有入度为0的顶点加入队列
每次从队列取出一个顶点，将其加入结果序列
移除该顶点的所有出边，更新相邻顶点的入度
重复步骤3-4直到队列为空

# 复杂度分析

时间复杂度：O(V + E)，其中V是顶点数，E是边数
空间复杂度：O(V)

# 代码实现

from collections import deque

def kahn_topological_sort(graph):
    n = len(graph)
    indegree = [0] * n
    
    # 计算入度
    for i in range(n):
        for j in range(n):
            if graph[i][j]:
                indegree[j] += 1
    
    # 初始化队列
    queue = deque()
    for i in range(n):
        if indegree[i] == 0:
            queue.append(i)
    
    result = []
    while queue:
        u = queue.popleft()
        result.append(u)
        
        # 移除出边
        for v in range(n):
            if graph[u][v]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)
    
    # 检查是否存在环
    return result if len(result) == n else []

# 示例

# 示例：课程依赖关系
# 0: 数据结构, 1: 算法设计, 2: 计算机网络, 3: 操作系统
graph = [
    [0, 1, 0, 0],  # 数据结构 -> 算法设计
    [0, 0, 0, 1],  # 算法设计 -> 操作系统
    [0, 0, 0, 1],  # 计算机网络 -> 操作系统
    [0, 0, 0, 0]   # 操作系统没有后续课程
]

result = kahn_topological_sort(graph)
print("课程学习顺序:", result)  # 输出: [0, 2, 1, 3] 或 [2, 0, 1, 3]

# 可视化演示

比较次数: 0

已访问节点:

# DFS算法

# 算法原理

DFS算法通过深度优先搜索，在回溯时将顶点加入结果序列的开头，最终得到拓扑排序。

# 算法步骤

对图中未访问的顶点进行DFS
在DFS回溯时，将顶点加入结果序列的开头
检查是否存在环（通过检测后向边）

# 复杂度分析

时间复杂度：O(V + E)
空间复杂度：O(V)

# 代码实现

def dfs_topological_sort(graph):
    n = len(graph)
    visited = [0] * n  # 0: 未访问, 1: 访问中, 2: 已完成
    result = []
    
    def dfs(u):
        if visited[u] == 1:  # 检测到环
            return False
        if visited[u] == 2:  # 已处理
            return True
        
        visited[u] = 1  # 标记为访问中
        
        # 访问邻接顶点
        for v in range(n):
            if graph[u][v]:
                if not dfs(v):
                    return False
        
        visited[u] = 2  # 标记为已完成
        result.insert(0, u)  # 加入结果序列开头
        return True
    
    # 对所有未访问的顶点进行DFS
    for u in range(n):
        if visited[u] == 0:
            if not dfs(u):
                return []  # 存在环
    
    return result

# 示例

# 示例：项目依赖关系
# 0: 基础库, 1: 核心模块, 2: UI组件, 3: 应用程序
graph = [
    [0, 1, 1, 0],  # 基础库 -> 核心模块, UI组件
    [0, 0, 0, 1],  # 核心模块 -> 应用程序
    [0, 0, 0, 1],  # UI组件 -> 应用程序
    [0, 0, 0, 0]   # 应用程序是最终产品
]

result = dfs_topological_sort(graph)
print("项目构建顺序:", result)  # 输出: [0, 2, 1, 3] 或 [0, 1, 2, 3]

# 可视化演示

比较次数: 0

已访问节点:

# 应用场景

任务调度
课程安排
编译依赖分析
项目管理中的依赖关系处理

# 算法比较

算法	优点	缺点	时间复杂度
Kahn	实现简单，易于理解	需要额外空间存储入度	O(V + E)
DFS	空间效率高	递归实现，栈溢出风险	O(V + E)

← 最小生成树算法