最小生成树-课程设计报告

课程设计报告问题描述:已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小

需求分析：在N地建设网络保证连通即可求最小的架设方式，任务完成可分为两个部分：A存储N中任意两地之间的权（采用邻接表，邻接矩阵）B用prim和克鲁斯卡尔两种算法分别求出N地中最优架设方式即最小生成树。C按顺序输出生成树中各条边以及它们的权值。概要设计：程序分为两大部分1存储部分，2算法部分；存储部分分为邻接矩阵和邻接表，而且包含了两者直接的互相转换；算法部分分为普里母算法和克鲁斯卡尔算法。Prim算法的思想：假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树:1:初始化:U={u0},TE={f}。此步骤设立一个只有结点u0的结点集U和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。2:在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u0,v0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U中,其次边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。3:如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。用代码实现为：voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){//算法7.9//用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。//记录从顶点集U到V－U的代价最小的边的辅助数组定义：//struct{//VertexTypeadjvex;//VRTypelowcost;//}closedge[MAX_VERTEX_NUM];inti,j,k;k=LocateVex(G,u);for(j=0;j<G.vexnum;++j){//辅助数组初始化if(j!=k){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;}}closedge[k].lowcost=0;//初始，U＝{u}for(i=1;i<G.vexnum;++i){//选择其余G.vexnum-1个顶点k=minimum(closedge);//求出T的下一个结点：第k顶点//此时closedge[k].lowcost=//MIN{closedge[vi].lowcost|closedge[vi].lowcost>0,vi∈V-U}printf(closedge[k].adjvex,G.vexs[k]);//输出生成树的边closedge[k].lowcost=0;//第k顶点并入U集for(j=0;j<G.vexnum;++j)if(G.arcs[k][j].adj<closedge[j].lowcost){//新顶点并入U后重新选择最小边//closedge[j]={G.vexs[k],G.arcs[k][j].adj};closedge[j].adjvex=G.vexs[k];closedge[j].lowcost=G.arcs[k][j].adj;}}}//MiniSpanTree克鲁斯卡尔算法的思想为：假设WN=(V,{E})是一个含有n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。详细设计：(a)程序中结构体定义：typedefstructEdgeType{ intu;//边的起始顶点 intv;//边的终止顶点 intw;//边的权}EdgeType;//以下定义邻接矩阵类型typedefstruct{intnunber;//顶点编号InfoTypeinfo;//顶点其他信息}VertexType;//顶点类型typedefstruct//图的定义{intedges[maxv][maxv];//邻接矩阵intn,e;//顶点数，弧数VertexTypevexs[maxv];//存放顶点信息}MGraph;//图的邻接矩阵类型//以下定义邻接表类型typedefstructANode//弧的结点结构类型{intadjvex;//该弧的终点位置InfoTypeinfo;//该弧的相关信息,这里用于存放权值structANode*nextarc;//指向下一条弧的指针}ArcNode;typedefstructVnode//邻接表头结点的类型{Vertexdata;//顶点信息intcount;//存放顶点入度,只在拓扑排序中用ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[maxv];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中顶点数n和边数e}ALGraph;//图的邻接表类型(b)程序中用来实现邻接矩阵和邻接表存储以及互相转化的函数voidMatToList(MGraphg,ALGraph*&G)//将邻接矩阵g转换成邻接表GvoidListToMat(ALGraph*G,MGraph&g)//将邻接表G转换成邻接矩阵gvoidDispMat(MGraphg)//输出邻接矩阵gvoidDispAdj(ALGraph*G)//输出邻接表G起运行结果为：(c)程序中用来完成prim和kriuskal算法的函数voidCreateMat(MGraph&g,intA[][maxv],intn)//输入邻接矩阵voidPrim(MGraphg,intv)//prim算法voidInsertSort(EdgeTypeE[],intn)//对E[0...n-1]按权值递增有序的进行直接插入排序voidKriuskal(MGraphg,intn)//克鲁斯卡尔算法起运行结果为：主函数模块为：voidmain(){ inti,j,A[maxv][maxv],v0; MGraphg,g1;ALGraph*G; printf("说明：\n1首先应该将N地有顺序编号从0到(N-1)\n2其次在编号过程中已经将0点标记给任意选取的初始结点\n3运行时以4地之间的无向有权图为例如果还原成N地只需将代码中注释部分去掉\n\n\n\n");printf("输入A[%d][%d]矩阵用来表示N地两两之间的权值:(0代表没有边)\n",maxv,maxv); /*for(i=0;i<maxv;i++)//输入邻接矩阵 for(j=0;j<maxv;j++) scanf("%d",&A[i][j]); printf("输入起始顶点V0:\n"); scanf("%d",&v0);*/为了方便现将输入注视掉，运用以下数据进行运算v0=0;A[0][0]=0; A[0][1]=1;A[0][2]=2;A[0][3]=0;A[1][0]=1;A[1][1]=0;A[1][2]=3;A[1][3]=0;A[2][0]=2;A[2][1]=3;A[2][2]=0;A[2][3]=4;A[3][0]=0;A[3][1]=0;A[3][2]=4;A[3][3]=0;g.n=4;g.e=4;for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g.edges[i][j]=A[i][j];printf("\n");printf("您输入的N地之间的邻接矩阵:\n");DispMat(g);G=(ALGraph*)malloc(sizeof(ALGraph));printf("将N地的邻接矩阵转换成邻接表存储:\n");MatToList(g,G);DispAdj(G);printf("将N地的邻接表转换成邻接矩阵存储:\n");for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g1.edges[i][j]=0;ListToMat(G,g1);DispMat(g1);printf("\n");printf("用普里姆算法求得N地之间架设方法为:\n\n\n"); CreateMat(g,A,maxv); Prim(g,v0); printf("\n\n\n\n"); printf("用克鲁斯卡尔算法求得N地之间架设方法为:\n\n\n");Kriuskal(g,g.e);}（d）调试分析：经过努力，课程设计终于完成，由于我对数据结构和c语言不是很了解，有时忽略了一些关键的细节，使得在编写程序的过程中出现了一些问题。对于打字有时粗心导致出现一些难以发现的小错误，在我们的耐心，细致的调试下最终使得程序能够运行，课程设计完满完工测试数据是一个二元数组A其具体赋值为：A[0][0]=0; A[0][1]=1;A[0][2]=2;A[0][3]=0;A[1][0]=1;A[1][1]=0;A[1][2]=3;A[1][3]=0;A[2][0]=2;A[2][1]=3;A[2][2]=0;A[2][3]=4;A[3][0]=0;A[3][1]=0;A[3][2]=4;A[3][3]=0;求的最小生成树的结果为：Prim算法假设网中有N个顶点，则第一个进行初始化的循环语句频度为n，第二个循环语句的频度为n-1。其中有两个内循环；由此普里母算法的时间复杂度为O(n2),与网中的边数无关！克鲁斯卡尔算法至多对e条边各扫描一次时间复杂度为O（eloge）。（e）课程总结认识：对于建立n地最小生成树问题是将数据结构的知识运用于实现现实问题，在程序设计过程中对于我来说十分繁杂，我先后请教了4位老师才将每一块的具体实现办法理解了！搭建框架是十分必要的，只有有了框架才能在具体实现上一步一步的完成。在具体实现算法是出现了问题：例如prim算法实现的时候没有办法记录起始点，再输出边的过程中出现错误，经过上网查阅资料才建立了数组point[]将其解决。再调试程序过程中也是相当繁琐，代码写完了但是运行过程中出现了很多很错错误，在运用debug来观测数据后才渐渐的将错误解决。编写程序是一件幸苦但又愉快的过程，在学完C语言是并没有什么太多的算法思想，但数据结构给了我很多灵感，有了数据结构的思想很多实际问题就能解决了，主要由于代码接触太少，所以在有了思想的情况下很难实现代码，以后要经常去用代码实现自己的想法，算法对于程序设计十分重要，数据结构可以说是编程者的大脑，没有数据结构代码就失去了运用于实际问题的能力。心得：在课程设计的过程中收获很多，独立思考是我首先觉悟到的，因为起初在看到繁杂的代码满脑子只有愤怒，自己根本没有办法实现，可后来在经过上网查阅思想和数据结构书我才慢慢的有了自己的想法。最后渐渐的喜欢上了代码，课程设计的确让我有一种成为编程人员的感觉了，经过努力我终于完成了本次课程设计，通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。我们本次做的是图的做小生成树问题，深刻的体会到它的实用性。通过本次课程设计我们发现我们对于C语言和数据结构还有很多地方不知道，今后需要努力学习。-------------------------------------------------------------------------------------------------------参考文献：[1]李云清，杨庆红.数据结构（C语言版）.北京：人民邮电出版社，2004.[2]严蔚敏,吴伟民.数据结构（C语言版）.北京：清华大学出版.1997.[3]苏光奎,李春葆.数据结构导学.北京:清华大学出版.2002.[4]周海英，马巧梅，靳雁霞.数据结构与算法设计.北京：国防工业出版社，2007.[5]张海藩.软件工程导论.北京：清华大学出版社.2003.[6]互联网附录：程序清单#include"stdafx.h"#include"stdlib.h"typedefintInfoType;typedefintVertex;#definemaxv4//图的顶点数#defineinf100000000//两顶点无相邻边时的权typedefstructEdgeType{ intu;//边的起始顶点 intv;//边的终止顶点 intw;//边的权}EdgeType;//以下定义邻接矩阵类型typedefstruct{intnunber;//顶点编号InfoTypeinfo;//顶点其他信息}VertexType;//顶点类型typedefstruct//图的定义{intedges[maxv][maxv];//邻接矩阵intn,e;//顶点数，弧数VertexTypevexs[maxv];//存放顶点信息}MGraph;//图的邻接矩阵类型//以下定义邻接表类型typedefstructANode//弧的结点结构类型{intadjvex;//该弧的终点位置InfoTypeinfo;//该弧的相关信息,这里用于存放权值structANode*nextarc;//指向下一条弧的指针}ArcNode;typedefstructVnode//邻接表头结点的类型{Vertexdata;//顶点信息intcount;//存放顶点入度,只在拓扑排序中用ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[maxv];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中顶点数n和边数e}ALGraph;//图的邻接表类型//将邻接矩阵g转换成邻接表GvoidMatToList(MGraphg,ALGraph*&G){inti,j,n=g.n;//n为顶点数ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)//给邻接表中所有头结点的指针域置初值G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++)//检查邻接矩阵中每个元素for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0)//邻接矩阵的当前元素不为0{p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点*pp->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc;//将*p链到链表后G->adjlist[i].firstarc=p;}G->n=n;G->e=g.e;}voidListToMat(ALGraph*G,MGraph&g)//将邻接表G转换成邻接矩阵g{inti,n=G->n;ArcNode*p;for(i=0;i<n;i++){p=G->adjlist[i].firstarc;while(p!=NULL){g.edges[i][p->adjvex]=p->info;p=p->nextarc;}}g.n=n;g.e=G->e;}voidDispMat(MGraphg)//输出邻接矩阵g{inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++)if(g.edges[i][j]==0)printf("%3s","∞");elseprintf("%3d",g.edges[i][j]);printf("\n");}}voidDispAdj(ALGraph*G)//输出邻接表G{inti;ArcNode*p;for(i=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("%3d:",i);while(p!=NULL){printf("%3d",p->adjvex);//输出该弧的终点位置p=p->nextarc;}printf("\n");}}voidCreateMat(MGraph&,int[][maxv],int);voidPrim(MGraph,int);voidInsertSort(EdgeType[],int);voidKriuskal(MGraph,int);voidmain(){ inti,j,A[maxv][maxv],v0; MGraphg,g1;ALGraph*G; printf("说明：\n1首先应该将N地有顺序编号从0到(N-1)\n2其次在编号过程中已经将0点标记给任意选取的初始结点\n3运行时以4地之间的无向有权图为例如果还原成N地只需将代码中注释部分去掉\n\n\n\n");printf("输入A[%d][%d]矩阵用来表示N地两两之间的权值:(0代表没有边)\n",maxv,maxv); /*for(i=0;i<maxv;i++)//输入邻接矩阵 for(j=0;j<maxv;j++) scanf("%d",&A[i][j]); printf("输入起始顶点V0:\n"); scanf("%d",&v0);*/v0=0;A[0][0]=0; A[0][1]=1;A[0][2]=2;A[0][3]=0;A[1][0]=1;A[1][1]=0;A[1][2]=3;A[1][3]=0;A[2][0]=2;A[2][1]=3;A[2][2]=0;A[2][3]=4;A[3][0]=0;A[3][1]=0;A[3][2]=4;A[3][3]=0;g.n=4;g.e=4;for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g.edges[i][j]=A[i][j];printf("\n");printf("您输入的N地之间的邻接矩阵:\n");DispMat(g);G=(ALGraph*)malloc(sizeof(ALGraph));printf("将N地的邻接矩阵转换成邻接表存储:\n");MatToList(g,G);DispAdj(G);printf("将N地的邻接表转换成邻接矩阵存储:\n");for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g1.edges[i][j]=0;ListToMat(G,g1);DispMat(g1);printf("\n");printf("用普里姆算法求得N地之间架设方法为:\n\n\n"); CreateMat(g,A,maxv); Prim(g,v0); printf("\n\n\n\n"); printf("用克鲁斯卡尔算法求得N地之间架设方法为:\n\n\n");Kriuskal(g,g.e);}voidCreateMat(MGraph&g,intA[][maxv],intn)//输入邻接矩阵{ inti,j; g.n=n; g.e=0; for(i=0;i<n;i++) for(j=0;j<n;j++) { if(A[i][j]!=0){ g.edges[i][j]=A[i][j]; g.e++; } else g.edges[i][j]=inf; } }voidPrim(MGraphg,intv){ inti,j,n=maxv; intmin; intpoint[maxv],key[maxv]; for(i=0;i<n;i++) { point[i]=v;//所有point均存有V key[i]=g.edges[v][i];//记录所有以V为起点的边的权 } key[v]=0;//将起点V到V的权值设为0 for(i=1;i<n;i++) { min=inf; for(j=0;j<n;j++) if(key[j]>0&&key[j]<min) { v=j; min=key[j]; } printf("边(%d,%d):%d\n\n\n",point[v],v,min); key[v]=0; for(j=0;j<n;j++) if(g.edges[v][j]<key[j]) { point[j]=v