最小生成树克鲁斯卡尔（kruskal）与普里姆（prim）算法实现及代码实现

客官°小女子只卖身不卖艺 2023-02-25 07:28 128阅读 0赞

#### 一、最小生成树是什么 ####

1、生成树：若一个无向连通图G的子图是包含了G的所有顶点的一棵树，则该子图是G的生成树。生成树是图的极小连通子图。简单来说就是删去所有成环的边，使得G变为无环图。  
2、最小生成树：对无向连通图的生成树中所有边**权值和最小**的树。

最小生成树有三大算法：克鲁斯卡尔算法（Kruskal）、普里姆算法（Prim）、Boruvka算法

--------------------

#### 二、克鲁斯卡尔算法（Kruskal） ####

**1、算法思想：**  
克鲁斯卡尔算法以**边**为主导。设有n个顶点的联通网络G(V,E)，①先将所有点取出，构造一个n个顶点0条边的全不连通图。②然后在所有边的集合E中选一条权值最小的边，若该边的两个顶点在不同的连通分量上（即该两点不连通），则加入此边，使两个顶点的两个连通分量连通。若该边的两个顶点落在相同的一个连通分量上（即本身就已连通），则舍去此边，以后都不会再用，重新选择一条权值最小的边。③如此重复下去，直到所有的顶点都落在同一个连通分量上为止。

**2、算法关键原理**  
①最小堆存放所有边的集合E，在E中每次要选择权值最小的边来连接。（若不了解小顶堆，[可以看这篇文章][Link 1]）。  
②选择权值最小的边后，要判断两个顶点是否是一个连通分量，这里可以用并查集来实现，（若不了解并查集，[可以看这篇文章][Link 2]）。

**3、代码实现**

#include<iostream>
    #include<queue>
    #include<vector>
    using namespace std;
    const int N = 50,M = 2500;
    struct edge		//存边信息的结构体
    { 
    	int u,v,w;	//u是起点，v是终点，w是权值
    };
    bool operator < (edge a,edge b)		//重载运算符"<"
    { 
    	return a.w > b.w;		//用边的权值排序，建立最小堆
    }
    
    priority_queue<edge> es;		//最小堆es存边的信息
    vector<edge> ans;			//数组ans存放所有成树的边
    int n,m,father[N],sumweight;		//father是并查集数组，sumweight是生成树的权值
    
    int find(int n)			//并查集的查找模板
    { 
    	if(father[n] == n)
    		return n;
    	else
    		father[n] = find(father[n]);
    	return father[n];
    }
    
    void unio(int a,int b)		//并查集的联合模板
    { 
    	int fa = find(a);
    	int fb = find(b);
    	father[fb] = fa;
    }
    
    void kruskal()			//克鲁斯卡尔算法
    { 
    	for(int i = 0;i <= n;i++)	//初始化并查集数组
    		father[i] = i;
    	while(!es.empty())		//当边的信息不空时
    	{ 
    		int a = es.top().u,b = es.top().v;
    		if(find(a) != find(b))	//判断此边的两端点是否连通，不连通时
    		{ 
    			unio(a,b);	//连通两端点
    			ans.push_back({ a,b,es.top().w});	//将该边加入ans数组
    			sumweight += es.top().w;		//计算生成树的权值
    		}
    		es.pop();		//不管该边用没用，判断完就删除，以后不会再用
    	}
    }
    
    int main()
    { 
    	int a,b,c;
    	cin >> n >> m;
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b >> c;
    		es.push({ a,b,c});	//存边信息
    	}
    
    	kruskal();
    	
    	for(int i = 0;i < ans.size();i++)	//输出最小生成树的边
    		cout << ans[i].u << " " << ans[i].v << " " << ans[i].w << endl;
    	cout << sumweight << endl;		//输出最小生成树的权值
    		
    	return 0;
    }

克鲁斯卡尔算法以边为主导，时间复杂度取决于边，所以适用于稀疏图

--------------------

#### 二、普里姆算法（prim） ####

**1、算法思想**  
普里姆算法以**顶点**为主导。①将所有顶点分为两个集合y和n，y是已经连接成树的顶点集合，n是为连接的散点集合。②首先在y中找到一个顶点（记为a），使得该点到n集合中的一个顶点（记为b）的权值最小（最小指y中任何一个顶点到n中任何一个顶点的权值都大于该边的权值），③然后将b划到y集合中，如此反复直到所有顶点都划分到y集合中，即所有点连接成树，则已结束。

**2、算法关键原理**  
①每次要在y集合中找一个到n集合中的点的最小权值，我们可以用一个low数组和一个near数组来实现，low\[i\]存的是距离i顶点的边的最小权值，near\[i\]存的是距离i顶点最小权值边的另一个端点。若near\[i\] = -1说明i点属于集合y中，i点已连通。  
②用这两个数组就可以实现y中任何一个顶点到n中任何一个顶点的最小权值，就是low中最小的值对应的i，near\[i\]到i的边，权值为low\[i\]

