图及Kruscal算法-数据结构实验报告(3)

电子科技大学信息与软件工程学院实验报告第1页电子科技大学实验报告课程名称：数据结构与算法学生姓名：陈*浩学号：*************点名序号：***指导教师：钱**实验地点：基础实验大楼实验时间：2015.05.292014-2015-2学期信息与软件工程学院电子科技大学信息与软件工程学院实验报告第2页实验报告(三)学生姓名：陈*浩学号：************指导教师：钱**实验地点：科研教学楼A508实验时间：2015.05.29一、实验室名称：软件实验室二、实验项目名称：数据结构与算法—图三、实验学时：4四、实验原理：Kruskal算法是一种按照图中边的权值递增的顺序构造最小生成树的方法。其基本思想是：设无向连通网为G＝（V，E），令G的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T由图G中的n个顶点构成，顶点之间没有一条边，这样T中各顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。如教材153页的图4.21(a)所示，按照Kruskal方法构造最小生成树的过程如图4.21所示。在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n个结点的生成树，有n－1条边，故反复上述过程，直到选取了n－1条边为止，就构成了一棵最小生成树。五、实验目的：本实验通过实现最小生成树的算法，使学生理解图的数据结构存储表示，并能理解最小生成树Kruskal算法。通过练习，加强对算法的理解，提高编程能力。六、实验内容：（1）假定每对顶点表示图的一条边，每条边对应一个权值；（2）输入每条边的顶点和权值；电子科技大学信息与软件工程学院实验报告第3页（3）输入每条边后，计算出最小生成树；（4）打印最小生成树边的顶点及权值。七、实验器材（设备、元器件）：PC机一台，装有C/C++语言集成开发环境。八、数据结构及程序#includestdio.h#includestdlib.h#includestring.h#definemaxnode17#definemaxedgs120charFileAddress[100]=F:\\graph.txt;//全局通用文件地址typedefstruct{intvex;//顶点信息intgno;//顶点所在的连通分量编号}TVex,*TpVex;typedefstruct{intvhead,vtail;//边依附的两顶点intwght;//边的权值intflag;//0：未加入MST;1：已入选;-1：已删除}TEdge,*TpEdge;typedefstruct{TpVexVexList;//顶点数组TpEdgeEdgeList;//边数组intnvex,nedge;//顶点数量，边数量}TGraph,*TpGraph;intRead_File(charFileAdress[],TpGraphGraph);//读取文件并建立图intKruskal_Tree(TpGraphGraph);//构建最小生成树并输出边信息voidAss_Con_Comp(TpGraphGraph,intVex1,intVex2);//使一个连通分量内的所有顶点的分量值相同voidOutput_Graph(TpGraphGraph);//输出图的结构电子科技大学信息与软件工程学院实验报告第4页intmain(void){TGraphG;intk;charchoose='y';printf(--------图与Kruskal算法----------\n);while(choose=='y'){printf(请输入信息文件地址（例如：F:\\\\filename.txt）：\n);gets(FileAddress);//输入文件地址k=Read_File(FileAddress,&G);if(k==-1){printf(地址有误！请重新输入！\n);continue;}Kruskal_Tree(&G);printf(\n--------图与Kruskal算法----------\n\n);printf(重新开始？y/n:);choose=getchar();}return0;}//*************************************************************//****读取文本文件并建立图//*************************************************************intRead_File(charFileAdress[],TpGraphGraph){intnVex[maxnode]={0};//判断结点存在intnVexs=0+1;//结点个数intnEdges=0;//边的条数inti=0;TEdgeEdges[maxedgs];TVexVexs[maxnode];FILE*fp=NULL;fp=fopen(FileAddress,r);//打开文件电子科技大学信息与软件工程学院实验报告第5页if(!fp)return-1;elseprintf(打开文件成功!\n);if(nEdgesmaxedgs){//读取边信息while(fscanf(fp,%d\t%d\t%d\n,&Edges[nEdges].vtail,&Edges[nEdges].vhead,&Edges[nEdges].wght)!=EOF){Edges[nEdges].flag=0;//未加入MST的边nVex[Edges[nEdges].vtail]=1;nVex[Edges[nEdges].vhead]=1;nEdges++;//记录边的条数}}for(i=0;imaxnode;i++){//计算结点的个数if(nVex[i]){Vexs[i].vex=i;//结点i存在Vexs[i].gno=i;//不同的结点赋予不同的连通分量编号nVexs++;}}(*Graph).VexList=Vexs;(*Graph).EdgeList=Edges;(*Graph).nvex=nVexs;(*Graph).nedge=nEdges;printf(从文件读取到图如下：\n);Output_Graph(Graph);fclose(fp);return0;}//*************************************************************//****输出图的结构//*************************************************************voidOutput_Graph(TpGraphGraph){inti,j;电子科技大学信息与软件工程学院实验报告第6页printf(顶点--信息\n);for(i=1;iGraph-nvex;i++)printf(%4d--%-4d\n,i,Graph-VexList[i].vex);printf(\n边-尾-头-权\n);for(j=0;jGraph-nedge;j++)printf(%2d-%-2d-%2d-%-2d\n,j+1,Graph-EdgeList[j].vtail,Graph-EdgeList[j].vhead,Graph-EdgeList[j].wght);}//*************************************************************//****根据图采用Kruskal算法建立并输出最小生成树//*************************************************************intKruskal_Tree(TpGraphGraph){inti,j,k,s;intmin=10000;intEdges=1;TpEdgemin_wght_edge;//权值最小的边printf(\n最小生成树结构如下：\n);while(EdgesGraph-nvex-1){min=10000;for(i=0;iGraph-nedge;i++){if((minGraph-EdgeList[i].wght)&&(Graph-EdgeList[i].flag==0)){min=Graph-EdgeList[i].wght;//记录当前的最小权值min_wght_edge=&Graph-EdgeList[i];//选择的最小边}}if(Graph-VexList[min_wght_edge-vtail].gno==Graph-VexList[min_wght_edge-vhead].gno)//最小边上两个顶点的连通分量相同{min_wght_edge-flag=-1;//舍去这条边for(j=0;jGraph-nedge;j++)//舍去无向图中对应的另一条边if(Graph-EdgeList[j].vtail==min_wght_edge-vhead&&Graph-EdgeList[j].vhead==min_wght_edge-vtail){Graph-EdgeList[j].flag=-1;break;电子科技大学信息与软件工程学院实验报告第7页}}else{min_wght_edge-flag=1;//将这条边加入MSTfor(k=0;kGraph-nedge;k++)//加入无向图中对应的另一条边if((Graph-EdgeList[k].vtail==min_wght_edge-vhead)&&(Graph-EdgeList[k].vhead==min_wght_edge-vtail)){Graph-EdgeList[k].flag=1;break;}Ass_Con_Comp(Graph,min_wght_edge-vtail,min_wght_edge-vhead);//统一连通分量printf(第%d条边：%d,%d，权值为%d\n,Edges,min_wght_edge-vtail,min_wght_edge-vhead,min_wght_edge-wght);++Edges;}}return0;}//*************************************************************//****统一一个集合内所有顶点的连通分量//*************************************************************voidAss_Con_Comp(TpGraphGraph,intVex1,intVex2){inti;for(i=0;iGraph-nedge;i++){if((Graph-EdgeList[i].flag==1)&&(Graph-EdgeList[i].vtail==Vex1)&&(Graph-EdgeList[i].vhead!=Vex2))if(Graph-VexList[Graph-EdgeList[i].vhead].gno!=Graph-VexList[Vex1].gno)Ass_Con_Comp(Graph,Graph-EdgeList[i].vhead,Vex1);if((Graph-EdgeList[i].flag==1)&&(Graph-EdgeList[i].vhead==Vex1)&&(Graph-EdgeList[i].vtail!=Vex2