c++基础知识-图论进阶
一、拓扑排序
1、基础知识
1）什么是拓扑排序
对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若，则u在线性序列中出现在v之前。
2）拓扑排序的操作方法
重复执行下列步骤，直到不存在入度为0的顶点为止。
a)选择一个入度为0的顶点并输出：
b)从图中删除此顶点及所有出边。
环的判断方法：操作结束后，如果输出的顶点的数量<图的顶点数，说明存在环，所需时间 O(n)。每个顶点入度减1的运算共执行了e次。所有总的时间复杂为O(n+e)。