資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式：建立有向無環圖 (DAG) 的隨機線性擴充套件
這裡我們將學習如何建立一個有向無環圖 (DAG) 的隨機線性擴充套件。線性擴充套件基本上是有向無環圖的拓撲排序。假設圖如下所示：
有向無環圖的拓撲排序是頂點的線性排序。對於有向圖的每條邊 u-v，頂點 u 將在排序中出現在頂點 v 之前。
眾所周知，源頂點將出現在目標頂點之後，因此我們需要使用堆疊來儲存之前的元素。完成所有節點後，我們可以簡單地從堆疊中顯示它們。
輸入
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
輸出
拓撲排序後的節點：5 4 2 3 1 0
演算法
topoSort(u, visited, stack)
輸入 - 起始頂點 u，一個用於跟蹤哪個節點已被訪問的陣列。一個用於儲存節點的堆疊。
輸出 - 將頂點按拓撲順序排序到堆疊中。
Begin mark u as visited for all vertices v which is adjacent with u, do if v is not visited, then topoSort(c, visited, stack) done push u into stack End
performTopologicalSorting(Graph)
輸入 - 給定的有向無環圖。
輸出 - 節點序列。
Begin initially mark all nodes as unvisited for all nodes v of the graph, do if v is not visited, then topoSort(i, visited, stack) done pop and print all elements from the stack End
示例
#include<iostream>
#include<stack>
#define NODE 6
using namespace std;
int graph[NODE][NODE] = {
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 0},
{1, 1, 0, 0, 0, 0},
{1, 0, 1, 0, 0, 0}
};
void topoSort(int u, bool visited[], stack<int> &stk) {
visited[u] = true; //set as the node v is visited
for(int v = 0; v<NODE; v++) {
if(graph[u][v]){ //for allvertices v adjacent to u
if(!visited[v])
topoSort(v, visited, stk);
}
}
stk.push(u); //push starting vertex into the stack
}
void performTopologicalSort() {
stack<int> stk;
bool vis[NODE];
for(int i = 0; i<NODE; i++)
vis[i] = false; //initially all nodes are unvisited
for(int i = 0; i<NODE; i++)
if(!vis[i]) //when node is not visited
topoSort(i, vis, stk);
while(!stk.empty()) {
cout << stk.top() << " ";
stk.pop();
}
}
main() {
cout << "Nodes after topological sorted order: ";
performTopologicalSort();
}輸出
Nodes after topological sorted order: 5 4 2 3 1 0
更新於：2019年7月30日
84 次瀏覽
廣告