用贪心算法求解Prim算法上机实验报告书

算法分析与设计

实验报告

班级： 学号： 姓名：

上机时间： 2011-10-8

1

一、实验目的与要求：

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的一棵最小生成树。 五、问题分析与算法设计

六、实验结果及分析

2

七、实验总结

八、程序代码

#include #include #include #include #include #define maxint 20 #define inf 700

int AllSelected(int n,int s[]) { int i;

for(i = 1;i <= n;i++) {

if(s[i] == 0) return 0; }

return 1;

3

}

void Prim(int n,int **c) {

int lowcost[maxint]; int closest[maxint];

bool s[maxint]; s[1]=true;

for(int i=2;i<=n;i++) {

lowcost[i]=c[1][i]; closest[i]=1; s[i]=false; }

for( i=1;i<=n;i++) {

int min=inf; int j=1;

for(int k=2;k<=n;k++) {

if((lowcost[k]

min=lowcost[k]; j=k; }

s[j]=true;

for(int k=2;k<=n;k++) if((c[j][k]

void main() {

int n,i,j; int **k;

printf(\请输入顶点个数:\

4

scanf(\

k= (int **)malloc(sizeof(int *)*(n + 1)); for(i = 1;i <= n;i++)

k[i] = (int *)malloc(sizeof(int)*(n+1));

printf(\输入顶点间的权值(自己到自己为0，没有路的为大于其他任何值的数):\\n\ for(i=1;i<=n;i++) for(j=i;j<=n;j++) {

printf(\ scanf(\ k[j][i]=k[i][j]; }

printf(\

printf(\顶点\\t\ for(i=1;i<=n;i++) {

printf(\ }

printf(\ for(i=1;i<=n;i++) {

printf(\

for(j=1;j<=n;j++) { printf(\ }

printf(\ }

printf(\ Prim(n,k); }

5