数据结构第七章图解读.ppt

举例： 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 生成树：所有顶点均由边连接在一起，但不存在回路的图。 深度优先生成树与广度优先生成树 生成森林：非连通图每个连通分量的生成树一起组成非连通图的生成森林。 说明 一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图 一个有n个顶点的连通图的生成树有n-1条边 生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路 含n个顶点n-1条边的图不一定是生成树 建立非连通图G的深度优先生成森林 void DFSForest ( Graph G , CSTree T ) { T = NULL ; for ( v = 0 ; v G .vexnum ; ++v ) visited[ v ] = FALSE ; for ( v = 0 ; v G .vexnum ;++v ) if ( !visited[ v ] ) { p = ( CSTree ) malloc ( sizeof ( CSNode ) ) ; *p = { GetVex ( G , v ) , NULL , NULL } ; if ( !T ) T = p ; else q - nextsibling = p ; q = p ; DFSTree ( G , v , p ) ; } } 从第v个顶点出发深度优先遍历图G，建立以T为根的生成树 void DFSTree (Graph G , int v , CSTree T ) { visited[ v ] = TRUE ; first = TRUE ; for(w