图 §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 之前。 找一个有向图的一个拓扑序列的过程称为拓扑排序。 假定计算机软件专业的课程之间存在下述关系：
课程代号课程名称 前导课程 C1 高等数学 无 c① C③ e 程序设计语言 无 c@ C3 数据结构 C2 5-14课程之间先后关系有向图 C4 编译原理 C2,C3 C5 操作系统 C3,C6 C6 计算机组成原理C7 C7 普通物理 0 课程之间的先后关系可用有向图表示，如图5-14所示。 对这个有向图进行拓扑排序可得到一个拓扑序列：C1,C2,C7,C6,C3,C4, C5。也可得到另一个拓扑序列C1,C7,C2,C3,C6,C4,C5。学生按照任何一个 拓扑序列都可以顺利地进行课程学习。 下面给出有向图拓扑排序算法的基本步骤： ①从图中选择一个入度为0的顶点，输出该顶点： ②从图中删除该顶点及其相关联的弧： ③重复执行①、②直到所有顶点均被输出，拓扑排序完成或者图中再也没有入 度为0的顶点（此种情况说明原有向图含有环）。 可以证明，任何一个无环有向图，其全部顶点都可以排成一个拓扑序列。而且 其拓扑序列不一定是唯一的。 下面以图5-15为例说明拓扑排序过程
课程代号 课程名称 前导课程 C1 高等数学 无 C2 程序设计语言 无 C3 数据结构 C2 5-14 课程之间先后关系有向图 C4 编译原理 C2，C3 C5 操作系统 C3，C6 C6 计算机组成原理 C7 C7 普通物理 C1 课程之间的先后关系可用有向图表示，如图 5-14 所示。 对这个有向图进行拓扑排序可得到一个拓扑序列：C1，C2，C7，C6，C3，C4， C5。也可得到另一个拓扑序列 C1，C7，C2，C3，C6，C4，C5。学生按照任何一个 拓扑序列都可以顺利地进行课程学习。 下面给出有向图拓扑排序算法的基本步骤： ①从图中选择一个入度为 0 的顶点，输出该顶点； ②从图中删除该顶点及其相关联的弧； ③重复执行①、②直到所有顶点均被输出，拓扑排序完成或者图中再也没有入 度为 0 的顶点（此种情况说明原有向图含有环）。 可以证明，任何一个无环有向图，其全部顶点都可以排成一个拓扑序列。而且 其拓扑序列不一定是唯一的。 下面以图 5-15 为例说明拓扑排序过程
e1(C② e5 C①e2 -C6A e7 C6 3A (a)有向图 (6)邻接表 图5-15有向图及入度邻接表 首先C1、C4的入度都为0，选C1,删除C1及其边el、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。 下面以邻接表作存储结构，给出拓扑排序的实现。算法设置一个链栈，将所有 入度为0的顶点压入该栈。找入度为0的顶点，只要从栈顶弹出一个元素即可。删 除边的操作转化为将为该顶点为弧尾，所有相应弧头的入度减l。在：adj_list中 增加一个域in,以表示入度。 拓扑排序算法如下： procedure top_sort(g:adj_list); /求出图g的拓扑序列，g采用邻接表，s一链栈，用以存放入度为0的顶 点// begin init_.lstack(s):/初始化栈s/ fori:=1 to n do/将g中入度为0顶点入栈s// if g[i].in=0
(a)有向图 (b)邻接表 图 5-15 有向图及入度邻接表 首先 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。 下面以邻接表作存储结构，给出拓扑排序的实现。算法设置一个链栈，将所有 入度为 0 的顶点压入该栈。找入度为 0 的顶点，只要从栈顶弹出一个元素即可。删 除边的操作转化为将为该顶点为弧尾，所有相应弧头的入度减 1。在:adj_list 中 增加一个域 in，以表示入度。 拓扑排序算法如下： procedure top_sort(g:adj_list); //求出图 g 的拓扑序列，g 采用邻接表，s 一链栈，用以存放入度为 0 的顶 点// begin init_lstack(s); //初始化栈 s// for i:=1 to n do //将 g 中入度为 0 顶点入栈 s// if g[i].in=0
then push(s,g[i].vertex); m:=0: while not empty(s)do v:=top(s) pop(s); write(g[v].vertex):/输出一个拓扑序列中顶点/ m:=m+1;/已输出顶点个数加1/ p:=g[v].link; while p<>nil do [p t.vertex].in:=g[p t.vertex].in-1: ifg[p↑.vertex]..in=o then push(s,p↑t.vertex);/新的入度为0顶点入栈/ p:=p↑.next] ifm<n then write('该有向图中含有环') end; 拓扑排序算法的时间复杂度为0(n+e)。 小结 本章主要讨论图这一重要的数据结构。图不同于线性结构，也不同于树形结构。 图包含若干个顶点，且其中任何两个顶点都可能存在邻接关系，这种关系用边或弧 表示。 图在存储结构主要有两种：邻接矩阵和邻接表。对于网还要存储所有权值
then push(s,g[i].vertex); m:=0; while not empty(s) do [ v:=top(s); pop(s); write(g[v].vertex); //输出一个拓扑序列中顶点// m:=m+1; //已输出顶点个数加 1// p:=g[v].link; while p<>nil do [p↑.vertex].in:=g[p↑.vertex].in-1; if g[p↑.vertex].in=0 then push(s,p↑.vertex); //新的入度为 0 顶点入栈// p:=p↑.next] ] if m<n then write('该有向图中含有环') end; 拓扑排序算法的时间复杂度为 O（n+e）。 小 结 本章主要讨论图这一重要的数据结构。图不同于线性结构，也不同于树形结构。 图包含若干个顶点，且其中任何两个顶点都可能存在邻接关系，这种关系用边或弧 表示。 图在存储结构主要有两种：邻接矩阵和邻接表。对于网还要存储所有权值
图有一种重要的运算一一遍历，即访问图中每个顶点一次且仅一次。遍历的基 本方法有两种：深度优先搜索和广度优先搜索。这两种方法的基本思想非常重要， 利用它们可以解决一些其它问题。两种搜索方法的具体实现依赖于图的存储结构。 图有着广泛的应用背景。本章着重介绍了两个实际应用：最小生成树和拓扑排 序。从这两个例子可以看出，图的应用方式是非常灵活的。 上一页且录下一页
图有一种重要的运算——遍历，即访问图中每个顶点一次且仅一次。遍历的基 本方法有两种：深度优先搜索和广度优先搜索。这两种方法的基本思想非常重要， 利用它们可以解决一些其它问题。两种搜索方法的具体实现依赖于图的存储结构。 图有着广泛的应用背景。本章着重介绍了两个实际应用：最小生成树和拓扑排 序。从这两个例子可以看出，图的应用方式是非常灵活的。 上一页 目 录 下一页