十大排序算法——拓扑排序

思想：

把有向图中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。
方法：
在有向图中选一个没有前驱的顶点且输出
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出（拓扑排序成功），或者当图中不存在无前驱的顶点（图中有回路）为止。

C

void TopologicalSort()/*输出拓扑排序函数。若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR*/ 
{ 
      int indegree[M]; 
      int i,k,j; 
      char n; 
      int count=0; 
      Stack thestack; 
      FindInDegree(G,indegree);//对各顶点求入度indegree[0....num] 
      InitStack(thestack);//初始化栈 
      for(i=0;i<G.num;i++) 
          Console.WriteLine("结点"+G.vertices[i].data+"的入度为"+indegree[i]); 
      for(i=0;i<G.num;i++) 
      { 
           if(indegree[i]==0) 
              Push(thestack.vertices[i]); 
      } 
      Console.Write("拓扑排序输出顺序为："); 
      while(thestack.Peek()!=null) 
      { 
               Pop(thestack.Peek()); 
               j=locatevex(G,n); 
               if (j==-2) 
                  { 
                         Console.WriteLine("发生错误，程序结束。"); 
                         exit(); 
                  } 
                Console.Write(G.vertices[j].data); 
                count++; 
                for(p=G.vertices[j].firstarc;p!=NULL;p=p.nextarc) 
                { 
                     k=p.adjvex; 
                     if (!(--indegree[k])) 
                         Push(G.vertices[k]); 
                } 
      } 
      if (count<G.num) 
          Cosole.WriteLine("该图有环，出现错误，无法排序。"); 
      else
          Console.WriteLine("排序成功。"); 
} 

算法的时间复杂度O（n+e）。