C++ 程序检查是否可以在图中执行拓扑排序
c++server side programmingprogramming更新于 2024/9/30 19:14:00
在有向无环图中，我们可以使用拓扑排序按线性顺序对顶点进行排序。
拓扑排序仅适用于有向无环图。在有向无环图 (DAG) 中，可以有多个拓扑排序。
在下面的 C++ 程序中，我们将执行拓扑排序来检查图中是否存在循环。
算法
对于函数 Topo_Sort
开始 定义函数 Topo_Sort() 将 x 声明为整数数据类型、布尔数组的 vstd[] 和堆栈。 将它们作为参数传递。 初始化 vstd[x] = true 以将当前节点标记为 vstd。 声明一个迭代器 i。 for (i = a[x].begin(); i != a[x].end(); ++i) if (!vstd[*i]) then 调用 Topo_Sort(*i, vstd, Stack) 函数。 调用 push() 函数将值插入堆栈。 结束。
示例
#include<iostream>
#include <list>
#include <stack>
using namespace std;
class grph { // 表示图的类
int ver;
list<int> *a; // 指向包含邻接列表的数组的指针列表
void Topo_Sort(int x, bool vstd[], stack<int> &Stack); // TopologicalSort 使用的函数
public:
grph(int ver); // grpf 的构造函数
void Insert_Edge(int x, int y); // 向图中插入一条边
void Topol_Sort(); // 打印完整图的拓扑排序
};
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); // 将 y 添加到 x 的列表中。
}
// Topol_Sort 使用的递归函数
void grph::Topo_Sort(int x, bool vstd[], stack<int> &Stack) {
vstd[x] = true; // 将当前节点标记为 vstd。
list<int>::iterator i;
for (i = a[x].begin(); i != a[x].end(); ++i)
if (!vstd[*i])
Topo_Sort(*i, vstd, Stack);
// 将当前顶点推送到存储结果的堆栈
Stack.push(x);
}
void grph::Topol_Sort() {
stack<int> Stack;
// 将所有顶点标记为非 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); // 创建上图中给出的图
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 << "图的拓扑排序为:\n";
g.Topol_Sort();
return 0;
}
输出
图的拓扑排序为: 5 4 2 3 1 0
