一、基本知识

1、定义：拓扑排序是对有向无圈图的排序，如果存在一条从vi--vj的路径，那么排序过程中vj必定在vi之后。

2、排序条件：必须是有向图并且无圈；

3、拓扑排序的结果不唯一。

 

二、排序过程

1、存储图结构：图的边集用邻接表存储，用vector数组来代替更好；还要一个存储入度的数组，表示每个节点的入度；

一个队列在遍历图时存储图的每个节点（如果对序号有升序，降序需要可以用优先队列）。

2、找到入度为0点，然后入队

3、队列的头结点出队，遍历头结点的邻接节点，并且删除邻接点与头结点的边（就是入度-1）

4、如果这个节点比入度变为0，则入队。

5、重复2,3,4操作，直到队列为空，就是结束。

 

三、例题

（1）对结果序列有要求（字典序）

题目链接：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int maxn = 500;vector 
            
              edge[maxn];int in[maxn]={ 0},vis[maxn]={ 0},num=0;int main(void){ int i,j; char a,b,c; string str,ans=""; while(cin>>str) { a=str[0];b=str[1];c=str[2]; if(vis[a]==0) vis[a]=1,num++; if(vis[c]==0) vis[c]=1,num++; if(b=='>') in[c]++,edge[a].push_back(c); else in[a]++,edge[c].push_back(a); } priority_queue 
             
              
               , greater 
               
                 > q; for(i=30;i<=220;i++) if(vis[i]&&in[i]==0) q.push(i); while(!q.empty()) { int top=q.top(); q.pop(); ans+=(char)(top); for(i=0;i
               
              
             
            
           
          
         
        
       
      

 

 

（2）貌似字典序要求（比较坑）

题目链接：

 思路：约束条件：“a必须在b之前”，“让1号尽量靠前，如果此时还有多种情况，就再让2号尽量靠前，如果还有多种情况，就让3号尽量靠前，以此类推。”，所依按照拓扑排序建立的图，最先出队的节点不能确定是否先输出，而最后的可以：

eg：

图为：

 3->6->5->1

2->8->7->1

4->9->10->1

如果正序建图：2 8 7 3 6 5 4 9 10 1

但正确结果是：3 6 5 2 8 7 4 9 10 1

 

可以确定前面小的不一定在前面，但是后面大的一定在后面，所以可以逆序建图，然后逆序输出。

参考文章：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxn = 30030;int in[maxn],n,m;vector 
           
             edge[maxn],ans;int main(void){ int t,i,x,y; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) edge[i].clear(),in[i]=0; ans.clear(); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); in[x]++;edge[y].push_back(x); } priority_queue 
            
              q; for(i=1;i<=n;i++) if(in[i]==0) q.push(i); while(!q.empty()) { int top=q.top(); ans.push_back(top); q.pop(); for(i=0;i
             
              =0;i--) { if(i!=ans.size()-1) printf(" "); printf("%d",ans[i]); } printf("\n"); } return 0;}