首页 > 代码库 > 拓拔排序算法
拓拔排序算法
一、定义：
拓扑排序是对有向无回路图(DAG)顶点的一种排序，它使得如果存在从u到v的有向路径，那么满足序列中u在v前。
例如：（来自于某牛）
最后变成
所以我们的算法可以描述为这样一个过程：
1、找到整个图中所有的原点，将这些点压进队列（栈）中
2、从队列（栈）中取出一点，输出，将该点及它的边删除，找到它所指向的点，如果改点是一个原点（删除指向它的点后），则压入队列（栈）
3、重复2过程，直到它为空
应用：
1、判断有向图中是否存在回路。如果无法构成拓扑序列，那么图中存在环。
2、如果一个事件有拓扑关系（比如时间先后、重要程度），那么可以给出一种可行方案。
3、给一个图确定拓扑关系，也就是为图的DP划分阶段。在关键路径中应用比较明显。
4、2-Sat问题中给顶点染色
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。