python实现拓扑排序的基本教程

几乎在所有的项目，甚至日常生活，待完成的不同任务之间通常都会存在着某些依赖关系，这些依赖关系会为它们的执行顺序行程表部分约束。对于这种依赖关系，很容易将其表示成一个有向无环图，并将寻找其中依赖顺序的过程称为拓扑排序。如果剩下入度非0的顶点，就说明N中有回路，不存在拓扑排序。存在回路，意味着某些活动的开始要以其自己的完成作为先决条件，这种现象成为活动之间的死锁。一种常见的顶点活动网实例是大学课程的先修课程。因此可以说拓扑排序算法是为了做出满足制约关系的工作安排。下面我们操作一个实例，如下图是一个有向无环图：用字典表示：G = { 'a':'bce', 'b':'d','c':'d','d':'','e':'cd'}输出结果：图中有环的情况：输出结果：