在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
分享到:
相关推荐
用C++实现的图的建立 以及用普里姆算法和克鲁斯卡尔算法求图的最小生成树
若要在n个城市之间建设通信网络,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网,是一个网...(2)利用普里姆算法和克鲁斯卡尔算法求网的最小生成树; (3)按顺序输出生成树中各条边以及它们的权值。
头歌数据结构图的最小生成树算法 第1关求图(邻接矩阵存储)最小生成树的普里姆(Prim)...构造最小生成树的方法有许多种,典型的构造方法有两种,一种称作普里姆(Prim)算法,另一种称作克鲁斯卡尔(Kruskal)算法。
图的算法之一,最小生成树的普里姆算法 自己编写的,有不足的地方欢迎大家指出来
克鲁斯卡尔算法构造最小生成树 克鲁斯卡尔算法构造最小生成树
最小生成树之普里姆算法
数据结构的课程设计。用普里姆算法求图的最小生成树
最小生成树普里姆算法的实现2收集.pdf
普里姆(Prim)算法构造最小生成树 编译通过版本 可以直接运行使用
建立一个图,其存储方式采用邻接矩阵形式,利用普里姆算法和克鲁斯卡尔算法求网的最小生成树,按顺序输出生成树中各条边以及它们的权值。
1、最小生成树的概念; 2、Prim算法及其实现; 3、Kruskal算法及其实现; 4、图的表示; 5、边的表示; 6、优先队列priority_queue的自定义排序 7、大根堆、小根堆的区别 8、结构体的构建 面向对象: 有一定C++基础...
(1)利用克鲁斯卡尔算法求图的最小生成树。 (2)能实现教科书6.5节中定义的抽象数据类型MFSet.以此表示构造生成树过程中的连通分量。 (3 ) 以文本形式输出生成树中各条边以及他们的权值. 三、需求分析 1、构造...
这是课程设计试验报告 我 自己做的 数据结构最小生成树 传上来大家用用
最小生成树的经典算法。我在代码中加入了文字解释。并以算法导论第二版书中例子为例,得到了相同结果。代码很完整,也有结果显示环节。
多种方法求解最小生成树问题的PDF文件 赋权有向图的最小生成树算法; 基于Kruskal算法的最小生成树的构建; 普里姆算法和克鲁斯卡尔算法构造最小生成树; 用遗传算法求最小生成树等。
最小生成树算法,基于Vs2010,可直接运行,代码可修改
用Prim算法构造一颗最小生成树 (2) 实验原理: ①从网中任一顶点开始,先把该顶点包含在生成树中,此时生成树只有 一个顶点。 ②找出一个端点在生成树中另一端点在生成树外的所有边,并把权值最 小的边连到同它所...
用普里姆算法求最小生成树并用mfc实现界面化。输入图的信息可以画出图及最小生成树。
最小生成树之普里姆算法
利用普里姆算法求解最小生成树 利用普里姆算法求解最小生成树 利用普里姆算法求解最小生成树