拓扑排序-学习笔记

定义

对一个有向无环图(Directed Acyclic Graph简称DAG)$G$进行拓扑排序，是将$G$中所有顶点排成一个线性序列，使得图中任意一对顶点$u$和$v$，若边$(u,v)∈E(G)$，则$u$在线性序列中出现在$v$之前。

实现步骤

在有向图中选一个没有前驱的顶点并且输出
删除所有和它有关的边
重复上述两步，直至所有顶点输出，或者当前图中不存在无前驱的顶点。后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断一个图是否有环。

无向图的判环

环上的点度数$>=2$ (与环外的点有边时度数$>2$)

删除所有度$<=1$的顶点及相关的边，并将另外与这些边相关的其它点的度减$1$
将度数变为$1$的点重复上步骤
如果最后还有未删除顶点，则存在环，否则没有环

 1 void tp()
 2 {
 3     for(int i=1;i<=n;i++)
 4         if(ind[i]==0)
 5             Q.push(i);
 6     while(!Q.empty())
 7     {
 8         int u=Q.front();
 9         Q.pop();
10         ans[++cnt]=u;
11         for(int i=0;i<G[u].size();i++)
12         {
13             int v=G[u][i];
14             ind[v]--;
15             if(ind[v]==0)
16                 Q.push(v);
17         }
18     }
19 }

$cnt<n$就说明有环，此时$ind[i]$不为$0$的点就在环上