第7章讲 图.ppt

1. 初始化两个辅助数组lowcost和adjvex； 2. 输出顶点u0，将顶点u0加入集合U中； 3. 重复执行下列操作n-1次 3.1 在lowcost中选取最短边，取adjvex中对应的顶点序号k； 3.2 输出顶点k和对应的权值； 3.3 将顶点k加入集合U中； 3.4 调整数组lowcost和adjvex； Prim算法——伪代码 7.4 最小生成树 克鲁斯卡尔（Kruskal）算法 基本思想：设无向连通网为G＝(V, E)，令G的最小生成树为T＝(U, TE)，其初态为U＝V，TE＝{ }，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。 7.4 最小生成树 克鲁斯卡尔（Kruskal）算法 1. 初始化：U=V；TE={ }； 2. 重复下述操作直到T中的连通分量个数为1： 2.1 在E中寻找最短边(u，v); 2.2 如果顶点u、v位于T的两个不同连通分量，则 2.2.1 将边(u，v)并入TE； 2.2.2 将这两个连通分量合为一个； 2.3 标记边(u，v)，使得(u，v)不参加后续最短边的选取； Kruskal算法的基本思想用伪代码描述如下： 关键：如何判别被考察边的两个顶点是否位于两个连通分量 7.4 最小生成树 25 12 34 19 26 46 38 17 25 A B E D C F A B E D C F 连通分量＝{A}, {B}, {C}, {D}, {E}, {F} 7.4 最小生成树 25 12 34 19 26 46 38 17 25 A B E D C F A B E D C F 连通分量＝{A}, {B}, {C}, {D}, {E}, {F} 12 连通分量＝{A}, {B, E}, {C}, {D}, {F} 7.4 最小生成树 25 12 34 19 26 46 38 17 25 A B E D C F A B E D C F 连通分量＝{A, F}, {B, E}, {C}, {D} 12 连通分量＝{A, F}, {B, E}, {C, D} 17 7.4 最小生成树 25 12 34 19 26 46 38 17 25 A B E D C F A B E D C F 连通分量＝{A}, {B, E}, {C}, {D}, {F} 12 连通分量＝{A, F}, {B, E}, {C}, {D} 19 17 7.4 最小生成树 25 12 34 19 26 46 38 17 25 A B E D C F A B E D C F 连通分量＝{A, F}, {B, E}, {C, D} 12 连通分量＝{A, F, C, D}, {B, E} 19 17 25 7.4 最小生成树 25 12 34 19 26 46 38 17 25 A B E D C F A B E D C F 连通分量＝{A, F, C, D}, {B, E} 12 连通分量＝{A, F, C, D, B, E} 19 17 25 26 7.4 最小生成树 1. 图的存储结构：因为Kruskal算法是依次对图中的边进行操作，因此考虑用边集数组存储图中的边，为了提高查找速度，将边集数组按边上的权排序。 数据结构设计 7.4 最小生成树 2. 连通分量。Kruskal算法实质上是使生成树以一种随意的方式生长，初始时每个顶点构成一棵生成树，然后每生长一次就将两棵树合并，到最后合并成一棵树。 因此，可以设置一个数组parent[n]，元素parent[i]表示顶点i的双亲结点，初始时，parent[i]= -1，表示顶点i没有双亲，即该结点是所在生成树的根结点；对于边(u, v)，设vex1和vex2分别表示两个顶点所在树的根结点，如果vex1≠vex2，则顶点u和v必位于不同的连通分量，令parent[vex2] = vex1，实现将两棵树合并。 求某顶点v所在生成树的根结点只需沿数组v = parent[v]不断查找v的双亲，直到parent[v]等于-1。 数据结构设计 7.4 最小生成树 1. 初始化辅助数组parent[n]；num = 0； 2. 依次考查每一条边for (i = 0; i arcNum; i++) 2.1 vex1 = edge[i].f