图的邻接表拓扑排序方法

概述

在图论中，拓扑排序是一种线性排序算法，适用于有向无环图（DAG）。它是将一个有向无环图中的顶点排成一个线性的序列的过程。拓扑排序的结果是唯一的当且仅当该图的每个非源节点都具有恰好一个前驱节点和至少一个后继节点。

邻接表表示

在邻接表中，每条边用一个链表来存储，顶点通过指向其邻居的指针进行连接。这种方式常用于稀疏图的存储，能有效节省空间。

假设我们有如下有向无环图（DAG）：

A -> B
A -> C
B -> D
C -> D

表示为邻接表的形式如下：

• A: [B, C]
• B: [D]
• C: [D]

拓扑排序算法

拓扑排序可以通过深度优先搜索（DFS）或广度优先搜索（BFS）来实现。这里以DFS为例，通过递归方式完成。

算法步骤

1. 初始化入度表：首先计算每个节点的入度。
2. 建立邻接表结构：将图表示为邻接表形式。
3. 选择一个入度为0的节点开始：将该节点加入拓扑排序序列中，将其从邻接表和入度表中移除。
4. 递归处理它的邻居节点：对于每个未被访问过的邻居节点，减少其入度。如果某个邻居节点的入度变为0，则重复步骤3。

实现代码

以下是使用Python实现的拓扑排序方法：

from collections import defaultdict, deque

def topological_sort(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, degree in in_degree.items() if degree == 0])
    
    # 结果列表用来存储拓扑排序后的节点
    sorted_order = []
    
    # 当队列不为空时，执行循环
    while queue:
        vertex = queue.popleft()
        sorted_order.append(vertex)
        
        for child in graph[vertex]:
            in_degree[child] -= 1
            if in_degree[child] == 0:
                queue.append(child)
                
    return sorted_order

# 示例图的邻接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

print(topological_sort(graph))  # 输出: ['A', 'B', 'C', 'D']

算法复杂度

• 时间复杂度：O(V + E)，其中 V 是图中的顶点数，E 是边数。因为我们需要遍历所有节点和边。
• 空间复杂度：O(V)，需要存储入度表以及队列。

结语

通过上述方法，我们可以有效地对有向无环图进行拓扑排序。这种方法在处理具有依赖关系的任务调度、死锁检测等领域有着广泛的应用。