浅谈拓扑排序与Kahn算法

拓扑排序的结果序列反应了有向图中前顶点的前驱后继关系。所以，手算拓扑排序很简单，每次检查入度为0的顶点，删除从此顶点出发的边，将该顶点加入拓扑排序序列即可。
Kahn算法其实就是模拟这个过程，不过其核心的优化在于将采用BSF的方式来进行，同时维护一个入度数组，每次加入一个顶点就更新入度数组，并且若入度为0则加入BSF的队列里供后续排序时访问即可。Kahn算法时间复杂度在O(|V|+|E|)，空间复杂度则和一般的BSF一样是O(|V|)
所以有如下代码

1. int kahn_toplogical_Sort(adjList &aGraph, int sequence[]) {
2.     // 计算顶点入度
3.     int *indegree = (int*)calloc(aGraph.vnum, sizeof(int));
4.     for(int i = 0; i < aGraph.vnum; ++i)
5.         for(arcNode *p = aGraph.vexlist[i].firstarc; p != nullptr; p = p->nextarc) {
6.             ++(indegree[p->adjVex]);
7.         }
8.     // 顶点队列初始化
9.     int *vex_Q = (int*)malloc(sizeof(int) * aGraph.vnum);
10.     int rear = 0, front = 0;
11.     for(int i = 0; i < aGraph.vnum; ++i)
12.         if(indegree[i] == 0)
13.             vex_Q[rear++] = i;
14.     int insequence = 0;
15.     while(rear != front) {
16.         int vex = vex_Q[front++];
17.         for(arcNode *p = aGraph.vexlist[vex].firstarc; p != nullptr; p = p->nextarc) {
18.             --(indegree[p->adjVex]);
19.             if(indegree[p->adjVex] == 0)
20.                 vex_Q[rear++] = p->adjVex;
21.         }
22.         sequence[insequence++] = vex;
23.     }
24.     free(indegree);
25.     free(vex_Q);
26.     if(insequence < aGraph.vnum)  //排序失败
27.         return 0;
28.     return 1;  //排序成功
29. }

复制代码

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除