有向无环图的拓扑排序

有向无环图的拓扑排序是一种对图中节点进行排序的算法，其中节点的顺序满足图中所有有向边的方向关系。

拓扑排序的步骤如下：
1. 初始化一个空的结果列表，用于存储排序后的节点。
2. 找到入度为 0 的节点（即没有指向它的边），将其加入结果列表中。
3. 删除该节点及其出边，更新剩余节点的入度。
4. 重复步骤 2 和步骤 3，直到所有节点都被处理。
5. 如果结果列表中的节点数少于图中的节点数，说明图中存在环，无法进行拓扑排序。

拓扑排序可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来实现。使用DFS实现时，可以通过递归或栈来进行节点的遍历和处理。使用BFS实现时，可以使用队列来进行节点的遍历和处理。

需要注意的是，有向无环图才能进行拓扑排序，如果图中存在环，则无法得到有效的排序结果。

相关问题

有向无环图 拓扑排序

拓扑排序是对有向无环图（DAG）中的节点进行排序的一种算法。它的目的是使得图中的每条有向边从排在前面的节点指向排在后面的节点。

拓扑排序的实现步骤如下：
1. 初始化一个队列，用于存储入度为0的节点。
2. 遍历图中的所有节点，计算每个节点的入度（即有多少条边指向该节点），并将入度为0的节点加入队列。
3. 从队列中取出一个节点，将其加入排序结果中，并将该节点指向的所有节点的入度减1。
4. 如果被减去入度后某个节点的入度变为0，则将该节点加入队列。
5. 重复步骤3和步骤4，直到队列为空。
6. 如果排序结果中的节点数量等于图中的节点数量，则说明拓扑排序成功；否则，说明图中存在环，无法进行拓扑排序。

拓扑排序可以用来解决一些问题，例如任务调度、编译顺序等，其中要求任务之间存在一定的依赖关系，并且不能形成循环依赖。

利用 DFS 实现有向无环图拓扑排序

利用 DFS 实现有向无环图拓扑排序的步骤如下：
1. 对于有向无环图中的每个顶点，进行 DFS 遍历。
2. 在 DFS 遍历的过程中，对每个顶点进行标记，标记其是否被访问过。
3. 在 DFS 遍历的过程中，对每个顶点进行标记，标记其结束时间。
4. 根据每个顶点的结束时间，进行排序，得到拓扑排序。

以下是具体的实现代码：

visited = [False] * MAX_SIZE
finishTime = [0] * MAX_SIZE
result = []

def topologicalSortDFS(G):
    for v in range(G.vexNum):
        visited[v] = False
    time = 0
    for v in range(G.vexNum):
        if not visited[v]:
            DFS(G, v)
    result.reverse()
    return result

def DFS(G, v):
    visited[v] = True
    for w in range(G.vexNum):
        if G.arc[v][w] != 0 and not visited[w]:
            DFS(G, w)
    global time
    time += 1
    finishTime[v] = time
    result.append(v)