PRIM算法图的最小生成树求解
评分
签名
日期
湖南商学院课程设计
设计名称 PRIM算法最小生成树求解
课程名称 算法导论
学 期 2010-2011学年第1学期 学时学分 51学时 3学分 专业班级 信科0821 组员名单 熊春辉 周伟佳 刘志超 学 号 080320637 080320638 080320625 指导老师 王 勇 提交日期 2010年 11月27日
PRIM算法最小生成树求解
一( 问题描述:
在科技发展的年代，许多问题都需要找到最简洁，最经济的
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
去加以实现。假设在n个城市之间建立通信联络网，则联通n个城市只需要n-1条线路，这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。对于n 个顶点的连通网可以建立许多不同的生成树，每一颗生成树都可以是一个连通网。现在，我们要选择这样一颗生成树，也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树的问题。可以推广到任意一个图的最小生成树问题。我们通过学习与阅读发现了PRIM算法有其解决这样问题的优越性。 二(算法设计与
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
:
1.算法设计:
构造最小生成树可以有多种算法。其中多数算法利用了最小生成树的下列一种简
V，{E})是一个连通图，U是顶点集V的一个非空子称为MST的性质:假设N=(
集。若(u,v)是一条具有最小权值的边，其中u包含于U,v包含于V-U，则必存在一颗包含边(u,v)的最小生成树。更具体地说，我们维持一个集合S包含于V，在它上面已构造了到这步为止的生成树，初始,S={s}。每次迭代我们在S
，C中增加一个结点，把结点v加入S能使“附加费用”min(e)=(u,v):u属于S(e)达到最小，并且包含了在生成树中达到这个最小值的边e=(u,v).这样解决此问题。
2.算法描述:
从U={u0}u0属于V,S={ }开始，重复执行下述步骤:在所有u属于U，v属于V-U
并入集合S，同时v0并入U，的边(u,v)属于E中找一条代价最小的边(u0,v0)
直到U=V为止，此时S中必有n-1条边，则T=(V,{S})为G的最小生成树 (3)结束
3.算法分析:
普利姆算法算法是前人的劳动成果，是正确的，对于同一个图而言，普利姆算法
2O(n)的时间复杂度，n为顶点数。
三(程序设计
1(程序设计的基本思路:。
构造图
函数
excel方差函数excelsd函数已知函数 2 f x m x mx m 2 1 4 2拉格朗日函数pdf函数公式下载
，初始状态各个顶点都是独立的，根据PRIM算法，将权排序，选择权最小的边，知道所有的顶点以n-1条边连接即结束，生成最小生成树。
2(程序内部实现的说明。
本程序采用嵌套及其循环调用的方法实现最小生成树。
采用调用PRIM算法函数void prim()。
最后的结点
最小生成树申请内存构造函数图形初始化排序函数生成
流程图:
如下图所示步骤:权值分别为1,2,3,4,5的5条边由于满足上述条件依次输出，最后生成树如图b所示。
(a)
(b)
四(测试结果及分析
1(测试报告:
特殊实例1:
输入顶点数，边数，各条路径权值
输出边路径
特殊实例2:
输入顶点数，边数，各条路径权值
输出边路径
实例3:
输入顶点数，边数，各条路径权值
输出边路径
2(分析
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
:
因此用PRIM算法求出了最小生成树，及其的解。
附录:
#include
#include
#define N 100
int p[N], key[N], tb[N][N];
void prim(int v, int n) {
int i, j;
int min;
for (i = 1; i <= n; i++)
{
p[i] = v;
key[i] = tb[v][i];
}
key[v] = 0;
for (i = 2; i <= n; i++)
{
min = INT_MAX;
for (j = 1; j <= n; j++)
if (key[j] > 0 && key[j] < min)
{
v = j;
min = key[j];
}
printf("%d%d ", p[v], v);
key[v] = 0;
for (j = 1; j <= n; j++)
if (tb[v][j] < key[j])
p[j] = v, key[j] = tb[v][j];
}
}
int main()
{
int n, m;
int i, j;
int u, v, w;
while (scanf("%d%d", &n, &m))
{
for(i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
tb[i][j] = INT_MAX;
}
while (m--)
{
scanf("%d%d%d", &u, &v, &w);
tb[u][v] = tb[v][u] = w;
}
prim(1, n);
printf("\n");
}
return 0;
}
课程设计成绩评定表
等级
成绩 优秀 良好 中等 及格 不及格 组成
1(文档很
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
。 1(文档规范。 1(文档较规范。 1(文档欠规范。 1(文档不规范。
2(排版很清晰。 2(排版清晰。 2(排版较清晰。 2(排版欠清晰。 2(排版不清晰。 报 3(内容很全面。 3(内容全面。 3(内容较全面。 3(内容欠全面。 3(内容不全面。 告 4(设计很合理。 4(设计合理。 4(设计较合理。 4(设计欠合理。 4(设计不合理。 文
档
1(算法正确。 1(算法正确。 1(算法正确。 1(算法基本正确。 1(算法不正确。
2(算法分析很全2(算法分析全面。 2(算法分析较全2(算法分析欠全2(算法分析不全算 面。 3(算法描述清晰。 面。 面。 面。 法 3(算法描述很清3(算法描述较清3(算法描述欠清3(算法描述不清分 晰。 晰。 晰。 晰。 析
1(程序设计思路很1(程序设计思路清1(程序设计思路较1(程序设计思路欠1(程序设计思路不
清晰。 晰。 清晰。 清晰。 清晰。
2(程序实现要点描2(程序实现要点描2(程序实现要点描2(程序实现要点描2(程序实现要点描程
述很清楚。 述清楚。 述较清楚。 述欠清楚。 述不清楚。 序
3(程序使用方式描3(程序使用方式描3(程序使用方式描3(程序使用方式描3(程序使用方式描设 述很清楚。 述清楚。 述较清楚。 述欠清楚。 述不清楚。 计
1(有运行结果描1(有运行结果描1(有运行结果描1(有运行结果描1(无运行结果描
述。 述。 述。 述。 述。 结 2(结果描述很清2(结果描述清晰、2(结果描述较清2(结果描述欠清2(结果描述不清果 晰、很完整。 完整。 晰、较完整。 晰、欠完整。 晰、很完整。 分 3(结果分析很深3(结果分析深入。 3(结果分析较深3(结果分析欠深3(结果分析不深
入。 入。 入。 入。 析
1(程序运行正确。 1(程序运行正确。 1(程序运行正确。 1(程序运行基本正1(程序运行不正
2(程序代码编写很2(程序代码编写整2(程序代码编写较确。 确。
整洁规范。 洁规范。 整洁规范。 2(程序代码编写欠2(程序代码编写不代
3(程序代码内有详3(程序代码内有较3(程序代码内有一整洁规范。 整洁规范。 码
细的注释。 多的注释。 些基本的注释。 3(程序代码内有较3(程序代码内没有编 少的注释。 注释。 写
综合成绩评定: 评阅老师(签章):
年 月 日
浙公网安备 33021202002483