拓扑排序是针对有向无环图的，当然也可以用它来检测到底有没有环，数据结构中学过其构成原理，这里就不再赘述，主要来讲他的实现。
分析原理，其实他的过程有点类似于层次遍历，所以用队列存储入度为0的点是OK的，但其实只要每次入队的结点入度为0，也没有顺序要求，栈也行，这里我为了避免每次比较麻烦，直接用优先队列实现。
#include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; int G[51][51]; int indegree[51]={0}; int num[51];//存储拓扑排序顺序 struct cmp{ bool operator()(const int a,const int b)const{ return indegree[a]>indegree[b];} }; bool topologicalsort(int n){ priority_queue<int,vector<int>,cmp>q; //优先队列存储入度下标，按从小到大排序 for(int i=1;i<=n;i++)//全部入队 q.push(i); int i=1; while(!q.empty()){ //只要队空，拓扑完成 int t=q.top();q.pop(); if(indegree[t]!=0)//队首元素入度不为0，失败 return false; num[i++]=t; for(int j=1;j<=n;j++) if(G[t][j]!=0) indegree[j]--; } return true; } int main(){ int n,x; scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&x); G[i][j]=x; if(x!=0)indegree[j]++; } if(topologicalsort(n)){ for(int i=1;i<=n;i++) printf("%d ",num[i]-1) ; printf("\n"); } else printf("ERROR"); return 0; }
而用栈实现拓扑排序有一个好处，其元素的输出恰好是逆拓扑排序，在求关键路径时有用，下面是其代码。
stack<int>s;//存储拓扑排序，逆向输出为逆拓扑排序 bool topological(int n) { queue<int>q; for(int i=1;i<=n;i++) if(indegree[i]==0) q.push(i); while(!q.empty()){ int t=q.front();q.pop(); s.push(t); for(int i=0;i<Adj[t].size();i++){ int x=Adj[t][i].v,w=Adj[t][i].w; indegree[x]--; if(indegree[x]==0) q.push(x); } } if(s.size()==n)return true; return false; }
