数据结构 第17讲 沟通无限校园网——最小生成树(kruskal算法)

本内容来源于本人著作《趣学算法》,在线章节:http://www.epubit.com.cn/book/details/4825

构造最小生成树还有一种算法,Kruskal算法:设G=(V,E)是无向连通带权图,V={1,2,…,n};设最小生成树T=(V,TE),该树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),Kruskal算法将这n个顶点看成是n个孤立的连通分支。它首先将所有的边按权值从小到大排序,然后只要T中选中的边数不到n−1,就做如下的贪心选择:在边集E中选取权值最小的边(i,j),如果将边(i,j)加入集合TE中不产生回路(圈),则将边(i,j)加入边集TE中,即用边(i,j)将这两个连通分支合并连接成一个连通分支;否则继续选择下一条最短边。把边(i,j)从集合E中删去。继续上面的贪心选择,直到T中所有顶点都在同一个连通分支上为止。此时,选取到的n−1条边恰好构成G的一棵最小生成树T。

那么,怎样判断加入某条边后图T会不会出现回路呢?

该算法对于手工计算十分方便,因为用肉眼可以很容易看到挑选哪些边能够避免构成回路(避圈法),但使用计算机程序来实现时,还需要一种机制来进行判断。Kruskal算法用了一个非常聪明的方法,就是运用集合避圈:如果所选择加入的边的起点和终点都在T的集合中,那么就可以断定一定会形成回路(圈)。其实就是我们前面提到的“避圈法”:边的两个结点不能属于同一集合。

步骤1:初始化。将图G的边集E中的所有边按权值从小到大排序,边集TE={ },把每个顶点都初始化为一个孤立的分支,即一个顶点对应一个集合。

步骤2:在E中寻找权值最小的边(i,j)。

步骤3:如果顶点i和j位于两个不同连通分支,则将边(i,j)加入边集TE,并执行合并操作,将两个连通分支进行合并。

步骤4:将边(i,j)从集合E中删去,即E=E−{(i,j)}。

步骤 5:如果选取边数小于n−1,转步骤2;否则,算法结束,生成最小生成树T。

2.完美图解

设G =(V,E)是无向连通带权图,

(1)初始化

将图G的边集E中的所有边按权值从小到大排序,

边集初始化为空集,TE={ },把每个结点都初始化为一个孤立的分支,即一个顶点对应一个集合,集合号为该结点的序号,如图2-100所示。

图2-100 每个结点初始化集合号

(2)找最小

在E中寻找权值最小的边e1(2,7),边值为1。

(3)合并

结点2和结点7的集合号不同,即属于两个不同连通分支,则将边(2,7)加入边集TE,执行合并操作(将两个连通分支所有结点合并为一个集合);假设把小的集合号赋值给大的集合号,那么7号结点的集合号也改为2,

(4)找最小

在E中寻找权值最小的边e2(4,5),边值为3。

(5)合并

结点4和结点5集合号不同,即属于两个不同连通分支,则将边(4,5)加入边集TE,执行合并操作将两个连通分支所有结点合并为一个集合;假设我们把小的集合号赋值给大的集合号,那么5号结点的集合号也改为4,

(6)找最小

在E中寻找权值最小的边e3(3,7),边值为4。

(7)合并

结点3和结点7集合号不同,即属于两个不同连通分支,则将边(3,7)加入边集TE,执行合并操作将两个连通分支所有结点合并为一个集合;假设我们把小的集合号赋值给大的集合号,那么3号结点的集合号也改为2,

(8)找最小

在E中寻找权值最小的边e4(4,7),边值为9。

(9)合并

结点4和结点7集合号不同,即属于两个不同连通分支,则将边(4,7)加入边集TE,执行合并操作将两个连通分支所有结点合并为一个集合;假设我们把小的集合号赋值给大的集合号,那么4、5号结点的集合号都改为2,

(10)找最小

在E中寻找权值最小的边e5(3,4),边值为15。

(11)合并

结点3和结点4集合号相同,属于同一连通分支,不能选择,否则会形成回路。

(12)找最小

在E中寻找权值最小的边e6(5,7),边值为16。

(13)合并

结点5和结点7集合号相同,属于同一连通分支,不能选择,否则会形成回路。

(14)找最小

