chap7图1.ppt

第七章 图 四类基本结构： 7.1 图的定义与基本术语 图的抽象数据类型定义 7.2 图的存储结构 7.3 图的遍历 7.4 图的应用 7.4.2 拓扑排序 1. 拓扑排序—问题引入 2. 拓扑排序 在AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件,此AOV网络所代表的工程是不可行的。 例如，对学生选课工程图进行拓扑排序， 得到的拓扑有序序列为(不一定唯一） C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 3. 拓扑排序 三、拓朴排序算法描述 三、拓朴排序算法描述 三、拓朴排序算法描述 4、拓朴排序算法描述 5. 逆拓扑排序 7.4.3 最短路径  本章主要内容 C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C2, C3 C5 算法语言 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计算机原理 C8 例如：计算机专业学生的学习就是一个工程 学生课程学习工程图 C1 C8 C2 C3 C9 C6 C7 C4 C5 检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。 例如： 可求得拓扑有序序列： A B C D 或 A C B D B D A C 存在回路，活动互 为前驱。无法执行！ 何谓“拓扑排序”？ 对有向图进行如下操作： 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列. C1 C8 C2 C3 C9 C6 C7 C4 C5 如何进行拓扑排序？ Ⅰ.从有向图中选取一个没有前驱的顶点, (入度为0 的顶点)，并输出之； Ⅱ.从有向图中删去此顶点以及所有以它为尾的弧； 重复上述两步，直至图中不存在没有前驱的顶点 所有顶点已输出，拓朴排序完成，说明图中不存在有向回路或 剩余的顶点入度都不为0（此时图中有环，拓朴排序不能进行下去）。 拓扑排序例如： C D A G F B H E A C B H D G F E 没有前驱的顶点 ?? 入度为零的顶点 删除顶点及它的出弧 ?? 弧头顶点的入度减1 在算法中需要用定量的描述替代定性的概念 5 4 3 2 1 6 V5 V4 V3 V2 V1 V6 2 3 2 3 5 ∧ ∧ 4 4 ∧ ∧ 5 ∧ ∧ V1 V6 V4 V2 V5 V3 V6 V1 V4 V5 V3 V2 拓扑序列： V1 V2 V3 V4 V5 V6 indegree 0 0 2 2 2 2 V1 V6 V4 V2 V5 V3 5 4 3 2 1 6 V5 V4 V3 V2 V1 V6 2 3 2 3 5 ∧ ∧ 4 4 ∧ ∧ 5 ∧ ∧ V6 V1 V4 V5 V3 V2 拓扑序列： V1 V2 V3 V4 V5 V6 indegree 0 0 2 2 2 2 5 4 3 2 1 0 栈 1 1 1 1 0 0 0 0 1 6 4 3 5 2 void TopSort_Stack(ALGraph G,int indegree[]) { ArcNode *p; int i,count=0; SqStack S; InitStack(S); for(i=1;i=G.vernum;i++) if(indegree[i]==0) Push(S,i); while(!StackEmpty(S)) { printf(%c ,G.vertex[