Prim与kruskal算法详解
|
441
|
kruskal,prim,图论,最小(大)生成树,模板,算法
|
Dewct

1618 字
|
7 分钟

首先，我们来看看这两种算法的效率，当然，prim和Dijkstra算法有异曲同工之妙，既然Dijkstra能用堆优化，prim当然也可以。
以下测试数据转自http://blog.csdn.net/gykimo/article/details/8538275
评测环境：WindowsXP，FreePascal2.40，Pentium（R） Dual-Core CPU T4300@2.10GHz，2G内存





通过上图可以看出：
1.Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。
2.Prim+Heap在任何时候都有令人满意的的时间复杂度，但是代价是空间消耗极大。【以及代码很复杂>_<】
3.时间复杂度并不能反映出一个算法的实际优劣。
竞赛所给的题大多数是稀疏图，所以尽可能地使用Prim+Heap吧，在稀疏图中这是无敌的。如果一定要在朴素Prim和Kruskal里选一个的话那就用Kruskal吧。当然Prim的代码比较简单，对付水题用Prim也无所谓，只要不是极稀疏图两者相差不大
 发表一下个人观点，还是kruskal好使，代码短，还好写。

一、prim

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
算法简单描述
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
 
下面对算法的图例描述

图例 说明 不可选 可选 已选（Vnew）
此为原始的加权连通图。每条边一侧的数字代表其权值。 – – –
顶点D被任意选为起始点。顶点A、B、E和F通过单条边与D相连。A是距离D最近的顶点，因此将A及对应边AD以高亮表示。 C, G A, B, E, F D
下一个顶点为距离D或A最近的顶点。B距D为9，距A为7，E为15，F为6。因此，F距D或A最近，因此将顶点F与相应边DF以高亮表示。 C, G B, E, F A, D
算法继续重复上面的步骤。距离A为7的顶点B被高亮表示。 C B, E, G A, D, F
在当前情况下，可以在C、E与G间进行选择。C距B为8，E距B为7，G距F为11。E最近，因此将顶点E与相应边BE高亮表示。 无 C, E, G A, D, F, B
这里，可供选择的顶点只有C和G。C距E为5，G距E为9，故选取C，并与边EC一同高亮表示。 无 C, G A, D, F, B, E
顶点G是唯一剩下的顶点，它距F为11，距E为9，E最近，故高亮表示G及相应边EG。 无 G A, D, F, B, E, C
现在，所有顶点均已被选取，图中绿色部分即为连通图的最小生成树。在此例中，最小生成树的权值之和为39。 无 无 A, D, F, B, E, C, G

 
简单证明prim算法
反证法：假设prim生成的不是最小生成树
1).设prim生成的树为G0
2).假设存在Gmin使得cost(Gmin)<cost(G0)   则在Gmin中存在<u,v>不属于G0
3).将<u,v>加入G0中可得一个环，且<u,v>不是该环的最长边(这是因为<u,v>∈Gmin)
4).这与prim每次生成最短边矛盾
5).故假设不成立，命题得证.
时间复杂度

这里记顶点数v，边数e
邻接矩阵:O(v2)                 邻接表:O(elog2v)
代码实现（来自POJ1789）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char a[23333][10];
int d[233333];
int n;
bool used[23333];
int map[2005][2005];
int prim()
{
	memset(used, 0, sizeof(used));
	memset(d, 0x3f, sizeof(d));
	d[1] = 0;
	int res = 0;
	while(1)
	{
		int v = -1;
		for(int u = 1;u <= n;u ++)
		{
			if(!used[u] && (v == -1|| d[u] < d[v]))
				v = u;
		}
		if(v == -1)
			break;
		used[v] = 1;
		res += d[v];
		for(int u = 1;u <= n;u ++)
		{
			d[u] = min(d[u], map[v][u]);
		}
	}
	return res;
}
int main()
{
	while(scanf("%d", &n)!=EOF)
	{
		if(n == 0)
			break;
		for(int i = 1;i <= n;i ++)
			scanf("%s", a[i]+1);
		int ans = 0;
		for(int i = 1;i <= n;i ++)
		{
			for(int k = i;k <= n;k ++)
			{
				ans = 0;
				if(k == i)
					continue;
				for(int j = 1;j <= 7;j ++)
				{
					if(a[i][j] != a[k][j])
					{
						ans ++;
					}
				}
				map[i][k] = ans;
				map[k][i] = ans;
			}
		}
		printf("The highest possible quality is 1/%d.\n", prim());
	}
	return 0;
}

二、prim+heap

与上面的思想一样，只是我用一个优先队列去维护一下，就可以加快速度了。
codevs1231 最优布线问题亲测 kruskal 179ms prim+heap 123ms
再加上本文开头转载的图片可以看出，prim+heap是很吊的，尤其是对于稠密图，例如poj 1789 Truck History就只能用prim做，因为边数实在太多。
代码实现（基于codevs1231）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN = 1e5+5;
int n, m;
int first[MAXN], next[MAXN << 1], tot = 0;
bool used[MAXN];
struct edge
{
	int from, to, cost;
	bool operator < (const edge &b)const
	{
		return cost > b.cost;
	}
}es[MAXN << 1];
priority_queue <edge> q;
void init()
{
	memset(first, -1, sizeof(first));
	tot = 0;
}
void build(int f, int t, int d)
{
	es[++tot] = (edge){f, t, d};
	next[tot] = first[f];
	first[f] = tot;
}
long long prim(int s)
{
	memset(used, 0, sizeof(used));
	long long ans = 0;
	int now = s;
	used[s] = 1;
	for (int i = first[s]; i != -1; i = next[i])
		q.push(es[i]);
	while (!q.empty())
	{
		edge u = q.top();
		q.pop();
		int v = u.to;
		if (used[v])
			continue;
		ans += u.cost;
		used[v] = 1;
		for (int i = first[v]; i != -1; i = next[i])
		{
			if (!used[es[i].to])
			{
				q.push(es[i]);
			}
		}
	}
	return ans;
}
int main()
{
	init();
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		int f, t, d;
		scanf("%d%d%d", &f, &t, &d);
		build(f, t, d);
		build(t, f, d);
	}
	printf("%lld", prim(1));
	return 0;
}

三、Kruskal

kruskal是对所有边进行排序，然后选权值最小的边连接，然后用并查集进行维护，就可以在O（eloge）的时间内求解，e为边数，所以当边数很大时会很慢。
代码实现（基于codevs1231）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int fa[1000005], tot = 0;
struct edge
{
	int from, to, cost;
}es[233333];
void build(int f, int t, int d)
{
	es[++tot] = (edge){f, t, d};
}
int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool cmp(edge a, edge b)
{
	return a.cost < b.cost;
}
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int f, t, d;
		scanf("%d%d%d", &f, &t, &d);
		build(f, t, d);
		build(t, f, d);
	}
	sort(es + 1, es + tot + 1, cmp);
	for (int i = 1; i <= tot; i++)
		fa[i] = i;
	long long ans = 0;
	for (int i = 1; i <= tot; i++)
	{
		int x = es[i].from, y = es[i].to;
		if (find(x) != find(y))
		{
			fa[find(x)] = find(y);
			ans += es[i].cost;
		}
	}
	cout << ans;
	return 0;
}

 

上一篇
下一篇