浅谈拓扑排序与Kahn算法

拓扑排序的结果序列反应了有向图中前顶点的前驱后继关系。所以，手算拓扑排序很简单，每次检查入度为0的顶点，删除从此顶点出发的边，将该顶点加入拓扑排序序列即可。

Kahn算法其实就是模拟这个过程，不过其核心的优化在于将采用BSF的方式来进行，同时维护一个入度数组，每次加入一个顶点就更新入度数组，并且若入度为0则加入BSF的队列里供后续排序时访问即可。Kahn算法时间复杂度在O(|V|+|E|)，空间复杂度则和一般的BSF一样是O(|V|)

所以有如下代码

int kahn_toplogical_Sort(adjList &aGraph, int sequence[]) {
    // 计算顶点入度 
    int *indegree = (int*)calloc(aGraph.vnum, sizeof(int));
    for(int i = 0; i < aGraph.vnum; ++i)
        for(arcNode *p = aGraph.vexlist[i].firstarc; p != nullptr; p = p->nextarc) {
            ++(indegree[p->adjVex]);
        }
    // 顶点队列初始化
    int *vex_Q = (int*)malloc(sizeof(int) * aGraph.vnum);
    int rear = 0, front = 0;
    for(int i = 0; i < aGraph.vnum; ++i)
        if(indegree[i] == 0)
            vex_Q[rear++] = i;
    int insequence = 0;
    while(rear != front) {
        int vex = vex_Q[front++];
        for(arcNode *p = aGraph.vexlist[vex].firstarc; p != nullptr; p = p->nextarc) {
            --(indegree[p->adjVex]);
            if(indegree[p->adjVex] == 0)
                vex_Q[rear++] = p->adjVex;
        }
        sequence[insequence++] = vex;
    }
    free(indegree);
    free(vex_Q);
    if(insequence < aGraph.vnum)  //排序失败
        return 0;
    return 1;  //排序成功
}

来源链接：https://www.cnblogs.com/RodneyTang/p/19018790