从零开始学习拓扑排序算法并在Python中实现

拓扑排序是一种在有向无环图（DAG）中对各顶点进行排序的算法，使得对于任意一条有向边$(u,v) ，u$在排序结果中都出现在$v$之前。拓扑排序可以用来确定工程的依赖关系，或者在编译器中确定源文件之间的编译顺序。

在学习拓扑排序算法之前，我们需要了解有向无环图（DAG）的定义。有向无环图是一种有向图，其中不存在从一个顶点出发经过若干个顶点回到自己的环路。

拓扑排序算法的基本思路是通过寻找入度为0的顶点来确定排序的顺序。具体步骤如下：

1. 首先创建一个队列，将所有入度为0的顶点放入队列。

2. 从队列中取出一个顶点进行处理，将其输出并在图中删除这个顶点以及从这个顶点出发的所有边。

3. 更新剩余顶点的入度，如果某个顶点入度为0，则将其放入队列。

4. 重复步骤2和步骤3，直到队列为空。

下面是在Python中实现拓扑排序算法的示例代码：

from collections import deque

def topoSort(graph):
    indegree = [0] * len(graph)  # 存储每个顶点的入度
    queue = deque()  # 创建一个队列用于存储入度为0的顶点

    # 计算每个顶点的入度
    for i in range(len(graph)):
        for j in range(len(graph[i])):
            indegree[graph[i][j]] += 1

    # 将入度为0的顶点放入队列
    for i in range(len(indegree)):
        if indegree[i] == 0:
            queue.append(i)

    # 开始拓扑排序
    while queue:
        vertex = queue.popleft()
        print(vertex)  # 输出顶点
        for i in range(len(graph[vertex])):
            indegree[graph[vertex][i]] -= 1  # 更新剩余顶点的入度
            if indegree[graph[vertex][i]] == 0:
                queue.append(graph[vertex][i])

# 测试拓扑排序算法
graph = [[],[2,3],[4],[5],[5],[]]
topoSort(graph)

在上述示例代码中，我们首先定义了一个有向无环图graph，其中每个元素表示顶点以及顶点指向的其他顶点。然后，我们通过计算每个顶点的入度，构建了一个入度数组indegree，并将入度为0的顶点放入队列。

随后，我们通过遍历队列，每次取出一个顶点，并输出它。然后，我们更新剩余顶点的入度，并将入度为0的顶点放入队列。重复以上步骤，直到队列为空，即完成了拓扑排序。

在这个例子中，输出结果是：0 1 2 3 4 5，表示按顺序排列的顶点。这个顺序是一个满足依赖关系的排序结果。

拓扑排序算法的时间复杂度为O(V + E)，其中V为顶点数，E为边数。