C++实现拓扑排序(邻接表存储，栈实现)

代码如下:

#include <iostream> #include <stack> using namespace std; const int N = 10010; using vnodeType = int; typedef struct Node {int adj;int w;Node *next; }Node;typedef struct Vnode {int indegree;vnodeType v;Node *firstEdge; }Vnode;class Graph { public:void createGraph(){int n, m;cin >> n >> m;vnodeNum = n;edgeNum = m;for (int i = 0; i < n; i++){cout << "请输入第" << i << "个顶点要存储的信息" << endl;cin >> adjlist[i].v;adjlist[i].firstEdge = nullptr;}for (int i = 0; i < m; i++){int x, y;cin >> x >> y;Node *p = new Node;p->adj = y;p->next = adjlist[x].firstEdge;adjlist[x].firstEdge = p;}}void findIndegree(){for (int i = 0; i < vnodeNum; i++){adjlist[i].indegree = 0;}for (int i = 0; i < vnodeNum; i++){for (Node *p = adjlist[i].firstEdge; p; p = p->next){adjlist[p->adj].indegree++;}}}void Top_sort(){int cnt = vnodeNum;findIndegree();stack<int>s;for (int i = 0; i < vnodeNum; i++){if (!adjlist[i].indegree) s.push(i);}while (!s.empty()){int xx = s.top();cout << adjlist[xx].v << " ";cnt--;s.pop();for (Node *p = adjlist[xx].firstEdge; p; p = p->next){int yy = p->adj;adjlist[yy].indegree--;if (!adjlist[yy].indegree) s.push(yy);}}if (cnt) cout << "The network has a cycle" << endl;}private:int vnodeNum;int edgeNum;Vnode adjlist[N];};int main() {Graph g;g.createGraph();g.Top_sort();return 0; }

测试结果:

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的C++实现拓扑排序(邻接表存储，栈实现)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。