用贪心算法求解Prim算法上机实验报告书_贪心算法设计实验报告
用贪心算法求解Prim算法上机实验报告书由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“贪心算法设计实验报告”。
算法分析与设计
实验报告
班级：学号：姓名：上机时间：
一、实验目的与要求：
1、熟悉贪心算法的基本原理和适用范围；
2、使用贪心算法编程，求解最小生成树问题。
二、实验题目：
用贪心算法求解Prim算法
三、实验内容：
任选一种贪心算法（prim或Kruskal），求解最小生成树。对算法进行
描述和复杂性分析。编程实现。
四、问题描述：
设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树的Prim
算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如
下的贪心选择：选取满足条件i∈s，j∈V-S，且c[i][j]最小的边，将顶
点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。
五、问题分析与算法设计
六、实验结果及分析
七、实验总结
八、程序代码
#include
#include
#include
#include
#include
#define maxint 20
#define inf 700
int AllSelected(int n,int s[])
{
int i;
for(i = 1;i
{
if(s[i] == 0)
return 0;
}
return 1;
}
void Prim(int n,int **c)
{
int lowcost[maxint];
int closest[maxint];
bools[maxint];s[1]=true;
for(int i=2;i
{
lowcost[i]=c[1][i];
closest[i]=1;
s[i]=false;
}
for(i=1;i
{
int min=inf;
int j=1;
for(int k=2;k
{
if((lowcost[k]
{
min=lowcost[k];
j=k;
}
s[j]=true;
for(int k=2;k
if((c[j][k]
{
lowcost[k]=c[j][k];closest[k]=j;
}
}
}
}
void main()
{
int n,i,j;
int **k;
printf(“请输入顶点个数:”);
scanf(“%d”,&n);
k=(int **)malloc(sizeof(int *)*(n + 1));
for(i = 1;i
k[i] =(int *)malloc(sizeof(int)*(n+1));
printf(“输入顶点间的权值(自己到自己为0，没有路的为大于其他任何值的数):n”);for(i=1;i
for(j=i;j
{
printf(“k[%d][%d]=k[%d][%d]=”,i,j,j,i);
scanf(“%d”,&k[i][j]);
k[j][i]=k[i][j];
}
printf(“n”);
printf(“顶点t”);
for(i=1;i
{
printf(“%dt”,i);
}
printf(“n”);
for(i=1;i
{
printf(“%dt”,i);
for(j=1;j
{
printf(“%dt”,k[i][j]);
}
printf(“n”);
}
printf(“n”);
Prim(n,k);
}
