数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 程序使用深度优先搜索针对有向无环图执行拓扑排序
有向无环图 (DAG) 的拓扑排序是一种线性的顶点排序，其中对于每个有向边 uv，其中顶点 u 在排序中在 v 之前。如果该图不是 DAG，则无法针对该图进行拓扑排序。
函数和伪代码
Begin function topologicalSort(): a) Mark the current node as visited. b) Recur for all the vertices adjacent to this vertex. c) Push current vertex to stack which stores result. End Begin function topoSort() which uses recursive topological sort() function: a) Mark all the vertices which are not visited. 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;
//declaration of functions
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;
//Recur for all the vertices adjacent to this vertex.
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];
//Mark all the vertices which are not visited.
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
更新时间：2019 年 7 月 30 日
1,000+ 浏览
广告