最小生成树的两种方法 （Kruskal算法和Prim算法）

先介绍有关图的几种概念和定义：

• 连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。
• 强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。
• 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
• 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
• 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。 
  

下面介绍两种求最小生成树算法：

1.Kruskal算法

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。 
1. 把图中的所有边按代价从小到大排序； 
2. 把图中的n个顶点看成独立的n棵树组成的森林； 
3. 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。 
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

 

 

2.Prim算法

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

1. 图的所有顶点集合为VV；初始令集合u={s},v=V−uu={s},v=V−u;
2. 在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
3. 重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

下面讲解一下最小生成树的模板题： 洛谷 P3366 【模板】最小生成树

 

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz

输入输出格式

输入格式：

第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）

接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式：

输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

输入输出样例

输入样例#1： 复制

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出样例#1： 复制

7

说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=20

对于40%的数据：N<=50，M<=2500

对于70%的数据：N<=500，M<=10000

对于100%的数据：N<=5000，M<=200000

样例解释：

所以最小生成树的总边权为2+2+3=7

此题是一个最小生成树的模板题，所以没有什么思路可言，直接看代码展示。本小鼠的代码是使用的kruskal算法。

代码展示：（show me code）

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m;
struct node{              // 建立一个结构体来进行数据的存储从起点到终点的权值 
	int from,to,value;
}a[200005];
int b[5005];             // 构造数组来存储n个独立的点以便判断是否是同一棵树上的节点 
bool cmp(node a,node b){
	return a.value<b.value;
}                        // 利用cmp函数来进行边权的排序，也是kruskal算法的核心 
int getf(int v)             // 找节点的根节点函数 
{
	if(b[v]==v)
	return v;
	else
	{
		b[v]=getf(b[v]);
		return b[v];
	}
}
void merge(int v,int u)        //归并两个不同为一棵树的节点函数 
{
	int t1=getf(v);
	int t2=getf(u);
	if(t1!=t2)
	b[t2]=t1;
	return;
}
int kruskal()      //让权值从小到大加边，如果两个节点不在同一棵树上，就将权值加在sum变量上，然后将两个节点进行归并 
{                  //之后访问的时候就要去掉这种已经合并的情况， 直到遍历到所有的顶点都在一棵树上时或者有n-1条边为止。 
	int sum=0;
	int count=0;
	for(int i=1;i<=m;i++)
	{
		int t1=getf(a[i].from);
		int t2=getf(a[i].to);
		if(t1!=t2)
		{
			sum+=a[i].value;
			count++;
			merge(t1,t2);
		}
		if(count==n-1)     //有n-1条边时，就将sum结果输出 
		return sum;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	b[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].from>>a[i].to>>a[i].value;
	}
	sort(a+1,a+m+1,cmp); // 将边权进行从小到大排序 
	printf("%d\n",kruskal());
	return 0;
}