LeetCode 拓扑排序题解

LeetCode 拓扑排序题解

题目描述

拓扑排序是一种对有向无环图（DAG）的顶点进行排序的算法，使得对于每条有向边 (u, v)，顶点 u 在排序结果中都出现在顶点 v 之前。

示例：

对于以下有向无环图：

A → B → C | ↑ ↓ | D → E → F

一个可能的拓扑排序结果是：A → D → B → E → F → C。

解题思路

方法：Kahn 算法（基于入度的拓扑排序）

思路：

• Kahn 算法的核心思想是通过维护每个顶点的入度，逐步将入度为 0 的顶点加入拓扑排序结果。
• 具体步骤：
  1. 计算每个顶点的入度。
  2. 将所有入度为 0 的顶点加入队列。
  3. 当队列不为空时：
     • 取出队首顶点，将其加入拓扑排序结果。
     • 遍历该顶点的所有邻接顶点，将它们的入度减 1。
     • 如果邻接顶点的入度变为 0，则将其加入队列。
  4. 如果最终拓扑排序结果的长度等于顶点数，则说明图是有向无环图，否则存在环。

复杂度分析：

• 时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数。每个顶点和边都会被处理一次。
• 空间复杂度：O(V + E)，需要存储图的邻接表和入度数组。

代码实现

方法：Kahn 算法

from collections import deque # 拓扑排序（Kahn 算法） def topological_sort_kahn(graph): # 计算每个顶点的入度 in_degree = {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: in_degree[neighbor] += 1 # 将所有入度为 0 的顶点加入队列 queue = deque([node for node in graph if in_degree[node] == 0]) # 拓扑排序结果 result = [] while queue: # 取出队首顶点 node = queue.popleft() # 将其加入拓扑排序结果 result.append(node) # 遍历该顶点的所有邻接顶点 for neighbor in graph[node]: # 将邻接顶点的入度减 1 in_degree[neighbor] -= 1 # 如果邻接顶点的入度变为 0，则将其加入队列 if in_degree[neighbor] == 0: queue.append(neighbor) # 检查是否存在环 if len(result) != len(graph): return None # 存在环 return result # 测试 def test_topological_sort_kahn(): # 构建图结构（邻接表） graph = { 'A': ['B', 'D'], 'B': ['C'], 'C': [], 'D': ['E'], 'E': ['B', 'F'], 'F': ['C'] } # 测试拓扑排序 print("Topological sort result:") result = topological_sort_kahn(graph) if result: print(' → '.join(result)) # 可能的输出：A → D → E → B → F → C else: print("The graph contains a cycle.") if __name__ == "__main__": test_topological_sort_kahn()

方法：深度优先搜索（DFS）

# 拓扑排序（DFS 方法） def topological_sort_dfs(graph): # 标记顶点的状态：0-未访问，1-正在访问，2-已访问 visited = {node: 0 for node in graph} # 拓扑排序结果（逆序） result = [] # 是否存在环 has_cycle = False def dfs(node): nonlocal has_cycle # 标记为正在访问 visited[node] = 1 # 遍历邻接顶点 for neighbor in graph[node]: if visited[neighbor] == 0: # 递归访问邻接顶点 dfs(neighbor) if has_cycle: return elif visited[neighbor] == 1: # 发现环 has_cycle = True return # 标记为已访问 visited[node] = 2 # 将顶点加入结果 result.append(node) # 对每个未访问的顶点进行 DFS for node in graph: if visited[node] == 0: dfs(node) if has_cycle: return None # 反转结果，得到拓扑排序 result.reverse() return result # 测试 def test_topological_sort_dfs(): # 构建图结构（邻接表） graph = { 'A': ['B', 'D'], 'B': ['C'], 'C': [], 'D': ['E'], 'E': ['B', 'F'], 'F': ['C'] } # 测试拓扑排序 print("Topological sort result (DFS):") result = topological_sort_dfs(graph) if result: print(' → '.join(result)) # 可能的输出：A → D → E → B → F → C else: print("The graph contains a cycle.") if __name__ == "__main__": test_topological_sort_dfs()

测试用例

测试用例：拓扑排序

输入：

A → B → C | ↑ ↓ | D → E → F

输出：

Topological sort result: A → D → E → B → F → C

总结

拓扑排序是一种重要的图论算法，它可以用于对有向无环图（DAG）的顶点进行排序，使得对于每条有向边 (u, v)，顶点 u 在排序结果中都出现在顶点 v 之前。

拓扑排序的核心思想是：通过维护每个顶点的入度（Kahn 算法）或通过深度优先搜索（DFS 方法），逐步将顶点加入拓扑排序结果。

掌握拓扑排序的原理和实现，对于理解和解决图论相关问题非常重要。