连通图中寻找最小生成树的常用算法有 2 种,分别是普里姆算法和克鲁斯卡尔算法。本节,我们将带您详细了解克鲁斯卡尔算法。
和普里姆算法类似,克鲁斯卡尔算法的实现过程也采用了贪心的策略:对于具有 n 个顶点的图,将图中的所有路径(边)按照权值大小进行升序排序,从权值最小的路径开始挑选,只要此路径不会和已选择的其它路径构成环路,就选定其作为最小生成树的一部分,直至选够 n-1 条路径。
对于具有 n 个顶点的图,选择 n-1 条路径就可以将所有顶点连接起来。在此基础上,保证所选的每条路径的权值都最小,就可以找到一棵最小生成树。
图 1 图存储结构
以图 1 所示的连通图为例,克鲁斯卡尔算法寻找最小生成树的过程为:
1) 将所有路径(边)按照权值大小进行升序排序:
2) 从最小的路径开始,只要该路径不会和其它已选路径产生环路,就选择它作为组成最小生成树的一部分。显然 (B,D) 符合要求,选择它组成最小生成树:
图 2 克鲁斯卡尔算法寻找最小生成树_过程 1
3) (D,T) 不会和已选路径 (B,D) 构成环路,可以组成最小生成树:
图 3 克鲁斯卡尔算法寻找最小生成树_过程 2
4) (A,C) 不会和 (B,D)、(D,T) 构成环路,可以组成最小生成树:
图 4 克鲁斯卡尔算法寻找最小生成树_过程 3
5) (C,D) 不会和 (A,C)、(B,D)、(D,T) 构成环路,可以组成最小生成树:
图 5 克鲁斯卡尔算法寻找最小生成树_过程 4
6) (C,B) 会和已选路径 (C,D)、(B,D) 构成环路(如图 6 所示),因此不会被选择:
图 6 克鲁斯卡尔算法寻找最小生成树_过程 5
7) (B,T) 会和已选路径 (B,D)、(D,T) 构成环路,也不被选择;
8) (A,B) 会和已选路径 (A,C)、(C,D)、(D,B) 构成环路,也不被选择;
9) (S,A) 不会和已选路径 (A,C)、(C,D)、(D,B)、(D,T) 构成环路,可以组成最小生成树:
图 7 克鲁斯卡尔算法寻找最小生成树_过程 6
图 1 中的图结构共有 6 个顶点,我们已经选择了 5 条路径,因此算法执行结束,图 7 所示即为最终找到的最小生成树。
克鲁斯卡尔算法的具体实现
克鲁斯卡尔算法的实现,难点在于如何判断所选路径是否会造成环路,这里给您介绍一种简单的解决方案:初始状态下,为图中的每个顶点配备一个互不相同的标记值,算法执行过程中,如果新路径两个顶点的标记值不同,则不会构成环路,该路径被选择的同时,要将两个顶点的标记改为和其它已选路径中的顶点标记相同;反之,如果该路径两个顶点的标记值相同,则会构成环路。
举个例子,图 5 中,已选路径为 (A,C)、(B,D)、(C,D)、(D,T),此时顶点 A、C、B、D、T 的标记值相同,顶点 S 的标记值和它们不同。图 6 中,判定 (B,C) 路径是否可以组成最小生成树时,由于顶点 B 和 C 的标记值相同,因此该路径会和其它已选路径构成环路(如图 6 所示),不能组成最小生成树。
如下为实现克鲁斯卡尔算法的 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; //每个顶点配置一个标记值 int assists[P]; int num = 0; //初始状态下,每个顶点的标记都不相同 for (i = 0; i < P; i++) { assists[i] = i; } //根据权值,对所有边进行升序排序 qsort(edges, N, sizeof(edges[0]), cmp); //遍历所有的边 for (int 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++; 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; } } } } void display(struct edge minTree[]) { int cost = 0; printf("最小生成树为:\n"); for (int 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; }
如下为实现克鲁斯卡尔算法的 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 Comparable<edge>{ //每个路径都有 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 i=0;i<N;i++) { int initial = scn.nextInt(), end = scn.nextInt(), weight = scn.nextInt(); edges[i] = new edge(initial,end,weight); } kruskal_MinTree(edges,minTree); display(minTree); } }
如下为实现克鲁斯卡尔算法的 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 = num+1 #将新加入生成树的顶点标记全部改为一样的 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 所示的图结构为例,以上程序的输出结果均为:
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