浅谈拓扑排序与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;//排序成功
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 谢谢分享，辛苦了 用心讨论，共获提升！ 谢谢分享，辛苦了 这个有用。 感谢分享，下载保存了，貌似很强大 很好很强大我过来先占个楼 待编辑 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 分享、互助 让互联网精神温暖你我 感谢分享，学习下。 不错，里面软件多更新就更好了 感谢，下载保存了 yyds。多谢分享 很好很强大我过来先占个楼 待编辑 感谢发布原创作品，程序园因你更精彩 感谢分享，学习下。 谢谢分享，试用一下 前排留名，哈哈哈 懂技术并乐意极积无私分享的人越来越少。珍惜 这个好，看起来很实用
页:
[1]
2