算法学习 - 图的拓扑排序

拓扑排序

拓扑排序是对有向无圈图的顶点的一种排序，使得如果存在一条从Vi到Vj的路径，那么排序中Vj一定出现在Vi后面。

所以假如图里面有圈就不可能完成排序的。

第一种方法

一种简单的办法就是在排序算法中，先找到任意一个没有入边的顶点，然后显示该顶点，并把它和它的边一起从图里删掉。依次类推到最后。

入度(indegree): 顶点v的入度为，所有指向顶点v的变数(u, v)。
出度(outdegree): 顶点v的出度为，顶点v所发出的边数(v, u)。

下面写下这种方法的伪代码，因为这个的时间复杂度O(|V|^2) 所以效率其实并不好，第二种方法给出真实代码。

void Topsort ( Graph G )
{
    int Counter;
    Vertex V, W;
    for ( Counter = 0; Counter < NumVertex; Counter++ )
    {
        V = FindNewVertexOfIndegreeZero();
        if ( V == NotVertex )
        {
            Error("Graph has a cycle");
            break;
        }
        TopNum[V] = Counter;
        for each W adjacent to V
            Indegree[W]--;
    }
}

此伪代码来源：《Data Structures and Algorithm Analysis in C》

第二种方法

这种办法其实也很好理解，就是说在我们上面哪种方法的时候我们发现，其实每次第一次我们把所有入度为0的点加入到队列中后，每次产生的新的入度为0的点，肯定是因为当前遍历的点所造成的，所以我们记录下每次点入度的更新，当为0就加入到队列中就可以了。

//
//  main.cpp
//  TopologySort
//
//  Created by Alps on 15/3/3.
//  Copyright (c) 2015年 chen. All rights reserved.
//

#include <iostream>
#include <queue>
using namespace std;

struct Node{
    int val;
    int length;
    Node* next;
    Node(): val(0), length(0), next(NULL) {}
};

typedef Node* Graph;

int *degree;

Graph CreateG (Graph G){
    int num;
    scanf("%d", &num); // input the number of the vertex
    G = (Graph)malloc(sizeof(struct Node) * (num+1)); //malloc memory for graph
    G[0].length = num; //save the graph vertex number
    degree = (int *)malloc((num+1) * sizeof(int));
    memset(degree, 0, num*sizeof(int));
    for (int i = 1; i <= num; i++) {
        G[i].val = i;
        G[i].next = NULL;
        int outdegree = 0;
        scanf("%d", &outdegree);
        for (int j = 0; j < outdegree; j++) {
            Node* temp = (Node*)malloc(sizeof(struct Node));
            scanf("%d %d",&(temp->val), &(temp->length));
            temp->next = G[i].next;
            G[i].next = temp;
            degree[temp->val] += 1;
        }
    }
    return G;
}

void PrintG (Graph G){
//    int length = sizeof(G)/sizeof(struct Node);
    int length = G[0].length;
    Node * temp;
    for (int i = 1; i <= length; i++) {
        temp = &G[i];
        printf("Node: %d ",temp->val);
        while (temp->next) {
            printf("-> %d(%d)",temp->next->val, temp->next->length);
            temp = temp->next;
        }
        printf("\n");
    }
}

int* TopologySort (Graph G){
    queue<Node> Q;
    int counter = 0;
    int length = G[0].length;
    int *TopNum = (int*)malloc((length+1) * sizeof(int));
    for (int i = 1; i <= length; i++) {
        if (degree[i] == 0) {
            Q.push(G[i]);
        }
    }
    while (!Q.empty()) {
        Node V = Q.front();
        TopNum[V.val] = ++counter;
        Node * temp = &V;
        while (temp->next) {
            temp = temp->next;
            degree[temp->val] -= 1;
            if (degree[temp->val] == 0) {
                Q.push(G[temp->val]);
            }
        }
        Q.pop();
    }

    if (length != counter) {
        return NULL;
    }

    return TopNum;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    Graph G;
    G = CreateG(G);

    PrintG(G);

    int *TopNum = TopologySort(G);
    for (int i = 1;TopNum != NULL && i <= G[0].length; i++) {
        printf("%d ",TopNum[i]);
    }
//    std::cout << "Hello, World!\n";
    return 0;
}