拓扑排序 - 拓扑排序.ppt

文档介绍：§ 拓扑排序( Topological Sort ) ?拓扑排序是一种对非线性结构的有向图进行线性化的重要手段。? AOV ( Activity On Vertex )网:就是顶点代表活动,边(狐)表示活动的优先关系的有向图。? AOV 网可以解决的两个问题: 1 )判定工程的可行性。若有回路则工程无法结束(不可行); 2 )确定各项活动在整个工程执行中的先后顺序(即拓扑排序序列)。课程编号课程名称必要的先修课程编号 C1程序设计基础无 C2离散数学 C1 C3数据结构 C1 , C2 C4汇编语言 C1 C5算法分析和设计 C3 , C4 C6计算机组成原理 C11 C7编译原理 C3 , C5 C8操作系统 C3 , C6 C9高等数学无 C10 线性代数 C9 C11 普通物理 C9 C12 数值分析 C1 , C9 , C10 c1 c9 c4 c2 c12 c10 c11 c5 c3 c6 c7 c8 将表转换成图拓扑排序的步骤: (1)从图中选择一个入度为 0的顶点且输出之; (2)从图中删掉该顶点及其所有以该顶点为弧尾的弧; 反复执行这两个步骤,直到所有的顶点都被输出, 输出的序列就是这个无环有向图的拓扑序列。 c1 c9 c4 c2 c12 c10 c11 c5 c3 c6 c7 c8 拓扑序列: c1,c9 c4 c2 c12 c10 c11 c5 c3 c6 c7 c8 拓扑序列: c1,c9 c4 c2 c12 c10 c11 c5 c3 c6 c7 c8 拓扑序列: c1,c9 c4 c2 c12 c10 c11 c5 c3 c6 c7 c8 拓扑序列: c1,c9,c4,c2,c10,c11 c12 c5 c3 c6 c7 c8 拓扑序列: c1,c9,c4,c2,c10,c11 c12 c5 c3 c6 c7 c8 拓扑序列: c1,c9,c4,c2,c10,c11,c3,c12,c6