算法分析与设计四次实验.pdfVIP

算法分析与设计实验日志

实验时间：2014年11月4日

学院计算机科学与技术学院专业网络工程

班0431201学号2012211758S331

实验题目：

采用普里姆(prim)算法构造网络的最小生成树

采用克鲁斯卡尔(kruskal)算法构造网络的最小生成树

实验目的：

深入理解最小生成树的概念，熟练掌握普里姆（prim），克鲁斯卡尔（kruskal）算法的工

作过程，并通过定义合适的数据结构

实验主要步骤：

实验源程序如下：

Prim算法

#includestdio.h

#includecstdlib

#includememory.h

constintMax=0x7fffffff;

constintN=50;

intn;

intg[N][N],dis[N],visited[N];

intprim()

{

inti,j;

intpos,min;

intans=0;

memset(visited,0,sizeof(visited));

visited[1]=1;pos=1;

//assignavaluetothedis[N]first

for(i=2;i=n;i++)

dis[i]=g[pos][i];

for(i=1;in;i++)

{

min=Max;

for(j=1;j=n;j++)

{

if(visited[j]0mindis[j])

{

min=dis[j];

pos=j;

}

}

printf(Thenodebeingtraversedis:%d\n,pos);

ans+=min;

printf(Thevalueofansis%ns);

//markthenode

visited[pos]=1;

//updatetheweight

for(j=1;j=n;j++)

if(visited[j]0dis[j]g[pos][j])

dis[j]=g[pos][j];

}

returnans;

}

intmain()

{

inti=1,j=1;

intans=0;

intw;

printf(Pleaseenterthenumberofthenodes:\n);

scanf(%d,n);

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

for(j=1;j=n;j++)

{

if(ij)

g[i][j]=0;

else

g[i][j]=Max;

}

printf(Pleaseenterthenumberoftheedges:\n);

intedgenum;

scanf(%d,edgenum);

intv1,v2;

printf(Pleaseenterthenum