数据结构与算法 头歌 图的拓扑排序算法

数据结构与算法之图的拓扑排序算法

导言

拓扑排序是对有向无环图(Directed Acyclic Graph, DAG)进行排序的一种算法。在实际开发中，拓扑排序算法常用于解决任务调度、编译顺序等问题。本文将介绍拓扑排序算法的实现过程，并帮助初学者理解该算法的原理及代码实现。

拓扑排序流程

以下是拓扑排序算法的流程，用表格展示每个步骤的具体内容。

代码实现

现在，我们来一步步实现拓扑排序算法，并给出相应代码及注释。

from collections import deque

def topological_sort(graph):
    # 初始化
    in_degree = {node: 0 for node in graph}
    adjacency_list = {node: [] for node in graph}
    
    # 构建邻接表
    for node in graph:
        for neighbor in graph[node]:
            adjacency_list[node].append(neighbor)
    
    # 计算入度
    for node in adjacency_list:
        for neighbor in adjacency_list[node]:
            in_degree[neighbor] += 1
    
    # 将入度为0的节点入队
    queue = deque()
    for node in in_degree:
        if in_degree[node] == 0:
            queue.append(node)
    
    # 拓扑排序
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in adjacency_list[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # 判断是否有环
    if len(result) != len(graph):
        raise ValueError("The graph contains cycles.")
    
    return result

以上代码实现了拓扑排序算法，具体步骤如下：

1. 初始化：创建图的邻接表表示adjacency_list，记录每个节点的入度in_degree。
2. 构建邻接表：遍历图的每个节点，将其邻居节点加入邻接表中。
3. 计算入度：遍历邻接表，统计每个节点的入度。
4. 将入度为0的节点入队：遍历入度表，将入度为0的节点加入队列中。
5. 拓扑排序：从队列中取出一个节点，输出该节点；然后更新其相邻节点的入度，若入度减为0，则加入队列中。
6. 判断是否有环：若队列为空，但还有未输出的节点，则表示图中存在环。

注意事项：上述代码中，我们使用了deque来实现队列数据结构。可以通过pip install collections来安装collections库。

使用示例

现在，我们来演示一下使用上述代码进行拓扑排序的示例。假设我们有以下有向图：

graph = {
    'A': ['C', 'D'],
    'B': ['D'],
    'C': ['E'],
    'D': ['E', 'F'],
    'E': ['F'],
    'F': []
}

我们将使用topological_sort(graph)函数对该图进行拓扑排序操作，代码如下：

graph = {
    'A': ['C', 'D'],
    'B': ['D'],
    'C': ['E'],
    'D': ['E', 'F'],
    'E': ['F'],
    'F': []
}

try:
    result = topological_sort(graph)
    print("拓扑排序结果：", result)
except ValueError as