拓扑排序思想

拓扑排序算法思想

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

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

3、重复以上步骤, 直到

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

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

这种好实现：

其实说白了，拓扑排序就是一个广度优先搜索。

拓扑排序的方法如下:

　　(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.

　　(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.

　　(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.

以下引自算法导论：

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

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

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

TopoSort(拓扑排序)

　

下列简单算法可以对一个有向无回路图进行拓扑排序。  

　　procedure Topological_Sort(G);  

　　begin  

　　 1.调用DFS(G)计算每个顶点的完成时间f[v];  

　　 2.当每个顶点完成后，把它插入链表前端;  

　　 3.返回由顶点组成的链表;  

　　end;  

　引理1  

　　有向图G无回路当且仅当对G进行深度优先搜索没有得到反向边。  

　定理1  

　　Topological_Sort(G)算法可产生有向无回路图G的拓扑排序。  

拓扑排序模板：
在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点表及顶点数等均可省略）。

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