拓扑排序算法思想

1、在AOV网络中选一个没有直接前驱的顶点, 并输出之;

2、从图中删去该顶点, 同时删去所有它发出的有向边;

3、重复以上步骤, 直到

◆ 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；

◆ 或者图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。
用两种情况做的题目，深化理解（拓扑排序完成；AOV网络中必定存在有向环）

以下引自算法导论：

有向无回路图又称为DAG。对这种有向无回路图的拓扑排序的结果为该图所有顶点的

一个线性序列，满足如果G包含(u,v)，则在序列中u出现在v之前（如果图是有回路

的就不可能存在这样的线性序列）。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的有向边均从左指向右。因此，拓扑排序不同于通常意义上对于线性表的排序。  

• 
  int graph[narray][narray]; //邻接阵 
  
• int indegree[narray]; //记录顶点的入度 
  
• int n; //n为顶点个数 
  
• memset(graph,0,sizeof(graph));
  
• memset(indegree,0,sizeof(indegree));
  
• for(i=1;i<</SPAN>=n;++i) //遍历n次每次找出一个顶点 
  
• {
  
•     for(j=1;j<</SPAN>=n;++j) //遍历所有的结点 
  
•     {
  
•         if(indegree[j]==0)
  
•         {
  
•             indegree[j]--; //该顶点的入度为-1，防止该顶点被在此遍历到 
  
•             if(i!=n) printf("%d ",j);
  
•             else printf("%d\n",j);
  
•             for(k=1;k<</SPAN>=n;++k)
  
•             {
  
•                  if(graph[j][k])
  
•                      indegree[k]--; //与该顶点关联的顶点的入度递减 
  
•             }
  
•             break;
  
•         }
  
•     }
  
• }