数据结构课件chap007章节幻灯片.ppt

V0 V1 V2 V3 V4 V5 100 10 30 60 20 50 5 10 ∞ ∞ 10 ∞ 30 100 ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ ∞ 50 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 10 ∞ ∞ ∞ 20 ∞ 60 ∞ ∞ ∞ ∞ ∞ ∞ 终点 从V0到各终点的最短路径求解过程 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] 求每一对顶点之间的最短路径 弗洛伊德算法O(n3)的基本思想： 从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径。 可以重复执行迪杰斯特拉O(n2) 若vi,vj存在，则存在路径{vi,vj} // 路径中不含其它顶点 若vi,v1,v1,vj存在，则存在路径{vi,v1,vj} // 路径中所含顶点序号不大于1 若{vi,…,v2}, {v2,…,vj}存在， 则存在一条路径{vi, …, v2, …vj} // 路径中所含顶点序号不大于2 … 依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。 弗洛伊德算法 定义一个n阶方阵序列：D(-1), D(0), D(1),… D(n-1) 其中，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)[i][j]是从vi到vj的中间节点的序号 不大于1的最短路径长度 D(k)[i][j]是从vi到vj的中间节点的序号 不大于k的最短路径长度 D(n-1)[i][j]就是从vi到vj的最短路径长度 弗洛伊德算法—示例 a c b 6 4 11 3 2 0 4 11 6 0 2 3 ∞ 0 D D(-1) D(0) D(1) D(2) 0 1 2 0 1 2 0 1 2 0 1 2 0 0 4 11 0 4 11 0 4 6 0 4 6 1 6 0 2 6 0 2 6 0 2 5 0 2 2 3 ∞ 0 3 7 0 3 7 0 3 7 0 P P(-1) P(0) P(1) P(2) 0 1 2 0 1 2 0 1 2 0 1 2 0 ab ac ab ac ab abc ab abc 1 ba bc ba bc ba bc bca bc 2 ca ca cab ca cab ca cab 　1. 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。 　2. 熟练掌握图的两种有哪些信誉好的足球投注网站路径的遍历：遍历的逻辑定义、深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站的算法。 在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。 　 3. 应用图的遍历算法求解各种简单路径问题。 　　4. 理解教科书中讨论的各种图的算法。 设置一个辅助数组，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边： struct { VertexType adjvex; // U集中的顶点序号 VRType lowcost; // 边的权值 } closedge[MAX_VERTEX_NUM]; a b c d e g f 19 5 14 18 27 16 8 21 3 a e 12 d c b 7 a a a 19 14 18 14 例如: e 12 e e 8 16 8 d 3 d d 7 21 3 c 5 5 void MiniSpanTree_P(MGraph G, VertexType u) { //用普里姆算法从顶点u出发构造网G的最小生成树 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; ++j ) // 辅助数组初始化 if (j!=k) closedge[j] = {