lzm

who dare win.

posts - 14, comments - 29, trackbacks - 0, articles - 0

Topsort 拓撲排序

Posted on 2009-04-06 09:40 lzmagic 閱讀(2076) 評論(2) 編輯收藏引用所屬分類: Algorithm

/**

* TOPSORT(簡單版) 拓撲排序(Topological Sort)

* 輸入：有向圖g

* 輸出：是否存在拓撲排序，如果存在，獲取拓撲排序序列seq

* 結構：圖g用鄰接矩陣表示

* 算法：廣度優先搜索(BFS)

* 復雜度：O(|V|^2)

#include <iostream>

#include <vector>

#include <queue>

#include <iterator>

#include <algorithm>

#include <numeric>

#include <climits>

using namespace std;

int n; // n ：頂點個數

vector<vector<int> > g; // g ：圖(graph)(用鄰接矩陣(adjacent matrix)表示)

vector<int> seq; // seq ：拓撲序列(sequence)

bool TopSort()

{

vector<int> inc(n, 0);

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j)

if (g[i][j] < INT_MAX) ++inc[j]; // 計算每個頂點的入度，

queue<int> que;

for (int j = 0; j < n; ++j)

if (inc[j] == 0) que.push(j); // 如果頂點的入度為0，入隊。

int seqc = 0;

seq.resize(n);

while (!que.empty()) // 如果隊列que非空，

{

int v = que.front(); que.pop();

seq[seqc++] = v; // 頂點v出隊，放入seq中，

for (int w = 0; w < n; ++w) // 遍歷所有v指向的頂點w，

if (g[v][w] < INT_MAX)

if (--inc[w] == 0) que.push(w); // 調整w的入度，如果w的入度為0，入隊。

}

return seqc == n; // 如果seq已處理頂點數為n，存在拓撲排序，否則存在回路。

}

int main()

{

n = 7;

g.assign(n, vector<int>(n, INT_MAX));

g[0][1] = 1, g[0][2] = 1, g[0][3] = 1;

g[1][3] = 1, g[1][4] = 1;

g[2][5] = 1;

g[3][2] = 1, g[3][5] = 1, g[3][6] = 1;

g[4][3] = 1, g[4][6] = 1;

g[6][5] = 1;

if (TopSort())

{

copy(seq.begin(), seq.end(), ostream_iterator<int>(cout, " "));

cout << endl;

}

else

{

cout << "circles exist" << endl;

}

system("pause");

return 0;

}

Feedback

# re: [圖論算法] TOPSORT 拓撲排序回復 更多評論

2009-04-07 13:38 by aiver

你的代碼輸出是 0 1 4 2 6 3 5， 2先于3輸出了，有問題。

# re: [圖論算法] TOPSORT 拓撲排序 回復 更多評論

2009-04-07 14:37 by lzmagic

@aiver
啊哈，有個小bug，現在已經修改好了，謝謝指出錯誤~
答案是：0 1 4 3 2 6 5

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: Floyd_Warshall算法 Kruskal算法 Prim算法 Critical Path 關鍵路徑 Bellman_Ford算法 SPFA算法 Dijkstra算法 USP 無權最短路徑算法 Topsort 拓撲排序 (正則表達式)是否匹配(字符串) Quicksort 快速排序

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

lzm

導航

常用鏈接

留言簿(2)

隨筆分類(13)

隨筆檔案(14)

收藏夾(4)

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

Topsort 拓撲排序

Feedback

# re: [圖論算法] TOPSORT 拓撲排序回復 更多評論

# re: [圖論算法] TOPSORT 拓撲排序 回復 更多評論

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

lzm

導航

常用鏈接

留言簿(2)

隨筆分類(13)

隨筆檔案(14)

收藏夾(4)

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

Topsort 拓撲排序

Feedback

# re: [圖論算法] TOPSORT 拓撲排序 回復 更多評論

# re: [圖論算法] TOPSORT 拓撲排序 回復 更多評論

# re: [圖論算法] TOPSORT 拓撲排序回復更多評論

# re: [圖論算法] TOPSORT 拓撲排序回復更多評論