Posted on 2009-04-06 09:40
lzmagic 閱讀(2073)
評論(2) 編輯 收藏 引用 所屬分類:
Algorithm
/**//**
* TOPSORT(簡單版) 拓撲排序(Topological Sort)
* 輸入：有向圖g
* 輸出：是否存在拓撲排序，如果存在，獲取拓撲排序序列seq
* 結(jié)構(gòu)：圖g用鄰接矩陣表示
* 算法：廣度優(yōu)先搜索(BFS)
* 復(fù)雜度：O(|V|^2)
*/
#include <iostream>
#include <vector>
#include <queue>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <climits>
using namespace std;
int n; // n ：頂點個數(shù)
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); // 調(diào)整w的入度，如果w的入度為0，入隊。
}
return seqc == n; // 如果seq已處理頂點數(shù)為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;
}