传送门:Kahn算法拓扑排序
摘录一段维基百科上的伪码:
L ← Empty list that will contain the sorted nodes
S ← Set of all nodes with no outgoing edges
for each node n in S do
visit(n)
function visit(node n)
if n has not been visited yet then
mark n as visited
for each node m with an edgefrom m to ndo
visit(m)
add n to L
DFS的实现更加简单直观,使用递归实现。利用DFS实现拓扑排序,实际上只需要添加一行代码,即上面伪码中的最后一行:add
n to L。
需要注意的是,将顶点添加到结果List中的时机是在visit方法即将退出之时。
这个算法的实现非常简单,但是要理解的话就相对复杂一点。
关键在于为什么在visit方法的最后将该顶点添加到一个集合中,就能保证这个集合就是拓扑排序的结果呢?
因为添加顶点到集合中的时机是在dfs方法即将退出之时,而dfs方法本身是个递归方法,只要当前顶点还存在边指向其它任何顶点,它就会递归调用dfs方法,而不会退出。因此,退出dfs方法,意味着当前顶点没有指向其它顶点的边了,即当前顶点是一条路径上的最后一个顶点。
下面简单证明一下它的正确性:
考虑任意的边v->w,当调用dfs(v)的时候,有如下三种情况:
- dfs(w)还没有被调用,即w还没有被mark,此时会调用dfs(w),然后当dfs(w)返回之后,dfs(v)才会返回
- dfs(w)已经被调用并返回了,即w已经被mark
dfs(w)已经被调用但是在此时调用dfs(v)的时候还未返回
需要注意的是,以上第三种情况在拓扑排序的场景下是不可能发生的,因为如果情况3是合法的话,就表示存在一条由w到v的路径。而现在我们的前提条件是由v到w有一条边,这就导致我们的图中存在环路,从而该图就不是一个有向无环图(DAG),而我们已经知道,非有向无环图是不能被拓扑排序的。
那么考虑前两种情况,无论是情况1还是情况2,w都会先于v被添加到结果列表中。所以边v->w总是由结果集中后出现的顶点指向先出现的顶点。为了让结果更自然一些,可以使用栈来作为存储最终结果的数据结构,从而能够保证边v->w总是由结果集中先出现的顶点指向后出现的顶点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<sstream>
#include<functional>
using namespace std;
typedef long long ll;
const int maxn = + ;
const int INF = 1e9 + ;
int T, n, m, cases;
vector<int>Map[maxn];
int c[maxn];//标记数组c[i] = 0 表示还未访问过点i, c[i] = 1表示已经访问过点i,并且还递归访问过它的所有子孙,c[i] = -1表示正在访问中,尚未返回
int topo[maxn], t;
bool dfs(int u)//从u出发
{
c[u] = -;//访问标志
for(int i = ; i < Map[u].size(); i++)
{
int v = Map[u][i];
if(c[v] < )return false;//如果子孙比父亲先访问,说明存在有向环,失败退出
else if(!c[v] && !dfs(v))return false;//如果子孙未被访问,访问子孙返回假,说明也是失败
}
c[u] = ;
topo[--t] = u;//在递归结束才加入topo排序中,这是由于在最深层次递归中,已经访问到了尽头,此时才是拓扑排序中的最后一个元素
return true;
}
bool toposort()
{
t = n;
memset(c, , sizeof(c));
for(int u = ; u <= n; u++)if(!c[u])
if(!dfs(u))return false;
return true;
}
int main()
{
while(cin >> n >> m)
{
if(!n && !m)break;
int u, v;
for(int i = ; i <= n; i++)Map[i].clear();
for(int i = ; i < m; i++)
{
cin >> u >> v;
Map[u].push_back(v);
}
if(toposort())
{
cout<<"Great! There is not cycle."<<endl;
for(int i = ; i < n; i++)cout<<topo[i]<<" ";
cout<<endl;
}
else cout<<"Network has a cycle!"<<endl;
}
return ;
}