利用 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)

相关问题

有向无环图输出拓扑排序

### 有向无环图 (DAG) 的拓扑排序算法

#### Kahn 算法
Kahn 算法通过不断移除入度为 0 的节点来实现排序。具体来说，该算法会初始化一个队列，将所有入度为 0 的节点加入其中。每次从队列中取出一个节点并将其添加到结果列表中，随后减少其邻接节点的入度；如果某个邻接节点的入度变为 0，则将其加入队列。重复此过程直到队列为空。最终的结果列表即为拓扑排序后的节点序列[^1]。

from collections import deque, defaultdict

def topological_sort_kahn(graph):
    indegree = {node: 0 for node in graph}
    for nodes in graph.values():
        for node in nodes:
            indegree[node] += 1
    
    queue = deque([node for node in indegree if indegree[node] == 0])
    topo_order = []

    while queue:
        current_node = queue.popleft()
        topo_order.append(current_node)

        for neighbor in graph[current_node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(topo_order) != len(indegree):  # 如果存在环路
        raise ValueError("Graph has at least one cycle.")
    
    return topo_order

#### 深度优先搜索 (DFS) 方法
另一种常见的拓扑排序方法是基于 DFS 实现。这种方法利用递归回溯的特点，在访问完某节点及其子树之后再将当前节点压栈。这样可以保证对于每条边 \( u \rightarrow v \)，\( u \) 总是在 \( v \) 后面被处理完毕从而进入栈底位置。最后返回逆序排列即可得到完整的拓扑顺序。

def dfs_util(node, visited, stack, adj_list):
    visited.add(node)
    for neighbour in adj_list.get(node, []):
        if neighbour not in visited:
            dfs_util(neighbour, visited, stack, adj_list)
    stack.insert(0, node)


def topological_sort_dfs(adj_list):
    visited = set()
    stack = []
    for key in list(adj_list.keys()):
        if key not in visited:
            dfs_util(key, visited, stack, adj_list)
            
    return stack[::-1]

这两种方法都能够有效检测图中存在的任何环，并生成合法有效的拓扑排序方案。

DFS算法实现拓扑排序C++

### 使用 C++ 实现基于 DFS 的拓扑排序

为了实现基于深度优先搜索 (DFS) 的拓扑排序，在有向无环图 (DAG) 中，可以采用以下方法：

#### 函数定义与初始化
首先，定义必要的数据结构来表示图以及辅助函数来进行深度优先遍历。

#include <iostream>
#include <list>
#include <stack>
using namespace std;

class Graph {
    int V; // 节点数量
    list<int> *adj; // 邻接表数组
public:
    Graph(int V); // 构造函数
    void addEdge(int v, int w);
    void topologicalSort();
private:
    void DFSUtil(int v, bool visited[], stack<int>& Stack);
};

此部分代码创建了一个 `Graph` 类用来存储顶点数目和邻接列表，并提供了添加边的方法[^1]。

#### 添加边到图中
接着是具体操作——往图里加入一条新的连接线（即边）:

void Graph::addEdge(int v, int w){
    adj[v].push_back(w); // 将w加到v的链表中
}

这段程序片段展示了如何利用成员变量 `adj` 来记录两个节点之间的关联关系。

#### 执行深度优先搜索并构建栈
核心逻辑在于执行一次完整的深度优先遍历过程，同时维护一个堆栈用于保存访问顺序的结果：

void Graph::DFSUtil(int v, bool visited[], stack<int>& Stack){
    // 把当前结点标记为已访问过
    visited[v] = true;
    
    // 对于所有相邻未被访问过的邻居做递归调用
    list<int>::iterator i;
    for(i=adj[v].begin();i!=adj[v].end();++i)
        if(!visited[*i])
            DFSUtil(*i, visited, Stack);

    // 当前结点处理完毕后压入栈内
    Stack.push(v);
}

这里实现了对给定起点及其可达区域内的每一个尚未探索过的子树进行深入挖掘的过程；一旦某个分支走到了尽头，则立即将该位置的信息存放到全局使用的 LIFO 结构之中等待后续输出。

#### 完成整个流程控制
最后一步就是把上述各个组件串联起来形成一套完整的解决方案：

// 主要接口：完成拓扑排序工作
void Graph::topologicalSort(){
    stack<int> Stack;
  
    // 设置全部顶点初始状态均为'未访问'
    bool* visited = new bool[V];
    for(int i = 0;i<V;++i)
        visited[i]=false;

    // 反复挑选那些还没有参与计算的新起始点继续深挖下去直到没有剩余为止
    for(int i = 0 ; i< V ; ++i )
      if( !visited[i] )
          DFSUtil(i , visited , Stack );

    // 输出最终得到的排列情况
    while(Stack.empty()==false){
       cout << Stack.top() << " ";
       Stack.pop();
    }
}

// 测试案例
int main(){
    // 创建测试用例中的简单图形实例对象
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    cout << "Following is a Topological Sort of the given graph \n";
    // 显示结果
    g.topologicalSort();

    return 0;
}

以上便是完整的基于 DFS 的拓扑排序算法实现。通过这种方式可以在 O(V+E) 时间复杂度下有效地解决大多数实际应用场景下的需求。