初始化优先队列q for i:=1 to n if indegree[i]=0 q.push(i) endif endfor if 队列q空 return false endif while 队列q不空 cnt:=cnt+1 u:=队列q弹出并返回值 j:=j+1 topo[j]:=u for k:=0 to u的出度数 v:=head[u,i] indegree[v]:=indegree[v]-1 if(indegree[v]=0) q.push(v) endif endfor endwhile if cnt=n return false else return true endif
深搜toposort()
1 2 3 4 5
t:=n for u:=1 to n if book[u]=0 and dfs(u)=false return false endif endfor return true
dfs(u)
1 2 3 4 5 6 7 8 9 10 11
book[u]:=-1 for v:=1 to n if g[u,v]=1 if book[v]<0 return false else if book[v]=0 and dfs(v)=false return false endif endif endfor book[u]=1 t:=t-1 topo[t]:=u return true