《数据结构精品教学》图的应用（蓝底）.ppt

2、求每对点之间的最短路径（Floyed算法） 前面已经可以求一个点到其余各点的最短路径，现在要求每对点间最短路径，一个直接办法是？ 最直观办法是：轮流以每个点为源点， 反复执行Dijkstra算法n次，就能求得每个点到其余点的最短路径。 另一种Floyed算法：概念更简单。其基本思想为：递推地产生一个矩阵序列A(-1)，A(0)，A(1)，…，A(n-1) ，其中初始的 A(-1)[i][j]是图的邻接矩阵，其余的 A(k)[i][j]=min{A(k-1)[i][j]， A(k-1)[i][k]＋A(k-1)[k][j]} 具体地说，第一次把V0作为中间点，用上式检查矩阵A(-1)中除V0对应行和列以外的每个元素，作相应修改，得矩阵A(0)。 第二次把V1作为中间点，用上式检查矩阵A(0)中除V1对应行和列以外的每个元素，作类似检查和修改，得矩阵A(1)。…… 直到每个点都做过一次中间点，最后矩阵A(n-1) 给出任意两点间的最短路径。 实例：通常我们把计划、施工过程、生产流程、程序流程等都看作一个大工程，大工程常常被划分成许多小的子工程，这些子工程称为活动。这些活动之间可能有一定的先后关系。当这个工程中所有活动都完成时，整个工程完成。 例如：计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，图8-9给出了若干门所开设的课程，其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完算法语言及离散数学，而开设离散数学则必须学完高等数学和程序设计基础。 为了反映整个工程中各活动之间的先后关系，我们可以采用有向图来表示。 8.3 拓扑排序 学生选修课程问题 顶点——表示课程 有向边——表示先决条件，若课程i是j的先决条件，则图中有边i,j 学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业——拓扑排序 有向图中，顶点表示活动，有向边表示活动的优先关系，如Vi,Vj表示活动Vi必须在Vj之前完成。 这种有向图叫做顶点活动网，简称AOV网。 8.3 拓扑排序 AOV网——有向无环图 有向：清楚地表示出各活动先后关系。前驱、后继 无环：指图中无回路。如果出现回路，则回路上活动无法进行 由于AOV网中无回路，因此可以把所有活动排成一个线性序列，并保证各活动按先后顺序排列。这种把有向图线性化的过程就叫做拓扑排序。得到的线性序列叫做拓扑序列。 对图8-10进行拓扑排序 结果可以有多个，因此拓扑序列不唯一。 实际意义：整个工程若按拓扑序列的顺序依次进行，则每项活动开始时，其前驱活动已完成，各活动间就不会发生冲突。 基本思想： （1）选择一个入度为0的点并输出 （2）从图中删除该点及其所有出边 反复执行以上两步，直到所有点都输出，则拓扑排序完成。 或者剩下的点中没有入度为0者，则说明图中有回路。 拓扑排序算法 C7 C1 C2 C4 C9 C12 C11 C10 C6 C8 C5 C3 表示必修课程优先关系的有向图（AOV网） 必修课程关系表 课程编号 课程名称 先决条件 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 数值分析 C9 ，C10，C1 举例： C7 C1 C2 C4 C9 C12 C11 C10 C6 C8 C5 C3 拓扑排序： 拓扑序列为： C1