lzm

who dare win.
posts - 14, comments - 29, trackbacks - 0, articles - 0

Topsort 拓扑排序

Posted on 2009-04-06 09:40 lzmagic 阅读(2048) 评论(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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理