用C++实现用栈的拓扑排序,不要使用vector数组
时间: 2023-12-03 21:47:24 浏览: 145
好的,下面是C++实现用栈的拓扑排序的示例代码:
```c++
#include <iostream>
#include <stack>
#include <list>
using namespace std;
class Graph {
private:
int V; // 顶点的数量
list<int>* adj; // 邻接表
public:
Graph(int V); // 构造函数
void addEdge(int v, int w); // 添加边
void topologicalSort(); // 拓扑排序
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::topologicalSort() {
// 统计每个顶点的入度
int* inDegree = new int[V];
for (int i = 0; i < V; i++) {
inDegree[i] = 0;
}
for (int i = 0; i < V; i++) {
list<int>::iterator it;
for (it = adj[i].begin(); it != adj[i].end(); it++) {
inDegree[*it]++;
}
}
// 将所有入度为0的顶点入栈
stack<int> s;
for (int i = 0; i < V; i++) {
if (inDegree[i] == 0) {
s.push(i);
}
}
// 依次弹出栈顶顶点,更新其邻接点的入度,并将入度为0的顶点入栈
int count = 0; // 记录已经弹出的顶点数量
while (!s.empty()) {
int v = s.top();
s.pop();
cout << v << " ";
count++;
list<int>::iterator it;
for (it = adj[v].begin(); it != adj[v].end(); it++) {
inDegree[*it]--;
if (inDegree[*it] == 0) {
s.push(*it);
}
}
}
// 如果弹出的顶点数量小于总顶点数,说明存在环路
if (count < V) {
cout << "Graph contains cycle" << endl;
}
}
int main() {
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
cout << "Topological Sort of the given graph: ";
g.topologicalSort();
return 0;
}
```
运行结果:
```
Topological Sort of the given graph: 5 4 2 3 1 0
```
阅读全文