在E中寻找权值最小的边e7(5,6),边值为17。

(15)合并

结点5和结点6集合号不同,即属于两个不同连通分支,则将边(5,6)加入边集TE,执行合并操作将两个连通分支所有结点合并为一个集合;假设我们把小的集合号赋值给大的集合号,那么6号结点的集合号都改为2,

(16)找最小

在E中寻找权值最小的边e8(2,3),边值为20。

(17)合并

结点2和结点3集合号相同,属于同一连通分支,不能选择,否则会形成回路。

(18)找最小

在E中寻找权值最小的边e9(1,2),边值为23。

(19)合并

结点1和结点2集合号不同,即属于两个不同连通分支,则将边(1,2)加入边集TE,执行合并操作将两个连通分支所有结点合并为一个集合;假设我们把小的集合号赋值给大的集合号,那么2、3、4、5、6、7号结点的集合号都改为1,

(20)选中的各边和所有的顶点就是最小生成树,各边权值之和就是最小生成树的代价。

3.伪码详解

(1)数据结构

int nodeset[N];//集合号数组
struct Edge {//边的存储结构
     int u;
     int v;
     int w;
}e[N*N];

(2)初始化

void Init(int n)
{
     for(int i = 1; i <= n; i++)
          nodeset[i] = i;//每个结点赋值一个集合号
}

(3)对边进行排序

bool comp(Edge x, Edge y) 
{
     return x.w < y.w;//定义优先级,按边值进行升序排序
}
sort(e, e+m, comp);//调用系统排序函数

(4)合并集合

int Merge(int a, int b)
{
     int p = nodeset[a];//p为a结点的集合号
     int q = nodeset[b]; //q为b结点的集合号
     if(p==q) return 0; //集合号相同,什么也不做,返回
     for(int i=1;i<=n;i++)//检查所有结点,把集合号是q的全部改为p
     {
       if(nodeset[i]==q)
          nodeset[i] = p;//a的集合号赋值给b集合号
     }
     return 1;
}

4.实战演练

//program 2-8
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100;
int nodeset[N];
int n, m;
struct Edge {
     int u;
     int v;
     int w;
}e[N*N];
bool comp(Edge x, Edge y) 
{
     return x.w < y.w;
}
void Init(int n)
{
     for(int i = 1; i <= n; i++)
          nodeset[i] = i;
}
int Merge(int a, int b)
{
     int p = nodeset[a];
     int q = nodeset[b];
     if(p==q) return 0;
     for(int i=1;i<=n;i++)//检查所有结点,把集合号是q的改为p
     {
       if(nodeset[i]==q)
          nodeset[i] = p;//a的集合号赋值给b集合号
     }
     return 1;
}
int Kruskal(int n)
{
     int ans = 0;
     for(int i=0;i<m;i++)
          if(Merge(e[i].u, e[i].v))
          {
              ans += e[i].w;
              n--;
              if(n==1)
                  return ans;
          }
     return 0;
}
int main()
{
  cout <<"输入结点数n和边数m:"<<endl;
  cin >> n >> m;
  Init(n);
  cout <<"输入结点数u,v和边值w:"<<endl;
  for(int i=0;i<m;i++)
      cin >> e[i].u>> e[i].v >>e[i].w;
  sort(e, e+m, comp);
  int ans = Kruskal(n);
  cout << "最小的花费是:" << ans << endl;
 return 0;
}

5.算法复杂度分析

(1)时间复杂度:算法中,需要对边进行排序,若使用快速排序,执行次数为e*loge,算法的时间复杂度为O(e*loge)。而合并集合需要n−1次合并,每次为O(n),合并集合的时间复杂度为O(n2)。

(2)空间复杂度:算法所需要的辅助空间包含集合号数组 nodeset[n],则算法的空间复杂度是O(n)。

6.算法优化拓展

该算法合并集合的时间复杂度为O(n2),我们可以用并查集(见附录E)的思想优化,使合并集合的时间复杂度降为O(e*logn),优化后的程序如下。

