上课的顺序(拓扑排序)

有一个课程表，有课程名和编号，还有一些课程的先导课信息，参数是vector,例如
A:B C D
B:C
C:
D:
表示有4门课，课程名分别为A,B,C,D,然后再上A课程之前必须先上B,C,D,上B之前必须先上C,求出一个上课的顺序。

 

以前没做过这类。是简单的拓扑排序。

根据百度百科，基本解法如下：

　(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.

　(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.

　(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.

 

代码codepad.org已验证

#include <stdio.h>
#include <stdlib.h>


void cover(int matrix[][4], int size){
    int row = 0;
    int column = 0;
    int count = 0;
    char record[size];
    int i = 0;
    for(;i<size;i++){
        record[i] = 0;
    }

    while(count!=size){
                row = 0;
        for(;row<size && record[row]!=1;row++){
            int sum = 0;
            column = 0;
            for(;column<size;column++){
                sum|=matrix[row][column];
            }
            if(sum == 0){
                printf("%d->",row);
                //remove the node;
                record[row] = 1;
                int d;
                for(d= 0;d<size;d++){
                    matrix[d][row] = 0;
                }
                                count++;
            }
        }
    }
}

int main(){
    int matrix[4][4]={{0}};
    matrix[0][1] = 1;
    matrix[0][3] = 1;
    matrix[1][2] = 1;
    matrix[3][2] = 1;
    cover(matrix,4);

    return 0;
}