最小生成树—普里姆与克鲁斯卡尔(贪心)_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 最小生成树—普里姆与克鲁斯卡尔(贪心)

最小生成树—普里姆与克鲁斯卡尔(贪心)

 2011/1/8 8:15:51  yzmduncan  http://yzmduncan.javaeye.com  我要评论(0)
  • 摘要:在n个城市之间铺设光缆,铺设光缆费用很高且各个城市之间铺设光缆的费用不同。如果设计目标是使这n个城市之间的任意两个城市都可以直接或间接通信,并且要使铺设光缆的费用最低,这样的问题就是一个求最小生成树的问题。解决这个问题的方法就是在有n个城市结点、n(n-1)/2条费用不同的边构成的无向连通图中找出最小生成树。最小生成树的应用相当广泛,是图论中比较基础的算法。解决最小生成树有两种算法:prim和kruskal。prim的思想:设置两个集合U和V,U中存放图G中最小生成树的结点集合
  • 标签:

????在n个城市之间铺设光缆,铺设光缆费用很高且各个城市之间铺设光缆的费用不同。如果设计目标是使这n个城市之间的任意两个城市都可以直接或间接通信,并且要使铺设光缆的费用最低,这样的问题就是一个求最小生成树的问题。解决这个问题的方法就是在有n个城市结点、n(n-1)/2条费用不同的边构成的无向连通图中找出最小生成树。

??? 最小生成树的应用相当广泛,是图论中比较基础的算法。解决最小生成树有两种算法:prim和kruskal。

??? prim的思想:

??? 设置两个集合U和V,U中存放图G中最小生成树的结点集合,V是整个结点集合。初始令U ={u0},设u0为起始点(任意设定)。从U和V/U的带权边中找出最小权值的边<u,v>,并将结点v加入到集合U中,当U=V时,构造完毕。

??? prim的设计:主要是一个lowCost数组用来存放由U到V/U的边的权值,已加入到U中的设为-1。

?

int prim()												//复杂度O(N^2)
{
	int result = 0;
	int minCost;
	int i,j,k;
	lowCost[0] = -1;									//从结点0开始
	for(i = 1; i< n; i++)
		lowCost[i] = graph[0][i];
	for(i = 1; i < n; i++)								//找n-1条边
	{
		minCost = MAX;
		for(j = 1; j < n; j++)							//找两个不想交集合的最小边
		{
			if(lowCost[j]>0 && lowCost[j]<minCost)
			{
				minCost = lowCost[j];
				k = j;
			}
		}
		lowCost[k] = -1;								//找到,标记
		result += minCost;
		for(j = 1; j < n; j++)							//加入这个结点后,更新两个集合的边。
		{
			if(graph[k][j] < lowCost[j])
				lowCost[j] = graph[k][j];
		}
	}
	return result;
}

????

kruskal思想:

??? 对图G的所有边按权值从小到大排序,每次取一条边,若此边的两个结点属于同一个连通分量,则舍弃这条边;若不属于同一个连通分量,则将这条边加入到最小生成树中。当所有结点属于同一个连通分量时,构造完毕。

??? kruskal设计:

??? 一个边的结构体。有几个关键问题:

?? 如何判断两个结点是否属于一个连通分量:

?每个连通分量都用其中一个结点来标识,p[]数组用来表示结点的父节点(初始p[i]=i),真正的头结点满足p[i]=i;首先根据传进来的边的两个顶点,用findSet找出点所属的父节点(递归,条件x==p[x]),若父节点相同,显然属于同一个连通分量,直接返回,测试下一条边;否则,合并两个连通分量。

?? 如何合并两个连通分量:

两个连通分量x,y,是将x合并到y还是y合并到x?这就用一个rank数组来确定(初始rank[]=0)。如果rank[x]>rank[y],则将y合并到x,即p[y] = x;否则,将x合并到y,即p[x] = y,如果rank[x]=rank[y],还要将rank[y]加1。

?

例:

初始传入最小边ab,rank[a]==0==rank[b],则将rank[b]加1,p[a]=b;

传入边ac,a属于分量b,c属于分量c,且rank[b]==1 > 0==rank[c],则p[c]=b;

同理传入ad,ae之后,p[d],p[e]都等于b。

传入边fg,同传入ab;

传入边bg,rank[b]==1==rank[g],则p[g]=b,rank[b]++;

传入边be,b与e同属于b,直接返回,最小生成树构造完毕!

?

??????????????????????????

#include <iostream>
using namespace std;
int n;					//结点个数
int m;					//边的条数
int p[26];				//用来寻找某个点属于的子连通图(P[i] == i)
int rank[26];			//若i属于某连通分量且p[i] = i;则用rank[i]来判断合并两个连通分量将哪个作为哪个的子集
int result;

typedef struct edge
{
	int v1;
	int v2;
	int w;
}Edge;
Edge e[75];

int cmp(const void *a, const void *b)
{
	return (*(Edge *)a).w - (*(Edge *)b).w;
}

void initial()
{
	memset(e,0,sizeof(Edge)*75);
	m = 0;
	result = 0;
}

int findSet(int x)			//找属于的集合
{
	if(x != p[x])
		p[x] = findSet(p[x]);
	return p[x];
}

void Union(int x, int y, int w)		/*****更改集合*****/
{
	if(x == y) return;
	if(rank[x] > rank[y])
	{
		p[y] = x;
	}
	else
	{
		p[x] = y;
		if(rank[x] == rank[y])
			rank[y] ++;
	}
	result += w;
}

int kruskal()
{
	int i;
	for(i = 0; i < 26; i++)
	{
		rank[i] = 0;
		p[i] = i;
	}
	qsort(e,m,sizeof(Edge),cmp);
	for(i = 0; i < m; i++)
		Union(findSet(e[i].v1), findSet(e[i].v2), e[i].w);
	return result;
}

int main()
{
	int i,j;
	char v1;
	int num;
	char v2;
	int w;
	while(cin>>n && n!=0)
	{
		initial();
		for(i = 1; i < n; i++)
		{
			cin>>v1>>num;
			for(j = 0; j < num; j++)
			{
				cin>>v2>>w;
				e[m].v1 = v1-'A';
				e[m].v2 = v2 -'A';
				e[m].w = w;
				m++;
			}
		}
		printf("%d\n",kruskal());
	}
	return 0;
}

?

?说明:参见poj1251

?

?

  • 相关文章
发表评论
用户名: 匿名