//program 2-9
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100;
int father[N];
int n, m;
struct Edge {
     int u;
     int v;
     int w;
}e[N*N];
bool comp(Edge x, Edge y) {
     return x.w < y.w;//排序优先级,按边的权值从小到大
}
void Init(int n)
{
     for(int i = 1; i <= n; i++)
          father[i] = i;//顶点所属集合号,初始化每个顶点一个集合号
}
int Find(int x) //找祖宗
{
     if(x != father[x])
     father[x] = Find(father[x]);//把当前结点到其祖宗路径上的所有结点的集合号改为祖宗集合号
     return father[x]; //返回其祖宗的集合号
}
int Merge(int a, int b) //两结点合并集合号
{
     int p = Find(a); //找a的集合号
     int q = Find(b); //找b的集合号
     if(p==q) return 0;
     if(p > q)
           father[p] = q;//小的集合号赋值给大的集合号
     else
           father[q] = p;
     return 1;
}
int Kruskal(int n)
{
     int ans = 0;
     for(int i=0;i<m;i++)
          if(Merge(e[i].u, e[i].v))
          {
              ans += e[i].w;
              n--;
              if(n==1)
                  return ans;
          }
     return 0;
}
int main() 
{
    cout <<"输入结点数n和边数m:"<<endl;
    cin >> n >> m;
    Init(n);
    cout <<"输入结点数u,v和边值w:"<<endl;
    for(int i=0;i<m;i++)
        cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e, e+m, comp);
    int ans = Kruskal(n);
    cout << "最小的花费是:" << ans << endl;
    return 0;
}

算法实现和测试

(1)运行环境

Code::Blocks

(2)输入

输入结点数n和边数m:
7 12
输入结点数u,v和边值w:
1 2 23
1 6 28
1 7 36
2 3 20
2 7 1
3 4 15
3 7 4
4 5 3
4 7 9
5 6 17
5 7 16
6 7 25

(3)输出

最小的花费是:57

7.两种算法的比较

(1)从算法的思想可以看出,如果图G中的边数较小时,可以采用Kruskal算法,因为Kruskal算法每次查找最短的边;边数较多可以用Prim算法,因为它是每次加一个结点。可见,Kruskal算法适用于稀疏图,而Prim算法适用于稠密图。

(2)从时间上讲,Prim算法的时间复杂度为O(n2),Kruskal算法的时间复杂度为O(eloge)。

(3)从空间上讲,显然在Prim算法中,只需要很小的空间就可以完成算法,因为每一次都是从V−U集合出发进行扫描的,只扫描与当前结点集到U集合的最小边。但在Kruskal算法中,需要对所有的边进行排序,对于大型图而言,Kruskal算法需要占用比Prim算法大得多的空间。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

AVL二叉树

AVL二叉查找树 AVL二叉查找树是一种特殊的二叉查找树,其规定 每个节点的左子树和右子树的高度差最多是1 AVL调整算法 AVL树插入一个新的节点到某个节点下...

32210
来自专栏Flutter入门

Android OpenGL ES(二)-正交投影

平移矩阵和单位矩阵和类似。但是向量[x,y,z,1]前乘这个平移矩阵后的结构就是平移矩阵中定义的偏移量。

3701
来自专栏数据结构与算法

4768 跳石头

4768 跳石头 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一年一度的“...

27710
来自专栏大数据和云计算技术

算法基础8:平衡树之红黑树

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第8篇《平衡查找树概述》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法...

3465
来自专栏数据结构与算法

洛谷P2678 跳石头

题目背景 一年一度的“跳石头”比赛又要开始了! 题目描述 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终...

3435
来自专栏小樱的经验随笔

从零基础学三分查找

今晚是我们学长第二次讲课,讲了一个三分!认真听了一下,感觉不是很难,可能会比二分还简单些!我就把上课讲的内容归纳为一篇文章概述吧!以后也会重点讲解的! 简单点说...

44010
来自专栏算法与数据结构

数据结构 数组和广义表以及树的基本概念

2-1 设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为 (2分) 1...

2578
来自专栏ml

cf------(round)#1 C. Ancient Berland Circus(几何)

C. Ancient Berland Circus time limit per test 2 seconds memory limit per test ...

2533
来自专栏开发与安全

平衡二叉树 AVL 的插入节点后旋转方法分析

平衡二叉树 AVL( 发明者为Adel'son-Vel'skii 和 Landis)是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1。 首先我...

2470
来自专栏温安适的blog

最小生产树Prim和Kruskal

47512

扫码关注云+社区

领取腾讯云代金券