数据结构课件第7章图.ppt

* 假设 G = ( V, E ) 是一个连通网，T=(U, TE) 是 G 的最小生成树。初始T 为空树．U(T)=Φ,TE(T)=Φ。重复执行⑴,⑵操作： ⑴选择G=(V,E)的任意顶点为树根,且U(T)=该树根。 ⑵向T中添加一条边，该边的一个顶点在树Ｔ中，另一顶点在树外（V(G))中,且该边权值为E(G)中最小者。 ⑶加入n-1 条边后，这时U =V。则 T = ( U, TE ) 为 G 的最小生成树。 2. 普里姆 (Prim) 算法 (1) 算法思想 adjvex lowcost 辅助数组 closedge 分量结构 显然： Closedge [i-1].lowcost = Min { cost ( u, v ) | u ∈U } 其中：cost (u, v) 表示赋于边 (u, v) 的权。 为实现此算法，需附设一个辅助数组 closedge 记录从 U 到 V–U 具有最小代价的边。对每个顶点 vi ∈V-U，closedge[i-1]记录所有与vi邻接的,从U到V-U的那组边中最小边信息 ，它包括两个域：一个是 adjvex 域，记录最小边在 U 中的那个顶点；另一个是 lowcost 域， 存储最小边的权值。 * 构造最小生成树时辅助数组中各分量的变化情况 closedge i adjvex lowcost adjvex lowcost adjvex lowcost adjvex lowcost adjvex lowcost adjvex lowcost 1 2 3 4 5 U V-U k v1 v2 v4 v3 v5 v6 6 5 1 5 5 6 4 3 2 6 v1 6 v1 1 v1 5 {v1} { v2, v3, v4, v5, v6 } v1 ∞ v1 ∞ v1 v2 v4 v3 v5 v6 6 5 1 5 5 6 4 3 2 6 2 0 0 0 0 0 {v1, v3} { v2, v4, v5, v6 } v1 v2 v4 v3 v5 v6 6 5 1 5 5 6 4 3 2 6 v3 5 v1 5 v3 6 v3 4 5 0 0 0 0 {v1, v3, v6} { v2, v4, v5 } v1 v2 v4 v3 v5 v6 6 5 1 5 5 6 4 3 2 6 v3 5 v6 2 v3 6 3 v1 v2 v4 v3 v5 v6 6 5 1 5 5 6 4 3 2 6 0 0 0 {v1, v3, v6, v4} { v2, v5 } v3 5 v3 6 1 0 0 {v1, v3, v6, v4, v2} {v5} v1 v2 v4 v3 v5 v6 6 5 1 5 5 6 4 3 2 6 v2 3 4 {v1, v3, v6, v4, v2, v5} { } 0 v1 v2 v4 v3 v5 v6 6 5 1 5 5 6 4 3 2 6 v1 v2 v4 v3 v5 v6 6 5 1 5 5 6 4 3 2 6 v1 v2 v4 v3 v5 v6 1 v1 v2 v4 v3 v5 v6 1 4 v1 v2 v4 v3 v5 v6 1 4 2 v1 v2 v4 v3 v5 v6 1 5 4 2 v1 v2 v4 v3 v5 v6 1 5 4 3 2 * 普里姆 (Prim) 算法构造最小生成树的过程 (2) 算法编写 // struct { // VertexType adjvex; // 存储该边依附的在 U 中的顶点 // int lowcost; // 存储该边上的权 // } closedge[ MAX_VERTEX_NUM ]; k = LocateVex ( gn, u ); for ( i = 0; i gn.vexnum; ++i ) // 辅助数组初始化 if ( i != k ) closedge[i] = { u, gn.arcs[k][i].adj }; // { adjvex, lowcost } closedge[k].lowcost = 0; // 初始，U = {u} // closedge[k].lowcost = 0，表示顶点 k 并入 U * void MiniSpanTree_PRIM ( AdjMatrix gn, VertexData u ) { // 用 Prim 算法从第 u 个顶点出发构造网 G 最小生成树 T，输出 T // 各边。记录从顶点集 U 到 V-U 代价最小边的辅助