§6.6拓扑排序 目的 根据结点间的关系求得结点的一个线性排列 在有关工程进度/次序规划之类问题中,有着大量应用。 一般的大型工程,都可以划分为多个工序/步骤/子工程,这 些工序有的可独立进行,但大多数和其他工序关联,即某工 序的进行,要等到其他一些工序的完成才能开始。这类问题 都可归结到拓扑排序
1 §6.6 拓扑排序 • 目的 – 根据结点间的关系求得结点的一个线性排列。 • 在有关工程进度/次序规划之类问题中，有着大量应用。 – 一般的大型工程，都可以划分为多个工序/步骤/子工程，这 些工序有的可独立进行，但大多数和其他工序关联，即某工 序的进行，要等到其他一些工序的完成才能开始。这类问题 都可归结到拓扑排序
§6.6.1拓扑序列与A0V网 对有向图G,若它的一个结点序列 LS 满足这样的条件:是G的边时,在LS中v位于y之 前(即j),否则在LS中v;与v的前后次序任意,则称LS为 图G的一个拓扑序列,求拓扑序列的操作称为拓扑排序 (Topological Sorting) 某一图的拓扑序 列可能不唯 2
2 §6.6.1 拓扑序列与AOV网 • 对有向图G，若它的一个结点序列 LS：v1 , v2 ,..., vn 满足这样的条件：是G的边时，在LS中vi位于vj之 前（即i<j），否则在LS中vi与vj的前后次序任意，则称LS为 图G的一个拓扑序列，求拓扑序列的操作称为拓扑排序 （Topological Sorting）。 某一图的拓扑序 列可能不唯一
§6.6.1拓扑序列与A0V网 拓扑排序主要用在一类称为AOV网( Activity on Vertex networks)的有向图中 AOV网是给有向图的结点与边赋予一定的语义的图,具 体地: 结点——代表活动。如工程中的工序/任务、状态等 边一代表活动之间的进行次序。边<表示活动先于进行 AOV网常用来表达流程图,如一个工程中各子任务间的 流程图、产品生产加工流程图、程序流程图、信息(数据) 流程图、活动安排流程图等
3 §6.6.1 拓扑序列与AOV网 • 拓扑排序主要用在一类称为AOV网（Activity on Vertex networks）的有向图中。 • AOV网是给有向图的结点与边赋予一定的语义的图，具 体地： – 结点──代表活动。如工程中的工序/子任务、状态等 – 边 ──代表活动之间的进行次序。边表示活动i先于j进行。 • AOV网常用来表达流程图，如一个工程中各子任务间的 流程图、产品生产加工流程图、程序流程图、信息（数据） 流程图、活动安排流程图等
§6.6.1拓扑序列与AOV网 学生的选课次序就是一个AOV网应用问题。例如,假定某计算机专 业的主要课程如表6-2所示,则对应的AOV网如图6-1所示。 表6-2课程进行关系 课程编号 课程名称 先行课 高等数学 离散数学 3 高级语言 4 数据结构 3,2 操作系统 4,6 计算机组成原理2 数据库原理 编译原理 4,7 图-对应的AOV网9 计算机网络 人工智能原理 1,2,3 软件工程 7.9 4
4 §6.6.1 拓扑序列与AOV网 • 学生的选课次序就是一个AOV网应用问题。例如， 假定某计算机专 业的主要课程如表6-2所示，则对应的AOV网如图6-1所示。 10 1 2 3 9 6 4 5 7 8 11 图 - 对应的AOV网 10 人工智能原理 1，2，3 7．9 表 6-2 课程进行关系 课程编号 课程名称 先行课 1 高等数学 - 2 离散数学 - 3 高级语言 - 4 数据结构 3，2 5 操作系统 4，6 6 计算机组成原理 2 7 数据库原理 5 8 编译原理 4，7 9 计算机网络 5，1 11 软件工程
§6.6.1拓扑序列与AOV网 ·图6-1可有多个拓扑序列,下面给出了它的两个 02v6 不同的拓扑序列: 12346597811 12346579811 如果采用串行修课方式,则可完全按拓扑序列进 行,但往往是一段时间内需同时修多门课,这就需 图对应的AOV网 识别出哪些课可同时修,这是一个识别可并行成份 的问题。例如,在图6-1中,可并行的课程有 1,2,3)→(46,10)→(5)→(9,7)→(8,1)等几组
5 §6.6.1 拓扑序列与AOV网 • 图 6-1可有多个拓扑序列，下面给出了它的两个 不同的拓扑序列： 1 2 3 4 6 5 9 7 8 11 1 2 3 4 6 5 7 9 8 11 • 如果采用串行修课方式，则可完全按拓扑序列进 行，但往往是一段时间内需同时修多门课，这就需 识别出哪些课可同时修，这是一个识别可并行成份 的问题。例如，在图 6-1中，可并行的课程有 (1,2,3)→(4,6,10)→(5) →(9,7)→(8,11)等几组。 10 1 2 3 9 6 4 5 7 8 11 图 - 对应的AOV网
§6.6.2拓扑排序算法与实现 (一)基本方法 ·进行拓扑排序的基本方法是简单而直观的,其包含下列几个步骤: [1]从有向图中找一个没有前趋的结点v,若v不存在,则表明不可进 行拓扑排序(图中有环路),结束(不完全成功); [2]将v输出; [3]将v从图中删除,同时删除关联于v的所有的边 「4]若图中全部结点均已输出,则结束(成功),否则转[]继续进行
6 §6.6.2 拓扑排序算法与实现 (一）基本方法 • 进行拓扑排序的基本方法是简单而直观的，其包含下列几个步骤： [1] 从有向图中找一个没有前趋的结点v，若v不存在，则表明不可进 行拓扑排序（图中有环路），结束（不完全成功）； [2] 将v输出； [3] 将v从图中删除，同时删除关联于v的所有的边 [4] 若图中全部结点均已输出，则结束（成功），否则转[1]继续进行
§6.6.2拓扑排序算法与实现 (一)基本方法 通过对此方法做适当扩充,就可在求拓扑序列的过程中 标识出可并行活动(结点) 具体做法是,初始时将所有无前趋结点标为一组可并行 结点。然后,每次执行步骤[3]后,将新产生的无前趋结点 标为新的一组可并行结点。为了将同组并行结点连续排列, 在步骤[中应优先选取并行组号与上次选择结点的并行组 号相同的结点(若有的话)
7 §6.6.2 拓扑排序算法与实现 (一）基本方法 • 通过对此方法做适当扩充，就可在求拓扑序列的过程中 标识出可并行活动（结点）。 • 具体做法是，初始时将所有无前趋结点标为一组可并行 结点。然后，每次执行步骤[3]后，将新产生的无前趋结点 标为新的一组可并行结点。为了将同组并行结点连续排列， 在步骤[1]中应优先选取并行组号与上次选择结点的并行组 号相同的结点（若有的话）
§6.6.2拓扑排序算法与实现 (二)数据结构的选取 邻接表的图结点的定义修改为: template struct TGrphNode long noded;∥结点编号 TElem nodelnfo;∥结点信息 long in Degree;∥结点的入度 TGrphedge* firstOutEdge;第一条出边的指针
8 §6.6.2 拓扑排序算法与实现 (二）数据结构的选取 • 邻接表的图结点的定义修改为： template struct TGrphNode { long nodeIdx; //结点编号 TElem nodeInfo; //结点信息 long inDegree; //结点的入度 TGrphEdge * firstOutEdge; //第一条出边的指针 };
§6.6.2拓扑排序算法与实现 (二)数据结构的选取 而图边的定义仍为: template struct TGrphEdge long edgeEndldx;∥边终点编号 TEdgelnfo edgeInfo;,边信息 TGrphedge*next;/链指针
9 §6.6.2 拓扑排序算法与实现 (二）数据结构的选取 • 而图边的定义仍为： template struct TGrphEdge { long edgeEndIdx; //边终点编号 TEdgeInfo edgeInfo; //边信息 TGrphEdge *next; //链指针 };
§6.6.2拓扑排序算法与实现 (二)算法实现 for(每个结点V if(入度为0)V进栈; while(栈不空) 从栈中弹出一个元素送v 输出v 求出v的第1个直接可达邻接点w; while(w存在) 将w的入度域减1 if(w的入度域为0)w进栈; 求出ⅴ的下个直接可达邻接点w; 3 //while //while
10 §6.6.2 拓扑排序算法与实现 (二）算法实现 for (每个结点v) if (v入度为0) v进栈; while (栈不空) { 从栈中弹出一个元素送v; 输出v; 求出v的第1个直接可达邻接点w; while (w存在) { 将w的入度域减1; if (w的入度域为0) w进栈; 求出v的下个直接可达邻接点w; } //while } //while