資料結構
網路
關係型資料庫管理系統
作業系統
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+ 瀏覽
廣告