数据结构第七章图试卷.ppt

假设已求得矩阵 D(k-1)，求D(k) 从顶点vi到vj中间顶点序号不大于k的最短路径有两种情况： 1）不经vk，则D(k)[i][j] = D(k-1)[i][j] 没有通路或有通路但经vk长度值较大 2）经vk，则 D(k)[i][j] D(k-1)[i][j] 若不小于，则属1）情况 而路径D(k)[i][j]为vi经vk到 vj的中间顶点序号不大于k的最段路径由两段组成；一段是从vi到 vk中间顶点序号不大于k-1的最段路径，一段是从vk到 vj中间顶点序号不大于k-1的最段路径。 即： D(k)[i][j] = D(k-1)[i][k] + D(k-1)[k][j] 条件： D(k)[i][j] D(k-1)[i][j] 即： D(k-1)[i][k] + D(k-1)[k][j] D(k-1)[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 举例： A C B 2 6 4 3 11 0 4 11 6 0 2 3 ∞ 0 初始： D(-1) = 路径： AB AC BA BC CA 0 4 6 6 0 2 3 7 0 加入B： D(1) = 路径： AB ABC BA BC CA CAB 0 4 11 6 0 2 3 7 0 加入A： D(0) = 路径： AB AC BA BC CA CAB 0 4 6 5 0 2 3 7 0 加入C： D(2) = 路径： AB ABC BCA BC CA CAB void FLOYD(MGraph G,PathMatrix P[ ],DistancMatrix D) { for ( v = 0 ; v G .vexnum ; ++ v ) for ( w = 0 ; w G .vexnum ; ++w ) { D[ v ][ w ] = G .arcs[ v ][ w ] ; for( u=0 ; uG.vexnum ; ++u ) P[v][w][u] = FALSE ; if ( D[v][w] INFINITY ) { P[v][w][v] = TRUE ; P[v][w][w] = TRUE ; } } for ( u = 0 ; u G.vexnum ; ++u ) for ( v = 0 ; v G.vexnum ; ++v ) for ( w = 0 ; w G.vexnum ; ++ w ) if ( D[v][u] + D[u][w] D[v][w] ) { D[v][w] = D[v][u] + D[u][w] ; for ( i = 0 ; iG.vexnum ; ++ i ) P[v][w][i] = P[v][u][i] || P[u][w][i]; } } 作业：7.1(1)(2)(3),7.10,7.22 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 问题：二叉树按层次遍历 问题：迷宫问题 7.4 图的连通性问题 一、无向图的连通分量和生成树 对无向非连同图进行深度优先遍历 三次调用得到的访问序列为： ALMJBFC DE GKHI A B C D E F G H I J K L M A L J M B F C D E G K H I 生成树：所有顶点均由边连接在一起，但不存在回路的图。 深度优先生成树与广度优先