**3、代码实现**

#include<iostream>
    using namespace std;
    
    const int N = 50,M = 2500,INF = 0x3f;	//INF默认为无穷大
    int n,m,e[N][N];		//邻接矩阵存储图
    int low[N],near[N],sumweigth = 0;	//sumweigth为生成树的权值
    
    void prim(int start)		//从start点开始做prim
    { 
    	for(int i = 1;i <= n;i++)
    	{ 
    		low[i] = e[start][i];		//初始化low数组，起初只有start到各点的距离
    		near[i] = start;		//到每个点最近的边都是start的距离
    	}
    	near[start] = -1;			//开始只有start点在y集合中
    
    	for(int i = 1;i <= n;i++)		//循环n个顶点
    	{ 
    		int minw = INF;			//用来查找low中最小的权值边
    		int v = -1;			//v初始化为-1
    		for(int j = 1;j <= n;j++)	//循环n个点
    		{ 
    			if(near[j] != -1 && low[j] < minw)	//如果j点在集合n中并且权值小于minw，更新minw和v
    			{ 
    				minw = low[j];	//更新minw
    				v = j;		//记录v点为j
    			}
    		}
    		if(v != -1)			//若v != -1说明找到了权值最小的v点
    		{ 
    			cout << near[v] << " " << v << " " << low[v] << endl;	//输出起点near[v]，终点v和权值
    			sumweigth += low[v];		//求最小生成树的权值
    			near[v] = -1;		//将v点化为集合y 
    			for(int j = 1;j <= n;j++)	//利用新加入的v点更新low数组
    			{ 
    				if(near[j] != -1 && e[v][j] < low[j])	//如果j点在集合y中且v到j的权值小于low[j]，将low[j]更新为最小
    				{ 
    					low[j] = e[v][j];	//更新low为最小权值
    					near[j] = v;		//更新到j的起点near[j]为v点
    				}
    			}
    		}
    	}
    }
    
    int main()
    { 
    	int a,b,c;
    	cin >> n >> m;
    	for(int i = 0;i <= n;i++)	//邻接矩阵初始化
    	{ 
    		for(int j = 0;j <= n;j++)
    		{ 
    			if(i == j)
    				e[i][j] = 0;
    			else
    				e[i][j] = INF;
    		}
    	}
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b >> c;
    		e[a][b] = c;	//邻接矩阵存储无向图
    		e[b][a] = c;
    	}
    
    	prim(1);	//从1号顶点做prim
    	cout << sumweigth << endl;	//输出最小生成树的权值
    
    	return 0;
    }

**注：** 普里姆算法时间复杂度是O(n*2*)，与边无关，所以适用于稠密图。

如果不需要记录生成树的具体是哪条边，只需要求出最小生成树的权值，则可以省略near数组，用low\[i\] = -1表示i点在集合y中。  
简单代码：

#include<iostream>
    #include<cstring>
    using namespace std;
    const int N = 50,INF = 0x3f;
    
    int e[N][N],dis[N],n,m;
    
    int prim()
    { 
    	int sum = 0;
    	for(int i = 1;i <= n;i++)	//默认从1号顶点开始建树
    		dis[i] = e[1][i];	//dis就是上面的low数组
    	dis[0] = INF;
    
    	for(int i = 0;i < n-1;i++)	//除了1号点，循环n-1个点
    	{ 
    		int t = 0;
    		for(int j = 1;j <= n;j++)	//找出dis数组中最小的权值
    			if(dis[j] && dis[t] > dis[j])	//dis距离不为0
    				t = j;
    		if(t == 0)
    			return INF;	//若点无法加入，则图不连通，返回正无穷
    		sum += dis[t];
    		dis[t] = 0;	//距离更新为0，t点加入树中
    		for(int j = 1;j <= n;j++)
    			if(dis[j] && dis[j] > e[t][j])	//更新dis数组，判断借助t点是否有到另一个集合中更短的边
    				dis[j] = e[t][j];
    	}
    	return sum;	//返回最小生成树的权值和
    }
    
    int main()
    { 
    	int a,b,c;
    	cin >> n >> m;
    	for(int i = 1;i <= n;i++)	//邻接矩阵初始化
    	{ 
    		for(int j = 1;j <= n;j++)
    		{ 
    			if(i == j)
    				e[i][j] = 0;
    			else
    				e[i][j] = INF;
    		}
    	}
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b >> c;
    		e[a][b] = c;
    		e[b][a] = c;
    	}
    
    	cout << prim() << endl;
    
    	return 0;
    }

[Link 1]: https://blog.csdn.net/qq_45735851/article/details/106154600
[Link 2]: https://blog.csdn.net/qq_45735851/article/details/106377870