实验三最小生成树问题
班级：计科1101班
学号：05
姓名：杜茂鹏
2013年5月23日
一、实验目的
掌握图的存储表示和以及图的最小生成树算法。

二、实验内容
1.实现图的存储，并且读入图的内容。

2.利用普里姆算法求网络的最小生成树。

3.实现构造生成树过程中的连通分量抽象数据类型。

4.以文本形式输出对应图的最小生成树各条边及权值。

三、实验要求
1．在上机前写出全部源程序；
2．能在机器上正确运行程序；
3．用户界面友好。

四、概要设计、
首先采用图的邻接矩阵存储结构，然后从终端输入图的顶点名称、弧以及弧的权值建立邻接矩阵，并将图存储在文件中。

然后利用已经建好的图，分别对其进行深度、广度优先遍历，一次输出遍历的顶点
最后建立此图的最小生成树，并将对应的边及权值写入文件中。

六、详细设计
实验内容(原理、操作步骤、程序代码)
#include<>
#include<>
#include<>
#define INFINITY INT_MAX owcost!=0&&mini>cld[i].lowcost)
{
mini=cld[i].lowcost;
s1=i;
}
}
return s1;
}
void CreateUDN(MGraph &G)
{
int IncInfo;
printf("请分别输入顶点数/弧数/以及弧所含信息:");
scanf("%d %d %d",&,&,&IncInfo);
getchar();
for(int i=0;i<;i++){ dj=INFINITY;
[i][j].info=NULL;
}
for(int k=0;k<;k++)
{
char v1,v2;
int w,i,j;
printf("输入一条边依附的顶点及权值:"); dj=w;
if(IncInfo)
*[i][j].info=IncInfo;
[j][i]=[i][j];
getchar();
}
}
dj!=INFINITY)
DFS(G,j);
}
void BFSTraverse(MGraph G,void(*Visit)(MGraph G,int v))
{
LinkQueue Q;
for(int v=0;v<;v++)
visited[v]=0;
InitQueue(Q);
for(int v=0;v<;v++)
if(!visited[v])
{
visited[v]=1;
Visit(G,v);
EnQueue(Q,[v]);
while(!QueueEmpty(Q))
{
DeQueue(Q);
for(int j=0;j<;j++)
if(!visited[j]&&[v][j].adj!=INFINITY)
{
visited[j]=1;
Visit(G,j);
EnQueue(Q,[j]);
}
}
}
}
void MiniSpanTree_PRIM(MGraph G,char u)
{
FILE *IN;
if((IN=fopen("","w+"))==NULL)
{
printf("file open error!");
exit(1);
}
int k=LocateVex(G,u);
for(int j=0;j<;j++)
if(j!=k){
[j].adjvex=u;
[j].lowcost=[k][j].adj;
}
[k].lowcost=0;
for(int i=1;i<;i++){
k=minimum(G,;
printf("%c%c",[k].adjvex,[k]);
int m=LocateVex(G,[k].adjvex);
printf("%d\n",[m][k].adj);
fprintf(IN,"%c,%c,%d",[k].adjvex,[k],[m][k].adj);
fputs("\n",IN);
[k].lowcost=0;
for(int j=0;j<;j++)
if[k][j].adj<[j].lowcost)
{
[j].adjvex=[k];
[j].lowcost=[k][j].adj;
}
}
fclose(IN);
}
void menu()
{
printf("1.生成无向网G\n");
printf("2.最小生成树\n");
printf("3.深度遍历\n");
printf("4.广度遍历\n");
printf("0.退出\n");
}
int main(void)
{
MGraph G;
int m;
do
{
menu();
printf("输入你想要进行的操作的序号:");
scanf("%d",&m);
getchar();
switch(m)
{
case 1:
CreateUDN(G);
break;
case 2:
char u;
u=GetVex(G,0);
MiniSpanTree_PRIM(G,u);
break;
case 3:
DFSTraverse(G,Visit);
break;
case 4:
BFSTraverse(G,Visit);
break;
case 0:
break;
default:
break;
}
}while(m);
}
七、测试结果(截图)
主界面
八、实验心得
1拼写错误节应该避免
2尽量用通俗易懂的标示符定义函数、变量
3变量应该先定义再使用
4应该从使用者的角度考虑，做出简洁的主界面
5编好一个函数时应该加注释方便以后阅读时好理解。