POJ-1287-Networking
http://poj.org/problem?id=1287
赤裸裸的最小生成树
最小生成树也称最小代价树,即各边的代价之和最小
最小生成树可用Prim算法,也可用Kruskal算法
Prim算法是基于顶点来实现最小生成树,Kruskal算法是基于边来实现最小生成树
Prim算法:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxvalue 0x7fffffff
int map[105][105];
int n;
int prim()
{
int i,j,temp,v,sum;
int visit[105],dis[105];
for(i=1;i<=n;i++)
dis[i]=map[1][i];
dis[1]=0;
memset(visit,0,sizeof(visit));
visit[1]=1;
sum=0;
for(i=1;i<n;i++)
{
temp=maxvalue;
for(j=1;j<=n;j++)
if(visit[j]==0&&dis[j]<=temp)
{
temp=dis[j];
v=j;
}
sum+=temp;
visit[v]=1;
for(j=1;j<=n;j++)
if(visit[j]==0&&map[v][j]<dis[j])
dis[j]=map[v][j];
}
return sum;
}
int main()
{
int i,j,t;
int a,b,c,ans;
while(scanf("%d",&n),n)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
map[i][j]=maxvalue;
scanf("%d",&t);
while(t--)
{
scanf("%d %d %d",&a,&b,&c);
if(map[a][b]>c)
{
map[a][b]=map[b][a]=c;
}
}
ans=prim();
printf("%d\n",ans);
}
return 0;
}
Kruskal算法:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxvalue 0x7fffffff
struct cam
{
int x;
int y;
int len;
}list[2005]; //开始数组开小了,WA了好几次
int f[105];
int n;
int cmp(const void *a,const void *b)
{
return (*(struct cam *)a).len-(*(struct cam *)b).len;
}
void init() //并查集判断两个顶点是否在不同的分图中
{
int i;
for(i=1;i<=n;i++)
f[i]=i;
}
int find(int x)
{
int r=x;
while(f[r]!=r)
r=f[r];
f[x]=r;
return r;
}
int Union(int x,int y)
{
int fx,fy;
fx=find(x);
fy=find(y);
if(fx!=fy)
{
f[fx]=fy;
return 1;
}
return 0;
}
int main()
{
int i,t;
int num,ans;
while(scanf("%d",&n),n)
{
scanf("%d",&t);
for(i=0;i<t;i++)
scanf("%d %d %d",&list[i].x,&list[i].y,&list[i].len);
qsort(list,t,sizeof(struct cam),cmp);
num=1;
ans=0;
init();
for(i=0;i<t;i++)
{
if(Union(list[i].x,list[i].y))
{
num++;
ans+=list[i].len;
if(num==n) //当集合中有n个点时即退出
break;
}
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
头歌数据结构图的最小生成树算法 第1关求图(邻接矩阵存储)最小生成树的普里姆(Prim)算法 第2关求图(邻接表存储)最小生成树的普里姆(Prim)算法 第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)...
最小生成树最小生成树最小生成树最小生成树最小生成树
代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小...
如何以最低的经济代价建设这个通信网,是一个网的最小生成树问题 2、利用克鲁斯卡尔算法求网的最小生成树; 3、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列; 4、输入为存在边的顶点对,以及它们之间...
问题描述:给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。基本要求:1、城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义...
最小生成树课程设计,给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。构造可以使n个城市连接的最小生成树
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
最小生成树的构造,以及求最小生成树的 普利姆算法和克鲁斯卡尔算法,C++实现算法
上窗体上有几个点,点击这些点形成连线,安最小生成树获得这些点的最小生成树
(1)、实验题目:给定一个地区的n 个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并得到的最小生成树的代价。 (2)、实验要求: 1、城市间的距离网采用的邻接矩阵表示,邻接矩阵的存储结构定义采用...
采用堆排序实现带权值的边的顺序排列 利用克鲁斯卡尔算法实现最小生成树 首先 n城市之间全连接 输出所有连接和其边的权值 最后输出n个城市之间通信代价最小的最小生成树。 可用于java数据结构课程设计:“若要在n个...
最小生成树 实验内容: 设G=(V,E)是无向图联通带权图,即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的一个子图G’是一棵包含G的所有定点的树,则称G’为G的生成树。生成树上各边权的总和称为该生成树的...
用Prim算法构造一颗最小生成树 (2) 实验原理: ①从网中任一顶点开始,先把该顶点包含在生成树中,此时生成树只有 一个顶点。 ②找出一个端点在生成树中另一端点在生成树外的所有边,并把权值最 小的边连到同它所...
最小生成树_Prim算法实现C++ 最小生成树_Prim算法实现C++ 最小生成树_Prim算法实现C++
Prim最小生成树Prim最小生成树Prim最小生成树
最小生成树是图论中的经典问题,也是一个重要部分,一般书上往往只介绍求最小生成树的算法,而忽略了更精彩的算法应用部分。本文将对最小生成树算法及其应用作全面的分析说明,使大家对此有更加深刻的认识。本文分三...
多种方法求解最小生成树问题的PDF文件 赋权有向图的最小生成树算法; 基于Kruskal算法的最小生成树的构建; 普里姆算法和克鲁斯卡尔算法构造最小生成树; 用遗传算法求最小生成树等。
最小生成树问题时指在由m个节点和n条边组成的网络模型中寻找连接所有节点的生成树,使得其所有边的权值之和最小。最小生成树问题广泛应用于系统设计、选址规划等组合优化问题中。
关于构建最小生成树的实验报告,里面是C代码,有详细的过程描述,PRIM算法
利用克鲁斯卡尔算法求网的最小生成树。要求:若要在n各城市之间建设通信网络,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网络,是一个网的最小生成树问题。