数据结构之图课件(编辑修改稿)

数据结构之图课件(编辑修改稿)内容摘要：

)。 对辅助数组初始化时间为 O(n)。 因此，当用邻接表作为图的存储结构时，广度优先搜索图的时间复杂性为 O(e+n)。 返回 最小生成树 在一个无向连通图 G中，如果取它的全部顶点和一部分边构成一个子图 G’，若边集 E(G’)中的边刚好将图的所有顶点连通但又不形成环路，我们就称子图 G’是原图 G的生成树（ Spanning tree）。 生成树有如下特点：任意两个顶点之间有且仅有一条路径；如果再增加一条边就会出现回路；如果去掉一条边此子图就会变成非连通图。 一个有 n 个顶点的完全图，一共存在 n(n2)种不同的生成树。 对于带权的连通图（连通网） G，其生成树也是带权的。 我们把生成树各边的权值总和称为该生成树的权。 并且将权最小的生成树称为最小生成树（ Minimum Spanning Tree）。 具有 n个顶点的连通图的生成树具有 n1条边（少于此边数不可能将各顶点连通，多于此边数则必然要出现回路）。 图 图 G 及其生成树 无向连通图 G ⑤ ④ ① ② ③ 0 6 5 6 6 5 5 1 3 4 2 ⑤ ④ ① ② ③ 0 6 6 5 5 4 生成树 图 图 G 及其生成树 生成树 ⑤ ④ ① ② ③ 0 6 1 3 4 2 ⑤ ④ ① ② ③ 0 5 1 3 4 2 最小生成树 (prim)算法 基本思想： 假设 N=（ V， E）是连通的， TE是N上最小生成树中的边集。 首先从某一结点 U。 开始， 令 U={U。 }， TE=， 重复下列工作：从一个顶点在 U中，另一个顶点在 VU中，找权值最小的边 U。 ， V。 , 并加入集合 TE中，同时， V。 加入 U 中。 直到 U=V为止。 此时，有 n1条边， T=（ V， TE）为 N的最小生成树。 假设 G=(V, E)是一个具有 n 个顶点的连通网络， T=(U,TE)是 G的最小生成树，其中 U是 T的顶点集， TE是 T的边集， U和 TE的初值均为空。 算法开始时，首先从 V中任取一个顶点（假定为 V。 ），将此顶点并入 U中，此时最小生成树顶点集 U={V。 }； 然后 ,从那些其一个端点已在 U中，另一个端点在 VU中，找一条最短（即权值最小）的边，假定该边为 (Vi, Vj), 其中 Vi∈ U， Vj∈ VU, 并把该边 (Vi, Vj)和顶点 Vi分别并入 T的边集 TE和顶点 集 U中 . 如此进行下去，每次往生成树里并入一个顶点和一条边，直到 n1次后，把所有 n 个顶点都并入生成树 T的顶点集 U中，此时 U=V， TE中包含有（ n1）条边； 这样， T就是最后得到的最小生成树。 普里姆算法中每次选取的边两端，总是一个在 U 中，一个在 VU 中，故这个边选取后一定能将未连通顶点连通而又保证不会形成环路。 图 普里姆算法例子 8 3 5 ⑤ ④ ① ② ③ 9 14 17 13 12 18 5181251317141813391738121498C为了便于在顶点集合 U和 VU之间选择权最小的边，需建立一个数组 closedge[v], (v∈V U),记录从 U到 VU之间权最小的边 . closedge[v]有两个字段 : closedge[v].vex: 存放与该边相关联的在 U中的顶点 , closedge[v].lowcost: 存放该边的权 . 普里姆算法 : void prim( gn, 1) /*gn: 图的邻接矩阵 ， 顶点为 { /* {1,2,… ,n}, 从顶点 1开始 for( i=2, i=n。 i++) /*从顶点 2开始初始化 */ { closedge[i].vex=1。 closedge[i].lowcost=gn[1, i]。 } closedge[1].lowcost=0。 /*顶点 1加入 U中 . For( i=1。 i,=n1。 i++) /*求 n1条边 { j=min(closedge)。 /* j∈V U printf(“… ”, closedge [j]. vex, j)。 /*输出一条边 closedge [j]. lowcost=0。 /*顶点 j加入 U中 . for (k=1。 k=n。 k++) if (gn [j, k] closedge [k]. lowcost。 { closedge[k].lowcost=gn[j, k]。 closedge[k].vex= j。 } } } 算法分析 该算法中每一步执行都要扫描数组 lowcost，在 VU顶点集中找出与 U最近的顶点，令其为 k，并打印边（ k,closest[k]）。 然后将 k加入 U顶点集合中，并修改数组lowcost和 closest。 这里用 c表示图的邻接矩阵， c[i][j]和 c[j][i]是边 (i,j)的权。 2 克鲁斯卡尔（ Kruskal）算法 基本思想：设 G=（ V， E），最小生成树的初态只有 n个结点，无边，即 T=（ V， ）， 从图 G中选择一条权值最小的边，若此边加入 T后， T中不产生回路，则把该边加入 T，否则放弃；选下一条边 , …… , 直到 T中有 n1条边为止。 现以图 (a)图为例说明此算法。 设此图是用边集数组表示的，边集数组是一个结构数组，数组中的每个元素表示一条边，组成每条边的是三元组序列（边的起始顶点、边的终止顶点、边的权值）。 将每条边的数据输入之后，按权值的大小进行了排序，如图 (b) 所示。 这样，按权值由小到大选取各边就是在数组中按下标由 1到 e(图中边的数目 )的次序选取。 图 克鲁斯卡尔算法例子  (a)带权图 ⑥ 8 5 18 ⑤ ④ ① ② ③ 4 23 12 15 25 20 10  (b)边集数组 1 2 2 3 2 4 1 4 1 5 5 3 4 4 6 6 2 5 6 6 4 5 8 10 12 15 18 20 23 25 1 2 3 4 5 6 7 8 9 10 起点 终点 权值  (c)最小生成树 8 5 18 ⑥ ⑤ ④ ① ② ③ 4 12 在选取某边时如何判断是否与已保留的边形成环路。 克鲁斯卡尔算法是通过将各顶点划分为集合的办法来解决的。 开始时假定 n 个顶点分属于 n 个集合，即每个集合中有一个顶点，当确定某条边作为生成树的一条边时，就将该边两端点所属的两集合合并为一个，表示原来属于两个集合的各个顶点已被这条新的边连通。 如果取到某条边，发现它的两个端点已属于同一集合时，此边则应当舍去。 因为两个顶点属于同一集合说明它们已连通，若再添上这条边就会出现环路。 如此进行下去，到所有的顶点均已属于一个集合时，此最小生成树就构成了。 用一个 set[ ]数组来表示顶点， set的初值为s[i]=0(i=1,2,…,n), 表示各顶点自成一个分量。 当从边集数组中按次序选取一条边时，查找它的两个顶点所属的分量，当这两个分量不相等，则表明所选的这条边的两个顶点分属不同的集合，该边加入到生成树中不会形成环路，应作为生成树的一条边，同时合并这两个分量为一个连通分量。 若这两个分量相等，则表明这条边的两个顶点同属一个集合，将此边加入到生成树必产生环路，应予放弃。 利用克鲁斯卡尔构造最小生成树的边集数组结构定义如下： define MAXE 100 struct edges /* 边集类型 ， 存储一边条的起始顶点为 bv,终止顶点为 tv和权 w */ { int bv,tv,w。 } typedef struct edges edgeset[MAXE]。 查找一个顶点所属的分量函数如下： int seeks(int set[],int v) { int i=v。 while(set[i]0) i=set[i]。 return(i)。 } 克鲁斯卡尔算法 void kruskal (edgeset ge, int n, int e) /* ge为权按从小到大排序的边集数组 */ { int set[MAXE], v1, v2, i, j。 for (i=1。 i=n。 i++) set[i]=0。 /*给 set中每个元素赋初值 */ i=1。 /* i表示获取的生成树中的边数 ， 初值为 1*/ j=1。 /* j表示 ge中的下标 ， 初始值为 1*/ while (jn amp。 amp。 i=e) /* 检查该边是否加入到生成树中。