拓扑排序总结

       今天搞了一天拓扑排序，在学习的过程中发现大多数博客不是看不懂就是只针对一种情况，于是这里小总结一下。

一、定义
    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
注意:
       1)只有有向无环图才存在拓扑序列;
       2)对于一个DAG,可能存在多个拓扑序列;
二、拓扑序列算法思想
    (1)从有向图中选取一个没有前驱(即入度为0)的顶点，并输出之;
    (2)从有向图中删去此顶点以及所有以它为尾的弧; 
    重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

    用排课程表讲解拓扑排序很容易理解：

                有许多课程是需要在学习了其它课程做基础才学习其它课程，例如：必须学完计算机基础才能学数据机构。如果这门课是最基础的那它的入度（即：需要学习完几门课之后在学习它，它的入度就是几）为零。

模版(矩阵)：

  

   

    

     

    
    

     

      int topo[2003],n;
     
    
   

    

     

    
    

     

      char g[2002][2003];
     
    
   

    

     

    
    

     

      memset(topo,0,sizeof(topo));
     
    
   

    

     

    
    

     

      int toposort()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int f=0;
     
    
   

    

     

    
    

     
 for(int i=0;i<n;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       f=0;
     
    
   

    

     

    
    

     
 for(int j=0;j<n;j++)
     
    
   

    

     

    
    

     
 if(topo[j]==0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       f=1;
     
    
   

    

     

    
    

     

       topo[j]=-1;
     
    
   

    

     

    
    

     
 for(int k=0;k<n;k++)
     
    
   

    

     

    
    

     
 if(g[j][k]==1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       topo[k]--;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 break;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(f==0)
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 1;
     
    
   

    

     

    
    

     

      }
     
    
  
 

f标记是否存在环。

模版（深搜）：

  

   

    

     

    
    

     

      int c[MAXN],G[MAXN][MAXN];
     
    
   

    

     

    
    

     

      int topo[MAXN],t;
     
    
   

    

     

    
    

     

      bool dfs(int u)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       c[u]=-1;
     
    
   

    

     

    
    

     
 for(int v=0;v<n;v++)
     
    
   

    

     

    
    

     
 if(G[u][v])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(c[v]<0)
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     
 else if(!c[v]&&!dfs(v))
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       c[u]=1;topo[--t]=u;
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      bool toposort()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       t=n;
     
    
   

    

     

    
    

     
 memset(c,0,sizeof(c));
     
    
   

    

     

    
    

     
 for(int u=0;u<n;u++)
     
    
   

    

     

    
    

     
 if(!c[u])
     
    
   

    

     

    
    

     
 if(!dfs(u))
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/9412471