数据结构
网络
关系数据库管理系统 (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 次浏览
广告