prim算法求最小生成树

目录

一.最小生成树的定义

 二.普里姆（prim）算法

一.定义

二.算法实现步骤

三.prim算法朴素

三.例题P3366 【模板】最小生成树

堆优化版prim

---

一.最小生成树的定义

最小生成树（Minimum Spanning Tree，简称MST）是图论中的一个概念。给定一个连通的无向图，最小生成树是指包含图中所有顶点的一棵树，且该树的所有边的权重之和最小。

最小生成树的基本定义和性质：

1. 连通性：最小生成树必须包含图中的所有顶点，并且通过边将它们连接起来，确保整个图是连通的，即任意两个顶点之间都有路径。（一颗有 n 个顶点的生成树有且仅有 n−1 条边，如果生成树中再添加一条边，则必定成环。）
2. 无环：最小生成树是一棵树，所以不能包含任何环（即回路）。
3. 最小权重：最小生成树的边权重之和应当尽可能地小。在有多个满足条件的最小生成树时，它们的权重之和是相同的。

---

 二.普里姆（prim）算法

一.定义

普里姆算法是一种构造性算法。假设G = (V， E)是一个具有n个顶点的带权连通图，T = (U，TE)是最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始点v出法的最小生成树T的步骤如下：

• 初始化U = { v }，以v到其他顶点的所有边为侯选边。
• 重复以下步骤(n - 1)次，使得其他(n - 1)个顶点被加入U中。

---

二.算法实现步骤

1. 选择一个起始节点作为最小生成树的起点。
2. 将该起始节点加入最小生成树集合，并将其标记为已访问。
3. 在所有与最小生成树集合相邻的边中，选择权重最小的边和它连接的未访问节点。
4. 将该边和节点加入最小生成树集合，并将该节点标记为已访问。
5. 重复步骤3和步骤4，直到最小生成树集合包含了图中的所有节点。

  

下面我们将按步骤实现此算法，现给出一个无向完全图，求出其最小生成树。

（ 以下图片中亮的点表示为已访问，暗的点为未访问）

 1.首先我们选择一起始节点作为最小生成树的起点（这里取V1点作为起点），我们将V1点加入最小生成树集合中，标记为已访问。

2. 在所有与最小生成树集合相邻的边中，选择权重最小的边和它连接的未访问节点，将V3点加入到最小生成树集合中，将V3点标记为未访问。

 3.在所有与最小生成树集合相邻的边中，选择权重最小的边和它连接的未访问节点，（注意这里是与最小生成树的集合相邻的边中找，而不仅仅是V1或者V3的邻边）将V4点加入到最小生成树集合中，将V4点标记为未访问。

 4.重复步骤3，将点V4点加入到最小生成树集合中，将V4点标记为未访问。

5.重复以上操作，最后得到该图的最小生成树（其一）。

我们求出的最小生成树可能不是唯一的，需要注意，比如该图的最小生成树就不是唯一的，有两个。

 通过以上的步骤，我们可以大致理解其prim算法的实现原理，接下来我们通过代码实现prim算法求最小生成树。

  

三.prim算法朴素

#include<bits/stdc++.h>
using namespace std;
const int N = 10005, inf = 0x3f3f3f;        //inf代表无穷大
int dis[N], e[N][N];              //dis数组用来存储边，e数组表示邻接矩阵
bool vis[N];                      //标记数组
int n, m, ans;
 
void prim()          //prim算法核心代码段
{
	ans = 0;
	memset(dis, 0x3f, sizeof(dis));    //初始化边为无穷大
	dis[1] = 0;                        //选1为起始节点
	for (int i = 1; i <= n; i++) {
		int t = -1;
		int temp = inf;
		for (int j = 1; j <= n; j++) {         //找邻边最小边
			if (!vis[j] && dis[j] < temp) {
				temp = dis[j];
				t = j;
			}
		}
		if (t == -1)              //图不联通
		{
			ans = inf;
			return;
		}
		vis[t] = true;             //将该点标记为已访问
		ans += dis[t];          
		for (int k = 1; k <= n; k++) {        //松弛
			dis[k] = min(dis[k], e[t][k]);
		}
	}
}
int main()
{
	cin >> n >> m;
	memset(e, inf, sizeof(e));         //将邻接矩阵初始化为无穷大
	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		e[a][b] = e[b][a] = c;         //无向图，对称   （这里可以加一个取最小边的判断）
	}
	prim();
	if (ans == inf)                    //该图不联通
		cout << "orz" << endl;
	else                               //输出最小生成树各边长度之和
		cout << ans << endl;
	return 0;
}

以上是prim朴素代码，这里为什么说朴素是因为，我们还可以进一步优化prim算法，prim朴素方法的时间复杂度是O(N^2)。如果借助堆，每次选边的时间复杂度是O(logM)，然后再使用邻接表来存储图的话，整个算法的时间复杂度会降到O(MlogN)。

下面我们通过一道模板题来实现堆优化版的prim算法。

---

三.例题P3366 【模板】最小生成树

https://www.luogu.com.cn/problem/P3366

题目描述

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

输入格式

第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。

接下来 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

说明/提示

数据规模：

对于 20% 的数据，N≤5，M≤20。

对于 40% 的数据，N≤50，M≤2500。

对于 70% 的数据，N≤500，M≤104。

对于 100% 的数据：1≤N≤5000，1≤M≤2×105，1≤Zi​≤104。

样例解释：

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

---

堆优化版prim

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
bool vis[N];          //标记数组
int dis[N], head[N];  //dis数组存放边
int n, m, ans, cnt=1, sum;
struct node {         //链式前向星结构体
	int to, tail, nx;
}e[N];
typedef pair<int, int> pii;   
priority_queue<pii, vector<pii>, greater<pii>>q;   //优先队列，最小堆
void add(int a, int b, int c)  //链式前向星代替邻接表
{
	e[cnt].to = b;
	e[cnt].tail= c;
	e[cnt].nx = head[a];
	head[a] = cnt++;
}
 
void prime()            //堆优化prim算法核心代码段
{
	q.push(make_pair(0, 1));      //将起始节点1入队
	vis[1] = 0;
	while (!q.empty()) {
		int w = q.top().first;    //将队首的对应的值赋值给w和v，方便使用
		int v = q.top().second;
		q.pop();              //不要忘记出队
		if (vis[v])               
			continue;
		vis[v] = 1;
		sum += w;
		ans++;              //记录存放的边数
		for (int i = head[v]; i; i = e[i].nx) {       //松弛
			if (e[i].tail < dis[e[i].to]) {
				dis[e[i].to] = e[i].tail;
				q.push(make_pair(dis[e[i].to], e[i].to));  //入队
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		add(x, y, z);          //完全图，两次存入前向星中
		add(y, x, z);
	}
	memset(dis, 0x3f, sizeof(dis));     //初始化
	prime();
	if (ans == n)
		cout << sum << endl;
	else
		cout << "orz" << endl;
	return 0;
}

 OK，本次关于prim算法求最小生成树的总结就结束了，如果对于本篇总结有疑问的欢迎讨论，同时如果有错误或者待修改完善的地方，也希望能够指出，我一定会及时改正，~QVQ~