在工程实践中,一个工程项目往往由若干个子项⽬目组成。这些子项目间往往有两种关系:

1  先后关系,即必须在某个项 ⽬完成后才能开始实施另一个子项目;

2  子项⽬目间无关系,即两个子项目可以同时进行,互不影响。

工厂里产品的生 产线上,一个产品由若干个零部件组成。零部件生产时,也存在这两种关系:先后关系,即一个部件必须在完成后才能生 产另一个部件;部件间无先后关系,即这两个部件可以同时生产。

大学里某个专业的课程学习,有些课程是基础课,它们 可独立于其他课程,即无前导课程;有些课程必须在某些基础看成是一个个顶点,课程的学习分别构成一个有向图,现在 要从这些有向图上分别找出的实施,产品的生产,课程的学习分别构成一个有向图,现在要从这些有向图上分别找出一个 施工流程图、产品生产流程图、课程学习流程图,以便顺利进行施工、产品生产和课程学习,解决这个问题可以采用拓扑 排序的方法。 设G=(V,E)是一个具有n个顶点的有向图,V中顶点的序列V1,V2,Vn称为⼀拓扑序列,当且仅当该顶点序列 满⾜足下列条件:若在有向图G中,从顶点Vi到是j有一条路径,则在序列中顶点必须排在顶点V之前。找一个有向图的一个拓扑序列的过程称为拓扑排序。

假定计算机软件专业的课程之间存在下述关系: 

课程代号              课程名称                    前导课程

C1                       ⾼高等数学                  无

C2                       程序设计语⾔言           无

C3                       数据结构                     C2


C4                       编译原理                     C2,C3


C5                       操作系统                     C3,C6


C6                       计算机组成原理           C7


C7                       普通物理                     C1

对这个有向图进⾏行拓扑排序可得到⼀一个拓扑序列:C1,C2,C7,C6,C3,C4,C5。也可得到另⼀一个拓扑序列C1, C7,C2,C3,C6,C4,C5。学⽣生按照任何⼀一个拓扑序列都可以顺利地进⾏行课程学习。下⾯面给出有向图拓扑排序算法的基本步骤:

1 从图中选择⼀一个⼊入度为0的顶点,输出该顶点;

2 从图中删除该顶点及其相关联的弧;

  (a)邻接表                                                                                                   (b)有向图  

首先C1、C4的入度都为0,选C1,删除C1及其边e1、e2,调整C2的⼊入度为0,C3的⼊入度为1,此时C2、C4的⼊入度为0 ,选C4,删除C4及边e3、e4,调整C3、C5的⼊入度为0,从C2、C5、C3中选C2,删除C2及边e,调整C6的⼊入度为2,从C3 、C5中选择C3,删除C3及边e6,调整C6的⼊入度为1,删除C5及边e7,调整C6的⼊入度为0,输出C6,⾄至此拓扑排完成,拓 扑序列为C1,C4,C2,C3,C5,C6。

这里拓扑排序给出两种方法：

1： 以邻接表作存储结构,给出拓扑排序的实现。算法设置一个队列（方便使用优先队列，输出相同条件下结点编号小的在前（后）的序列）,将所有⼊入度为0的顶点入该队。找入度为0的 顶点,只要从依次出队即可。删除边的操作转化为将为该顶点为弧尾,所有相应弧头的入度减1。

2：类似于dfs   用一个栈来存排序后的顺序，从一个顶点开始访问，依次访问它的邻接顶点，回溯的时候将当前结点压入栈（度为0的顶点一定是最后压入栈的）

下面以poj 2376为例

输入n 表示n个结点；

从第一个结点开始依次输入该结点的邻接结点，输入0表示改结点的邻接结点结束，开始输入下一个结点的邻接结点。