最小生成树-实验报告

1、实验五 最小生成树一、需求分析1、本程序目是要建设一个最经济网，输出相应最小生成树。在这里都用整型数来代替。2、测试数据见下程序。二、概要设计主程序：int main()初始化；while (条件) 接受命令; 处理命令;return 0;三、详细设计#include/头文件using namespace std;#define MAX_VERTEX_NUM 20/最大结点数#define MAX 200typedef struct Close/结构体char adjvex;int lowcost;Close,closeMAX_VERTEX_NUM;typedef struct ArcNode

2、int adjvex;ArcNode *nextarc;int info;ArcNode;typedef struct VNodechar data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList verties;int vexnum,arcnum;ALGraph;ALGraph G;/对象Gint LocateVek(ALGraph ,char );/返回结点位置int minimum(close);/返回最小数void MinSpanTree_PRIM(ALGraph,char);/最小生成树void

3、Create(ALGraph &);/创建邻接表int main()char a;int i=1;Create(G);/*for(int i=1;inextarc)coutG.vertiesi.data-adjvex.data=infoendl;*/while(i)couta;MinSpanTree_PRIM(G,a);couti;return 0;int LocateVek(ALGraph G,char u)int i;for(i=1;i=G.vexnum;i+)if(u=G.vertiesi.data)return i;return -1;int minimum(close m)/返回最小

4、数int i=0,j,n=200;for(i=1;i=G.vexnum;i+)if(mi.lowcostn&mi.lowcost!=0)n=mi.lowcost;j=i;return j;void MinSpanTree_PRIM(ALGraph G,char u)int j,k,a;close closedge;ArcNode *s,*p,*q;for(j=1;j=MAX_VERTEX_NUM;j+)closedgej.lowcost=MAX;/把所有值都赋为最大k=LocateVek(G,u);for(j=1;jnextarc)if(j=s-adjvex)closedgej.lowcost

5、=s-info;break;closedgek.lowcost=0;cout最小生成树 : ;/查找并输出最小生成树for(j=1;jG.vexnum;j+)k=minimum(closedge);cout(closedgek.adjvex,G.vertiesk.data);closedgek.lowcost=0;for(int i=1;inextarc)if(p-infoadjvex)closedgei.adjvex=G.vertiesk.data;closedgei.lowcost=p-info;coutendl;cout边及对应权值: =1;j-)if(closedgej.lowcost

6、=0&G.vertiesj.data!=u)cout(closedgej.adjvex,G.vertiesj.datanextarc)if(a-64=q-adjvex)coutinfoendl;void Create(ALGraph &G)int i,j,k,x;char a,b;ArcNode *s;coutG.vexnum;coutG.arcnum;cout输入顶点信息:endl;for(i=1;iG.vertiesi.data;G.vertiesi.firstarc=NULL;for(i=1;i=G.arcnum;i+)coutab;cinx;j=a-64;k=b-64;/将字符型转化成整数型s=new ArcNode;s-info=x;s-adjvex=k;s-nextarc=G.vertiesj.firstarc;G.vertiesj.firstarc=s;s=new ArcNode;s-info=x;s-adjvex=j;s-nextarc=G.vertiesk.firstarc;G.vertiesk.firstarc=s;四、调试分析 1、在写程序时遇到很多有关专业名词C语言编译，没有完全套用书上固有解释，而是按照自己有限英语词汇理解去编译。 2、通过求最小生成树，进一步掌握了图含义。五、运行结果六、实验环境（1）Wi