有向无环图 拓扑排序

拓扑排序是对有向无环图（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)

dfs算法实现有向无环图拓扑排序

DFS（深度优先搜索）可以用于有向无环图（DAG，Directed Acyclic Graph）的拓扑排序。拓扑排序是一种将图中顶点按照它们的依赖关系线性排列的方式，对于DAG来说，这样的排序总是存在的。以下是使用DFS实现拓扑排序的基本步骤：

1. **选择源节点**：DAG中通常有一个入度为0的节点（称为源节点），作为起始进行排序。

2. **标记并访问**：对选定的源节点进行标记（通常设为已访问），然后递归地遍历其所有未访问的相邻节点（前驱节点）。

3. **递归遍历**：对每个相邻节点重复步骤2，直到所有可达的节点都被访问过。

4. **记录路径**：在访问过程中，每访问一个节点，就将其加入到排序结果序列的末尾。

5. **回溯处理**：当所有节点都完成访问后，如果还有剩余节点未被添加到排序序列，说明当前图中存在循环，这意味着不可能完成拓扑排序，此时需要检查图是否存在问题。

6. **返回结果**：如果没有发现循环，最终得到的序列就是DAG的一个合法拓扑排序。

需要注意的是，由于DFS的特性，在处理有向图时可能存在多个合法的拓扑排序顺序。同时，如果图中存在负权边，可能需要借助其他算法如Kahn’s Algorithm来进行排序。