第7章讲+图.ppt

* 第*页 具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。 考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。 克鲁斯卡尔算法的基本思想： * 第*页 a b c d e g f 19 5 14 18 27 16 8 21 3 a e 12 d c b g f 7 14 8 5 3 16 21 例如: 7 12 18 19 * 第*页 算法描述: 构造非连通图 ST=( V,{ } ); k = i = 0; // k 计选中的边数 while (kn-1) { ++i; 检查边集 E 中第 i 条权值最小的边(u,v); 若(u,v)加入ST后不使ST中产生回路， 则 输出边(u,v); 且 k++; } Typedef struct{ //存放有序边 int vi,vj,w; }edgeset[MAXE]; int set[MAXV]; // 用于判断两个顶点是否是同一集合 int FindSet(int set[ ], int v){ i = v; while(set[i]0) i = set[i]; //求v所在树的根，一棵树的所有 // 节点都在一个集合中 return i; } void kruskal (edgeset ge, int n, int e) // ge为权按从小到大排序的边集数组 { for (i=1;i=n;i++) set[i]=0; //给set中每个元素赋初值 i=1; //i为ge中的下标，初始值为1 j=1; // j为生成树中的边数，初值为1 while (jn) // 检查该边是否加入到生成树中,共获得n-1条边 { v=FindSet(set,ge[i].vi); w=FindSet (set,ge[i].vj); if (v!=w) { //当 vi,vj不在同一集合，该边加入生成树 printf(“(%d,%d)”,ge[i].vi,ge[i].vj); set[v]=w; j++; } i++; } } Kruscal算法实现 V1 V2 V3 V6 V5 V4 6 5 1 5 2 3 4 5 6 6 边权排序： (V1,V3)1 (V1,V4)5 (V1,V2)6 (V4,V6)2 (V2,V3)5 (V3,V5)6 (V2,V5)3 (V3,V4)5 (V5,V6)6 (V3,V6)4 (V1,V3) 0 0 0 0 0 0 0 SET v1 v2 v3 v4 v5 v6 0 1 2 3 4 5 6 V=1 ,W=3 V1 V3 (V4,V6) Set[1]=3 3 V=4 ,W=6 Set[4]=6 6 V4 V6 (V2,V5) V=2 ,W=5 Set[2]=5 5 V2 V5 (V3,V6) V=3 ,W=6 Set[3]=6 6 (V1,V4) V=6 ,W=6 同一集合 (V2,V3) V=5 ,W=6 Set[5]=6 6 * 第*页 普里姆算法 克鲁斯卡尔算法 时间复杂度 O(n2) O(eloge) 稠密图 稀疏图 算法名 适应范围 比较两种算法 * 第*页 7.5 重（双）连通图 和关节点 若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。 问题： * 第*页 若连通图中的某个顶点和其相关 联的边被删去之后，该连通图被分割 成两个或两个以上的连通分量，则称 此顶点为关节点。 没有关节点的连通图为双连通图。 如何判别给定的连通图是否是双连通图？ * 第*页 a h g c b f d e a b c d e f g h 1 2 3 4 5 6 7 8 3 3 1 1 1 1 1 1 例如:下列连通图中， 顶点 a 和顶点 c 是关节点 深度优先生成树 * 第*页 关节点有何特征？