kruskal算法（克鲁斯卡尔算法）详解，图文并茂

在连通网中查找最小生成树的常用方法有两个分别称为普里姆算法和克鲁斯卡尔算法。本节我们给您讲解克鲁斯卡尔算法。克鲁斯卡尔算法查找最小生成树的方法是将连通网中所有的边按照权值大小做升序排序从权值最小的边开始选择只要此边不和已选择的边一起构成环路就可以选择它组成最小生成树。对于 N 个顶点的连通网挑选出 N-1 条符合条件的边这些边组成的生成树就是最小生成树。举个例子图 1 是一个连通网克鲁斯卡尔算法查找图 1 对应的最小生成树需要经历以下几个步骤图 1 连通网1) 将连通网中的所有边按照权值大小做升序排序2) 从 B-D 边开始挑选由于尚未选择任何边组成最小生成树且 B-D 自身不会构成环路所以 B-D 边可以组成最小生成树。图 2 B-D 边组成最小生成树3) D-T 边不会和已选 B-D 边构成环路可以组成最小生成树图 3 D-T 边组成最小生成树4) A-C 边不会和已选 B-D、D-T 边构成环路可以组成最小生成树图 4 A-C 边组成最小生成树5) C-D 边不会和已选 A-C、B-D、D-T 边构成环路可以组成最小生成树图 5 C-D 边组成最小生成树6) C-B 边会和已选 C-D、B-D 边构成环路因此不能组成最小生成树图 6 C-B 边不能组成最小生成树7) B-T 、A-B、S-A 三条边都会和已选 A-C、C-D、B-D、D-T 构成环路都不能组成最小生成树。而 S-A 不会和已选边构成环路可以组成最小生成树。图 7 S-A 边组成最小生成树8) 如图 7 所示对于一个包含 6 个顶点的连通网我们已经选择了 5 条边这些边组成的生成树就是最小生成树。图 8 最小生成树克鲁斯卡尔算法的具体实现实现克鲁斯卡尔算法的难点在于“如何判断一个新边是否会和已选择的边构成环路”这里教大家一种判断的方法初始状态下为连通网中的各个顶点配置不同的标记。对于一个新边如果它两端顶点的标记不同就不会构成环路可以组成最小生成树。一旦新边被选择需要将它的两个顶点以及和它直接相连的所有已选边两端的顶点改为相同的标记反之如果新边两端顶点的标记相同就表示会构成环路。举个例子在上面的图 4 中已选择的边为 A-C、B-D、D-T接下来要判断 C-D 边是否可以组成最小生成树。对于已经选择的边B-D 和 D-T 直接相邻所以 B、D、T 的标记相同假设为 1A-C 边两端顶点的标记也相同假设为 2。判断 C-D 边是否可以组成最小生成树由于 C、D 的标记不同1 ≠ 2所以可以组成最小生成树。C-D 作为新选择的边与它相连的已选边有 A-C、B-D、D-T所以要将 A、C、D、B、T 改为相同的标记。再比如说在图 5 的基础上判断 C-B 是否可以组成最小生成树。由上面例子的分析结果得知C、B 两个顶点的标记相同因此 C-B 边会和其它已选边构成环路不能组成最小生成树如图 6 所示。如下是用克鲁斯卡尔算法在图 1 所示的连通网中查找最小生成树的 C 语言程序#include stdio.h #include stdlib.h #define N 9 // 图中边的数量 #define P 6 // 图中顶点的数量 //构建表示边的结构体 struct edge { //一条边有 2 个顶点 int initial; int end; //边的权值 int weight; }; //qsort排序函数中使用使edges结构体中的边按照权值大小升序排序 int cmp(const void* a, const void* b) { return ((struct edge*)a)-weight - ((struct edge*)b)-weight; } //克鲁斯卡尔算法寻找最小生成树edges 存储用户输入的图的各个边minTree 用于记录组成最小生成树的各个边 void kruskal_MinTree(struct edge edges[], struct edge minTree[]) { int i, initial, end, elem, k; //每个顶点配置一个标记值 int assists[P]; int num 0; //初始状态下每个顶点的标记都不相同 for (i 0; i P; i) { assists[i] i; } //根据权值对所有边进行升序排序 qsort(edges, N, sizeof(edges[0]), cmp); //遍历所有的边 for (i 0; i N; i) { //找到当前边的两个顶点在 assists 数组中的位置下标 initial edges[i].initial - 1; end edges[i].end - 1; //如果顶点位置存在且顶点的标记不同说明不在一个集合中不会产生回路 if (assists[initial] ! assists[end]) { //记录该边作为最小生成树的组成部分 minTree[num] edges[i]; //计数1 num; elem assists[end]; //将新加入生成树的顶点标记全部改为一样的 for (k 0; k P; k) { if (assists[k] elem) { assists[k] assists[initial]; } } //如果选择的边的数量和顶点数相差1证明最小生成树已经形成退出循环 if (num P - 1) { break; } } } } void display(struct edge minTree[]) { int cost 0, i; printf(最小生成树为:\n); for (i 0; i P - 1; i) { printf(%d-%d 权值%d\n, minTree[i].initial, minTree[i].end, minTree[i].weight); cost minTree[i].weight; } printf(总权值为%d, cost); } int main() { int i; struct edge edges[N], minTree[P - 1]; for (i 0; i N; i) { scanf(%d %d %d, edges[i].initial, edges[i].end, edges[i].weight); } kruskal_MinTree(edges, minTree); display(minTree); return 0; }用克鲁斯卡尔算法在图 1 所示的连通网中查找最小生成树的 Java 程序import java.util.Arrays; import java.util.Scanner; public class prim { static int N 9; // 图中边的数量 static int P 6; // 图中顶点的数量 //构建表示路径的类 public static class edge implements Comparableedge{ //每个路径都有 2 个顶点和 1 个权值 int initial; int end; int weight; public edge(int initial, int end, int weight) { this.initial initial; this.end end; this.weight weight; } //对每个 edge 对象根据权值做升序排序 Override public int compareTo(edge o) { return this.weight - o.weight; } } public static void kruskal_MinTree(edge[] edges,edge [] minTree) { int []assists new int[P]; //每个顶点配置一个不同的标记值 for (int i 0; i P; i) { assists[i] i; } //根据权值对所有边进行升序排序 Arrays.sort(edges); //遍历所有的边 int num 0; for (int i 0; i N; i) { //找到当前边的两个顶点在 assists 数组中的位置下标 int initial edges[i].initial - 1; int end edges[i].end - 1; //如果顶点位置存在且顶点的标记不同说明不在一个集合中不会产生回路 if (assists[initial] ! assists[end]) { //记录该边作为最小生成树的组成部分 minTree[num] edges[i]; //计数1 num; int elem assists[end]; //将新加入生成树的顶点标记全不更改为一样的 for (int k 0; k P; k) { if (assists[k] elem) { assists[k] assists[initial]; } } //如果选择的边的数量和顶点数相差1证明最小生成树已经形成退出循环 if (num P - 1) { break; } } } } public static void display(edge [] minTree) { System.out.println(最小生成树为); int cost 0; for (int i 0; i P - 1; i) { System.out.println(minTree[i].initial - minTree[i].end 权值为minTree[i].weight); cost minTree[i].weight; } System.out.print(总权值为:cost); } public static void main(String[] args) { Scanner scn new Scanner(System.in); edge[] edges new edge[N]; edge[] minTree new edge[P-1]; System.out.println(请输入图中各个边的信息); for(int i0;iN;i) { int initial scn.nextInt(), end scn.nextInt(), weight scn.nextInt(); edges[i] new edge(initial,end,weight); } kruskal_MinTree(edges,minTree); display(minTree); } }用克鲁斯卡尔算法在图 1 所示的连通网中查找最小生成树的 python 程序N 9 #图中边的数量 P 6 #图中顶点的数量 #构建表示边的结构体 class edge: #一条边有 2 个顶点 initial 0 end 0 #边的权值 weight 0 def __init__(self,initial,end,weight): self.initial initial self.end end self.weight weight edges [] # 用于保存用户输入的图各条边的信息 minTree[] # 保存最小生成数各个边的信息 #输入 N 条边的信息 for i in range(N): li input().split() initial int(li[0]) end int(li[1]) weight int(li[2]) edges.append(edge(initial,end,weight)) # 根据 weight 给 edges 列表排序 def cmp(elem): return elem.weight #克鲁斯卡尔算法寻找最小生成树 def kruskal_MinTree(): #记录选择边的数量 num 0 #为每个顶点配置一个不同的标记 assists [i for i in range(P)] #对 edges 列表进行排序 edges.sort(key cmp) #遍历 N 条边从重选择可组成最小生成树的边 for i in range(N): #找到当前边的两个顶点在 assists 数组中的位置下标 initial edges[i].initial -1 end edges[i].end-1 # 如果顶点位置存在且顶点的标记不同说明不在一个集合中不会产生回路 if assists[initial] ! assists[end]: # 记录该边作为最小生成树的组成部分 minTree.append(edges[i]) #计数1 num num1 #将新加入生成树的顶点标记全部改为一样的 elem assists[end] for k in range(P): if assists[k] elem: assists[k] assists[initial] #如果选择的边的数量和顶点数相差1证明最小生成树已经形成退出循环 if num P-1: break def display(): cost 0 print(最小生成树为:) for i in range(P-1): print(%d-%d 权值%d%(minTree[i].initial, minTree[i].end, minTree[i].weight)) cost cost minTree[i].weight print(总权值为:%d%(cost)) kruskal_MinTree() display()将图 1 中的 A、B、C、D、S、T 顶点分别用数字 1~6 表示上面程序的执行结果均为5 1 7 5 3 8 1 2 6 1 3 3 3 2 4 3 4 3 2 4 2 2 6 5 4 6 2 最小生成树为: 2-4 权值2 4-6 权值2 1-3 权值3 3-4 权值3 5-1 权值7 总权值为17