拓扑排序的目标是能够处理DAG的顶点,让每个顶点在它指向的所有顶点被处理
之前被处理 。排序结果使得图上节点的非线性序转化为线性序,但节点的排列顺序
依然遵循原图上节点前驱与后继的传递性。

       因为要做n个顶点的n次栈操作+e次入度减一运算,所以总的时间复杂度为O(n+e)。

int ToPologicalSort(int n,int degree[],Edge _edgeArr[]){
 Edge tmpNod;
 
int l,top=-1;
 
 RecordInDegree(n,degree,_edgeArr);  
// 记录各节点入度数

 
for(int i=0;i<n;i++)
    
if(degree[i]==0){
       degree[i]
=top;  // 在原数组构造栈,入度为0节点压栈
       top=i;
    }

      
 
  
for(int i=0;i<n;i++){
     
if(top==-1){ printf("成环\n"); return 0;} //栈空,节点有剩余,成环
     l=top;
     top
=degree[top];
     printf(
"%d ",l);
    
     tmpNod
=_edgeArr[l];
     
while(tmpNod){
       
if(--degree[tmpNod->v]==0){  // 对应相邻节点入度减一,为0则压栈
         degree[tmpNod->v]=top;
         top
=tmpNod->v;
       }

       tmpNod
=tmpNod->link;
     }

  }

}


void RecordInDegree(int n,int degree[],Edge _edgeArr[]){
   Edge tmpNod; 
int i;
   
for(i=0;i<n;i++){
      tmpNod
=_edgeArr[i];
      
while(tmpNod){
          degree[tmpNod
->v]++;  // i相邻后继入度加一
          tmpNod=tmpNod->link;
      }

   }

}