实验三最小生成树问题班级：计科1101班学号：0909101605姓名：杜茂鹏2013年5月23日一、实验目的掌握图的存储表示和以及图的最小生成树算法。
二、实验内容1.实现图的存储，并且读入图的内容。
2.利用普里姆算法求网络的最小生成树。
3.实现构造生成树过程中的连通分量抽象数据类型。
4.以文本形式输出对应图的最小生成树各条边及权值。
三、实验要求1．在上机前写出全部源程序；2．能在机器上正确运行程序；3．用户界面友好。
四、概要设计、首先采用图的邻接矩阵存储结构，然后从终端输入图的顶点名称、弧以及弧的权值建立邻接矩阵，并将图存储在文件Graph.txt中。
然后利用已经建好的图，分别对其进行深度、广度优先遍历，一次输出遍历的顶点最后建立此图的最小生成树，并将对应的边及权值写入文件graph_prim.txt 中。
六、详细设计实验内容(原理、操作步骤、程序代码)#include<stdio.h>#include<stdlib.h>#include<limits.h>#define INFINITY INT_MAX //最大值#define MAX_VERTEX_NUM 20 //最大顶点个数int visited[MAX_VERTEX_NUM];typedef struct ArcCell{int adj;int *info; //该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct close{char adjvex;int lowcost;}closedge[MAX_VERTEX_NUM];typedef struct{char vexs[MAX_VERTEX_NUM]; //顶点向量AdjMatrix arcs; //邻接矩阵int vexnum,arcnum; //图的当前顶点数和弧数closedge cld;}MGraph;typedef struct QNode{char data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front1;QueuePtr rear;}LinkQueue;void (*VisitFunc)(MGraph G,int v);void DFSTraverse(MGraph G,void (* Visit)(MGraph G,int v)); void DFS(MGraph G,int v);void InitQueue(LinkQueue &Q){Q.front1=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front1)exit(0);Q.front1->next=NULL;}void EnQueue(LinkQueue &Q,char e){QueuePtr p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;}char DeQueue(LinkQueue &Q){if(Q.front1==Q.rear)exit(0);QueuePtr p=Q.front1->next;char e=p->data;Q.front1->next=p->next;if(Q.rear==p)Q.rear=Q.front1;free(p);return e;}int QueueEmpty(LinkQueue Q){if(Q.front1==Q.rear)return 1;return 0;}int LocateVex(MGraph &G,char v1){int i=0;while(!(G.vexs[i]==v1))i++;return i;}char GetVex(MGraph G,int i){char u;u=G.vexs[i];return u;}int minimum(MGraph G,closedge cld){int mini=1000,s1;for(int i=0;i<G.vexnum;i++){if(cld[i].lowcost!=0&&mini>cld[i].lowcost){mini=cld[i].lowcost;s1=i;}}return s1;}void CreateUDN(MGraph &G){int IncInfo;printf("请分别输入顶点数/弧数/以及弧所含信息:");scanf("%d %d %d",&G.vexnum,&G.arcnum,&IncInfo);getchar();for(int i=0;i<G.vexnum;i++){ //构造顶点向量printf("请输入顶点:");scanf("%c",&G.vexs[i]);getchar();}for(int i=0;i<G.vexnum;i++) //初始化邻接矩阵for(int j=0;j<G.vexnum;j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}for(int k=0;k<G.arcnum;k++){char v1,v2;int w,i,j;printf("输入一条边依附的顶点及权值:"); //构造邻接矩阵scanf("%c %c %d",&v1,&v2,&w); //输入一条边依附的顶点及权值i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j].adj=w;if(IncInfo)*G.arcs[i][j].info=IncInfo;G.arcs[j][i]=G.arcs[i][j];getchar();}}//深度优先遍历void Visit(MGraph G,int v){printf("%c",G.vexs[v]);}void DFSTraverse(MGraph G,void (* Visit)(MGraph G,int v)){VisitFunc=Visit;for(int v=0;v<G.vexnum;v++)visited[v]=0;for(int v=0;v<G.vexnum;v++)if(!visited[v]){DFS(G,v);}}void DFS(MGraph G,int v){visited[v]=1;VisitFunc(G,v);for(int j=0;j<G.vexnum;j++)if(!visited[j]&&G.arcs[v][j].adj!=INFINITY)DFS(G,j);}void BFSTraverse(MGraph G,void(*Visit)(MGraph G,int v)) {LinkQueue Q;for(int v=0;v<G.vexnum;v++)visited[v]=0;InitQueue(Q);for(int v=0;v<G.vexnum;v++)if(!visited[v]){visited[v]=1;Visit(G,v);EnQueue(Q,G.vexs[v]);while(!QueueEmpty(Q)){DeQueue(Q);for(int j=0;j<G.vexnum;j++)if(!visited[j]&&G.arcs[v][j].adj!=INFINITY) {visited[j]=1;Visit(G,j);EnQueue(Q,G.vexs[j]);}}}}void MiniSpanTree_PRIM(MGraph G,char u){FILE *IN;if((IN=fopen("graph_prim.txt","w+"))==NULL){printf("file open error!");exit(1);}int k=LocateVex(G,u);for(int j=0;j<G.vexnum;j++)if(j!=k){G.cld[j].adjvex=u;G.cld[j].lowcost=G.arcs[k][j].adj;}G.cld[k].lowcost=0;for(int i=1;i<G.vexnum;i++){k=minimum(G,G.cld);printf("%c%c",G.cld[k].adjvex,G.vexs[k]);int m=LocateVex(G,G.cld[k].adjvex);printf("%d\n",G.arcs[m][k].adj);fprintf(IN,"%c,%c,%d",G.cld[k].adjvex,G.vexs[k],G.arcs[m][k].adj);fputs("\n",IN);G.cld[k].lowcost=0;for(int j=0;j<G.vexnum;j++)if(G.arcs[k][j].adj<G.cld[j].lowcost){G.cld[j].adjvex=G.vexs[k];G.cld[j].lowcost=G.arcs[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编好一个函数时应该加注释方便以后阅读时好理解。