PRIM算法图的最小生成树求解.doc

PRIM算法图的最小生成树求解
评分
签名
日期
湖南商学院课程设计
设计名称 PRIM算法最小生成树求解
课程名称 算法导论
学 期 2010-2011学年第1学期 学时学分 51学时 3学分 专业班级 信科081(程序设计的基本思路:。
构造图函数，初始状态各个顶点都是独立的，根据PRIM算法，将权排序，选择权最小的边，知道所有的顶点以n-1条边连接即结束，生成最小生成树。
2(程序内部实现的说明。
本程序采用嵌套及其循环调用的方法实现最小生成树。
采用调用PRIM算法函数void prim()。
最后的结点
最小生成树申请内存构造函数图形初始化排序函数生成
流程图:
如下图所示步骤:权值分别为1,2,3,4,5的5条边由于满足上述条件依次输出，最后生成树如图b所示。
(a)
(b)
四(测试结果及分析
1(测试报告:
特殊实例1:
输入顶点数，边数，各条路径权值
输出边路径
特殊实例2:
输入顶点数，边数，各条路径权值
输出边路径
实例3:
输入顶点数，边数，各条路径权值
输出边路径
2(分析总结:
因此用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;
}
课程设计成绩评定表
等级
成绩 优秀 良好 中等 及格 不及格 组成