資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 程式檢查有向圖中是否可以進行拓撲排序
在有向無環圖中，我們可以使用拓撲排序以線性順序對頂點進行排序。
拓撲排序僅適用於有向無環圖。在有向無環圖 (DAG) 中，拓撲排序可以有多個。
在以下 C++ 程式中，我們執行拓撲排序以檢查圖中是否存在迴路。
演算法
對於函式 Topo_Sort
Begin Define function Topo_Sort() Declare x to the integer datatype, vstd[] of the Boolean array and Stack as a stack. Pass them as parameter. Initialize vstd[x] = true to mark the current node as vstd. Declare an iterator i. for (i = a[x].begin(); i != a[x].end(); ++i) if (!vstd[*i]) then Call Topo_Sort(*i, vstd, Stack) function. Call push() function to insert values into stack. End.
例子
#include<iostream>
#include <list>
#include <stack>
using namespace std;
class grph { // Class to represent a graph
int ver;
list<int> *a; // Pointer to an array containing adjacency listsList
void Topo_Sort(int x, bool vstd[], stack<int> &Stack); // A function used by TopologicalSort
public:
grph(int ver); // Constructor of grpf
void Insert_Edge(int x, int y); // to insert an edge to graph
void Topol_Sort(); // prints a Topological Sort of the complete graph
};
grph::grph(int ver) {
this->ver = ver;
a = new list<int>[ver];
}
void grph::Insert_Edge(int x, int y) {
a[x].push_back(y); // Add y to x’s list.
}
// A recursive function used by Topol_Sort
void grph::Topo_Sort(int x, bool vstd[], stack<int> &Stack) {
vstd[x] = true; // Mark the current node as vstd.
list<int>::iterator i;
for (i = a[x].begin(); i != a[x].end(); ++i)
if (!vstd[*i])
Topo_Sort(*i, vstd, Stack);
// Push current vertex to stack which stores result
Stack.push(x);
}
void grph::Topol_Sort() {
stack<int> Stack;
// Mark all the vertices as not vstd
bool *vstd = new bool[ver];
for (int i = 0; i < ver; i++)
vstd[i] = false;
for (int i = 0; i < ver; i++)
if (vstd[i] == false)
Topo_Sort(i, vstd, Stack);
while (Stack.empty() == false) {
cout << Stack.top() << " ";
Stack.pop();
}
}
int main() {
grph g(6); // Create a graph given in the above diagram
g.Insert_Edge(5, 2);
g.Insert_Edge(5, 0);
g.Insert_Edge(4, 0);
g.Insert_Edge(4, 1);
g.Insert_Edge(2, 3);
g.Insert_Edge(3, 1);
cout << "Topological Sort of the graph is: \n";
g.Topol_Sort();
return 0;
}輸出
Topological Sort of the graph is: 5 4 2 3 1 0
更新時間：2019 年 7 月 30 日
524 次檢視
廣告