当前位置：首页>编程日记>正文

最小生成树之克鲁斯卡尔（Kruskal）算法

编程日记 2024/02/09 11:34:58

学习最小生成树算法之前我们先来了解下下面这些概念：

树（Tree）：如果一个无向连通图中不存在回路，则这种图称为树。

生成树 （Spanning Tree）：无向连通图G的一个子图如果是一颗包含G的所有顶点的树，则该子图称为G的生成树。

生成树是连通图的极小连通子图。这里所谓极小是指：若在树中任意增加一条边，则将出现一条回路；若去掉一条边，将会使之变成非连通图。

最小生成树（Minimum Spanning Tree，MST）：或者称为最小代价树Minimum-cost Spanning Tree:对无向连通图的生成树，各边的权值总和称为生成树的权，权最小的生成树称为最小生成树。

构成生成树的准则有三条：

<1> 必须只使用该网络中的边来构造最小生成树。

<2> 必须使用且仅使用n-1条边来连接网络中的n个顶点

<3> 不能使用产生回路的边。

构造最小生成树的算法主要有：克鲁斯卡尔（Kruskal）算法和普利姆（Prim）算法他们都遵循以上准则。

接下分别讨论一下这两种算法以及判定最小生成树是否唯一的方法。

克鲁斯卡尔算法

克鲁斯卡尔算法的基本思想是以边为主导地位，始终选择当前可用（所选的边不能构成回路）的最小权植边。所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。这一步可以直接使用库函数qsort或者sort。接下来从小到大依次考察每一条边（u，v）。

具体实现过程如下：

<1>　设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T={V,空}，图中每个顶点自成一格连通分量。

<2>　在Ｅ中选择一条具有最小权植的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到Ｔ中；否则，即这条边的两个顶点落到同一连通分量上，则将此边舍去（此后永不选用这条边），重新选择一条权植最小的边。

<3>　如此重复下去，直到所有顶点在同一连通分量上为止。

下面是伪代码：

 1 // 把所有边排序，记第i小的边为e[i] (1<=i<=m)m为边的个数 
 2 // 初始化MST为空
 3 // 初始化连通分量，使每个点各自成为一个独立的连通分量
 4 
 5 for (int i = 0; i < m; i++)
 6 {
 7     if (e[i].u和e[i].v不在同一连通分量)
 8     {
 9         // 把边e[i]加入ＭＳＴ
10         // 合并e[i].u和e[i].v所在的连通分量 
11     } 
12 }