代碼如下:

#include <iostream> #include <queue> #include <vector> using namespace std; const int N = 10010; int in[N]; vector<int>v[N]; vector<int>print;//存放拓撲序列 int main() {int n, m;//n為點的個數，m為邊的條數,點的序號從0開始while (cin >> n >> m, n, m){memset(in, 0, sizeof(in));//清空入度for (int i = 0; i < n; i++) v[i].clear();for (int i = 1; i <= m; i++){int x, y;cin >> x >> y;v[x].push_back(y);//x指向yin[y]++;//y的入度+1}priority_queue<int, vector<int>, greater<int>>q;//優先隊列，設置從小到大排序，小的在隊列前面for (int i = 0; i < n; i++)if (!in[i]) q.push(i);//把入度為0的節點壓入隊列while (!q.empty()){int xx = q.top();print.push_back(xx);//也可以直接輸出，不用存進這個vector容器也行q.pop();n--;//每次去掉一個節點for (int i = 0; i < v[xx].size(); i++){int yy = v[xx][i];in[yy]--;if (!in[yy])q.push(yy);//如果去掉上一個節點之后下一個節點的入度為0，則壓入隊列}}if (!n){for (vector<int>::iterator it = print.begin(); it != print.end(); it++){cout << *it << " ";}cout << endl;}elsecout << "No" << endl;//如果有環的話節點數不會為0}return 0; }

測試結果:

總結

以上是生活随笔為你收集整理的C++实现拓扑排序(vector模拟邻接表存储，优先队列实现)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。