最小生成树prim算法 | Eternal_zttz

最小生成树prim算法

今天上机刷练习赛,遇到了一道求最小生成树的题目,然后就卡死在这一题了。(emmm,天知道wo上个学期学了图算法后就再也没有碰过有关图的问题了)。

然而题目还是要做的,遂在网上blog里游荡了一番,又重新拾起了遗忘已久的prim和kruskal算法。

至此记录一波~

Prim 算法

历史概览

普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法 –百度百科

算法思想

Prim算法本质上使用的是一种贪心策略,算法的基本思路如下:

  1. 从任意点开始,将该点设为源点。将整个图分为两个部分V,U,其中,V代表已经选过的点的集合,U代表还未选过的点的集合。最初,V中只有源点一个元素。
  2. 从U中元素选择一个离V中元素最近的一个点,将该点加入到V中。
  3. 重复2操作n-1次,知道所有的点都在V中,此时算法结束。

这里我们以洛谷P3366模版题为例

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <cstring>
#define MaxInt 999999
#define N 5001
long long e[N][N],low[N],vis[N];//e代表边集合,low[i]代表从U中点i到V中各元素的最小距离,vis数组记录元素是在V中或是U中
long long ans;
int n,m,k,flag;
void prim(){
int s = 1;
//初始low数组
for (int i = 1;i<=n;i++){
low[i] = e[s][i];
}
vis[s] = 1;//将s点加入到集合V中
for (int j = 1;j<n;j++){
long long min = MaxInt;
//从未被访问的点中选一个最小的点
for (int i = 1;i<=n;i++){
if(!vis[i]&&low[i]<min){//!vis[i]代表元素在U中,low[i]是点i到V的最小距离,这里是为了找一个最近的点
min = low[i];
flag = i;
}
}
ans+=min;
vis[flag] = 1;//将点加入到V中
//更新各点的最短距离,因为有新点加入到V中,如果这个新点对U中的点的距离小于原距离,更新此距离
for (int i = 1;i<=n;i++){
if(e[flag][i]<low[i])
low[i] = e[flag][i];
}
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i =1 ;i<=n;i++){
for (int j =1;j<=n;j++)
e[i][j] = MaxInt;
}
for (int i = 0;i<m;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
if(e[a][b]>c){//这里是为了对重边进行处理
e[a][b] = c;
e[b][a] = c;
}
}
prim();
printf("%lld\n",ans);
}

这里是用邻接矩阵存图,算法的时间复杂度为O(n^2).
此代码对于洛谷的模版题可以过7个数据点,因为为邻接矩阵存图,空间消耗太大,对于剩下的三个测试点会有MLE错误。

-------------The End-------------