拓扑排序的模板题,主要是来学习一下用DFS来判断是否有环,以及输出拓扑排序的序列。用DFS进行拓扑排序需要借助一个标记c[v]
,c[v]=0
表示图中的结点未被访问过,c[v]=1
表示正在访问结点(及其后继),c[v]=2
表示结点访问完成。(当然,也可以设置为其他有相同含义的不同的数值。)
有向图中存在环,当且仅当访问到一个结点v
有c[v]=1
。证:设当前正在访问结点u
,其直接后继v
满足c[v]=1
,那么一定存在一条从v
到u
的路径,又存在有向边(u,v)
,则图中存在环。若c[v]!=1
,那么不存在从v
到u
的路径,也就没有环。
另一种比较熟悉的做法是不断从图中删去入度为0的结点,并把其加入拓扑序列。如果图中剩余的所有结点都不满足入度为0,则说明图中存在环。
1 |
|
1 |
|