### 实现拓扑排序 #### 使用C++实现拓扑排序 通过深度优先搜索(DFS)，可以有效地完成有向无环图(DAG)的拓扑排序。下面是一个基于此方法的C++程序示例： ```cpp #include <iostream> #include <list> #include <stack> using namespace std; class Graph { int V; list<int> *adj; void topologicalSortUtil(int v, bool visited[], stack<int> &Stack); public: Graph(int V); void addEdge(int v, int w); void topologicalSort(); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); } void Graph::topologicalSortUtil(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]) topologicalSortUtil(*i, visited, Stack); Stack.push(v); } 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] == false) topologicalSortUtil(i, visited, Stack); while (Stack.empty() == false) { cout << Stack.top() << " "; Stack.pop(); } } ``` 上述代码定义了一个`Graph`类来表示图结构并实现了拓扑排序算法[^1]。 #### 使用Python实现拓扑排序 同样地，在Python中也可以利用类似的逻辑来进行拓扑排序，这里提供了一种更简洁的方式： ```python from collections import defaultdict class Graph: def __init__(self, vertices): self.graph = defaultdict(list) self.V = vertices def addEdge(self, u, v): self.graph[u].append(v) def topologicalSortUtil(self,v,visited,stack): visited[v] = True for i in self.graph[v]: if visited[i] == False: self.topologicalSortUtil(i, visited, stack) stack.insert(0, v) def topologicalSort(self): visited = [False]*self.V stack =[] for i in range(self.V): if visited[i] == False: self.topologicalSortUtil(i, visited, stack) print(stack) g= Graph(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); print ("Following is a Topological Sort of the given graph") g.topologicalSort() ``` 这段Python脚本创建了一个名为`Graph`的类用于构建图形对象，并提供了添加边的方法以及执行拓扑排序的功能[^2]。