C ++程序应用DFS对有向无环图进行拓扑排序
DAG（有向无环图）的拓扑排序是顶点的线性排序，这样对于每个有向边uv，在此排序中，顶点u在v之前。如果该图不是DAG，则无法对图进行拓扑排序。
函数和伪代码
Begin function topologicalSort(): a) Mark the current node as visited. b) 为与该顶点相邻的所有顶点递归。 c) Push current vertex to stack which stores result. End Begin function topoSort() which uses recursive topological sort() function: a) 标记所有未访问的顶点。 b) Call the function topologicalSort(). c) Print the content. End
示例
#include<iostream>
#include <list>
#include <stack>
using namespace std;
class G {
int n;
list<int> *adj;
//功能声明
void topologicalSort(int v, bool visited[], stack<int> &Stack);
public:
G(int n); //constructor
void addEd(int v, int w);
void topoSort();
};
G::G(int n) {
this->n = n;
adj = new list<int> [n];
}
void G::addEd(int v, int w) // add the edges to the graph. {
adj[v].push_back(w); //add w to v’s list
}
void G::topologicalSort(int v, bool visited[], stack<int> &Stack) {
visited[v] = true; //mark current node as visited
list<int>::iterator i;
//为与该顶点相邻的所有顶点递归。
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSort(*i, visited, Stack);
Stack.push(v);
}
void G::topoSort() {
stack<int> Stack;
bool *visited = new bool[n];
//标记所有未访问的顶点。
for (int i = 0; i < n; i++)
visited[i] = false;
for (int i = 0; i < n; i++)
if (visited[i] == false)
//Call the function topologicalSort().
topologicalSort(i, visited, Stack);
while (Stack.empty() == false) {
cout << Stack.top() << " "; //print the element
Stack.pop();
}
}
int main() {
G g(6);
g.addEd(4, 2);
g.addEd(5, 1);
g.addEd(4, 0);
g.addEd(3, 1);
g.addEd(1, 3);
g.addEd(3, 2);
cout << " Topological Sort of the given graph \n";
g.topoSort();
return 0;
}输出结果
Topological Sort of the given graph 5 4 1 3 2 0