数据结构课件第七章图幻灯片.ppt

　 3. 应用图的遍历算法求解各种简单路径问题。 　　4. 理解教科书中讨论的各种图的算法。 终点 从v0到各终点的D值和最短路径的求解过程 I=1 I=2 I=3 I=4 I=5 v1 ? ? ? ? ? v2 10 (v0,v2) v3 ? 60 (v0,v2,v3) 50 (v0,v4,v3) v4 30 (v0, v4) 30 (v0,v4) v5 100 (v0,v5) 100 (v0,v5) 90 (v0,v4,v5) 60 (v0,v4,v3,v5) vj v2 v4 v3 v5 S {v0, v2} (v0,v2,v4) {v0,v2,v3,v4} {v0,v2,v3,v4,v5} 求每一对顶点之间的最短路径 弗洛伊德算法的基本思想是： 从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径。 若vi,vj存在，则存在路径{vi,vj} // 路径中不含其它顶点 若vi,v1,v1,vj存在，则存在路径{vi,v1,vj} // 路径中所含中间顶点序号不大于1 若{vi,…,v2}, {v2,…,vj}存在， 则存在一条路径{vi, …, v2, …vj} // 路径中所含中间顶点序号不大于2 … 依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。 弗洛伊德思想可用下式描述: D(-1)[i][j]=arcs[i][j] D(k)[i][j]=Min{ D(k-1)[i][j], D(k-1)[i][k]+D(k-1)[k][j] } 其中:0≤k≤n-1 D(-1),D(0),D(1),…….D(K),……D(n-1)是一个N阶方阵序列 1、D(1)[i][j]是从vi到vj的中间顶点的序号不大 于1的最短路径长度； 2、D(k)[i][j]是从vi到vj的中间顶点的序号不大 于k的最短路径长度； 3、D(n-1)[i][j]就是从vi到vj的最短路径长度； 7、5 有向无环图及其应用 一、定义 一个无环的有向图图称为有向无环图（DAG） 有向无环图是描述含有公共子式的表达 式的的有效工具 有向无环图也是描述一项工程或系统的 进行过程的有效工具 有向无环图的概念 下图给出了有向树、DAG图和有向图的例子，(a)、(b)、(c)都是有向图，(a)、(b)都是DAG图，只有(a)是有向树；可以通过观察图例理解三者之间的联系与区别。 有向无环图表示举例 有向无环图是描述含有公共子式的一类表达式的有效工具。例如对于表达式 ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e) 可以用第四章讨论的二叉树表示为如下图所示的有向树。 有向无环图表示举例(续) 例如对于同样表达式 ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e) 利用有向无环图则可实现对相同子式的共享，从而节省存储空间，下图给出了该表达式的有向无环图。 有向无环图的应用 有向无环图也是描述一项工程或系统进展过程的有效工具。 对整个工程和系统，人们所关心的是两个方面的问题： 一是工程能否顺利进展， 二是预期完成整个工程所必须花费的时间最短； 对应于描述工程进展过程的有向无环图而言，即为进行拓扑排序和关键路径的操作。 AOV网及应用举例 在有向图中用顶点表示活动而用弧表示活动间的优先关系，人们称该有向图为顶点表示活动的网（activity on vertex network），简称为AOV网。 例如，软件工程专业的学生必须学习一组基础课程和专业基础课程。其中有些基础课程是独立于其它课程的，如高等数学和高级语言程序设计；有些课程必须在学完其先导课程后才能开始学习，如在学完高级语言程序设计和离散数学之后才能学习算法与数据结构。 若用顶点表示课程，用弧表示课程之间的先后修关系（即弧i，j表示课程j的先修课程是i）。 AOV网的应用举例示图 拓扑排序 问题: 假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。 检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。 何谓“拓扑排序”？ 对有向图进行如下操作： 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。 例如：对于下列有向图 B D A C 可求得拓扑有序序列： A B C D 或 A C B D 由此所得顶点的线性