拓扑排序

时间：2017-07-30 12:20:48 收藏：0 阅读：269

对有向无边图的一种排序，它使得如果存在一条从 Vi 到 Vj 的路径，那么在排序中 Vj 出现在 Vi 后面

方法：找出任意一个没有入边的顶点开始，将其及其出度边删除，重复

伪码如下：

void Topsort(Graph G) {
    Queue Q;
    int Count = 0;
    Vertex V, W;
    Q = CreateQueue(NumVertex);
    MakeEmpty(Q);
    for each vertex Vertex
        if (Indegree[V] == 0)
            Enqueue(V, Q)

    while (!Empty(Q)) {
        V = Dequeue(Q);
        TopNum[V] = ++Count;

        for each W adjacent to V
            if (--Indegree[W] == 0)
                Enqueue(W, Q);
    }

    if (Counter != NumVertex)
        Error("cycle");

    DisposeQueue(Q);
}

原文：http://www.cnblogs.com/m2492565210/p/7258539.html