图 §4.5拓扑排序 在工程实践中，一个工程项目往往由若干个子项目组成。这些子项目间往往有 两种关系：①先后关系，即必须在一项目完成拭一，才能开始实施另一个子项目： ②子项目间无关系，即两个子项目可以同时进行，互不影响。工厂里产品的生产线 上，一个产品由若干个零部件组成。零部件生产时，也存在这两种关系：先后关系， 即一个部件必须在完成后才能生产另一个部件：部件间无先后关系，即这两个部件 可以同时生产。大学里某个专业的课程学习，有些课程是基础课，它们可独立于其 他课程，即无前导课程：有些课程必须在某些基础看成是一个个顶点，课程的学习 分别构成一个有向图，现在要从这些有向图上分别找出的实施，产品的生产，课程 的学习分别构成一个有向图，现在要从这些有向图上分别找出一个施工流程图、产 品生产流程图、课程学习流程图，以便顺利进行施工、产品生产和课程学习，解决 这个问题可以采用拓扑排序的方法。 设G=(W,E)是一个具有n个顶点的有向图，V中顶点的序列V1,V2,Vn称 为一个拓扑序列，当且仅当该顶点序列满足下列条件：若在有向图G中，从顶点 Vi到是Vj有一条路径，则在序列中顶点Vi必须排在顶点Vj之前。 找一个有向图的一个拓扑序列的过程称为拓扑排序。 假定计算机软件专业的课程之间存在下述关系： 图 §4.5 拓扑排序 在工程实践中，一个工程项目往往由若干个子项目组成。这些子项目间往往有 两种关系：①先后关系，即必须在一项目完成拭一，才能开始实施另一个子项目； ②子项目间无关系，即两个子项目可以同时进行，互不影响。工厂里产品的生产线 上，一个产品由若干个零部件组成。零部件生产时，也存在这两种关系：先后关系， 即一个部件必须在完成后才能生产另一个部件；部件间无先后关系，即这两个部件 可以同时生产。大学里某个专业的课程学习，有些课程是基础课，它们可独立于其 他课程，即无前导课程；有些课程必须在某些基础看成是一个个顶点，课程的学习 分别构成一个有向图，现在要从这些有向图上分别找出的实施，产品的生产，课程 的学习分别构成一个有向图，现在要从这些有向图上分别找出一个施工流程图、产 品生产流程图、课程学习流程图，以便顺利进行施工、产品生产和课程学习，解决 这个问题可以采用拓扑排序的方法。 设 G=（V，E）是一个具有 n 个顶点的有向图，V 中顶点的序列 V1，V2，Vn 称 为一个拓扑序列，当且仅当该顶点序列满足下列条件：若在有向图 G 中，从顶点 Vi 到是 Vj 有一条路径，则在序列中顶点 Vi 必须排在顶点 Vj 之前。 找一个有向图的一个拓扑序列的过程称为拓扑排序。 假定计算机软件专业的课程之间存在下述关系：