浅谈拓扑排序与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.firstarc; p != nullptr; p = p->nextarc) {
++(indegree);
}
// 顶点队列初始化
int *vex_Q = (int*)malloc(sizeof(int) * aGraph.vnum);
int rear = 0, front = 0;
for(int i = 0; i < aGraph.vnum; ++i)
if(indegree == 0)
vex_Q = i;
int insequence = 0;
while(rear != front) {
int vex = vex_Q;
for(arcNode *p = aGraph.vexlist.firstarc; p != nullptr; p = p->nextarc) {
--(indegree);
if(indegree == 0)
vex_Q = p->adjVex;
}
sequence = vex;
}
free(indegree);
free(vex_Q);
if(insequence < aGraph.vnum)//排序失败
return 0;
return 1;//排序成功
}
来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除
页:
[1]