佛山科学技术学院

.@;

佛山科学技术学院

摘要：⑨广度优先搜索由邻接矩阵函数voidbfsAdjoin()⑩求出用普里姆算法表示的图的最小生成树函数Prim()⑾求出用克鲁斯卡尔算法表示的图的最小生成树函数Kruskal()...关键词：矩阵,算法类别：专题技术来源：牛档搜索（Niudown.COM）

本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！佛山科学技术学院实验报告实验名称典型数据结构算法实验项目图的最小生成树专业班级08教育技术学（1）姓名杨李纳学号2008914122指导教师容汝佳成绩日期2010.1.6一、实验目的1．熟悉图的邻接矩阵、邻接表表示。2．理解利用普里姆算法从顶点v。出发求出用邻接矩阵GA表示的图的最小生成树.3.理解利用克鲁斯卡尔方法求边集数组GE所示图的最小生成树二、实验内容本实验内容的主要基本操作包括图的邻接矩阵、邻接表表示以及图的邻接矩阵、邻接表的利用克鲁斯卡尔方法求边集数组GE所示图的最小生成树利用普里姆算法从顶点v。出发求出用邻接矩阵GA表示的图的最小生成树。三、实验步骤1．需求分析输入的形式：这个实验主要是根据运行界面提示，在键盘上输入相应的数据：输入待处理图的顶点数，输入无向带权图的每条边的起点和终点序号及权值。eq\o\ac(○,2)输出的形式：数据是以图的边集形式输出的，把输入的数据分别把利用普里姆算法和利用克鲁卡尔方法所求出的最小生成树相应地输出来。③程序所能达到的功能：这里在菜单控制下：实现数据的初始化、建立无向带权图的邻接矩阵、输出正确的结果。④测试数据：实验结果详见。2．概要设计1)基本操作：

voidIntiGMatrix(adjmatrix&GA,intn)操作结果：初始化图的邻接矩阵.

voidCreateMatrix(adjmatrixGA,intn,intk1,intk2);

初始条件：邻接矩阵已存在

操作结果：建立图的邻接矩阵voidInitGEdge(edgeset&GE,inte)操作结果:建立图的边集数组voidChangeEdgeSet(adjmatrixGA,edgesetGE,intn,inte)初始条件：边集数组已存在

操作结果：根据图的邻接矩阵生成图的边集数组voidIntiGAdjoin(adjlist&GL,intn)

初始条件：邻接表已存在

操作结果：初始邻接表voidCreateAdjoin(adjlist&GL,intn,intk1,intk2)初始条件：邻接表已存在

操作结果：建立邻接表voidSortEdgeSet(edgesetGE,inte)初始条件：邻接表已存在

操作结果：按升序排列图的边集数组voidPrim(adjmatrixGA,edgesetCT,intn)初始条件：邻接矩阵已存在

操作结果：求出用邻接矩阵GA表示的图的最小生成树voidKruskal(edgesetGE,edgesetC,intn)初始条件：边集数组已存在

操作结果：求边集数组GE所示图的最小生成树2）本程序包含8个函数：

①主函数main()

②初始化图的邻接矩阵函数voidIntiGMatrix③建立图的邻接矩阵表函数oidCreateMatrix()

④建立图的边集数组函数InitGEdge()⑤根据图的邻接矩阵生成图的边集数组函数ChangeEdgeSet()⑥初始邻接表函数voidIntiGAdjoin(）⑦建立邻接表函数voidCreateAdjoin()

⑧按升序排列图的边集数组函数voidSortEdgeSet()⑨广度优先搜索由邻接矩阵函数voidbfsAdjoin()⑩求出用普里姆算法表示的图的最小生成树函数Prim()⑾求出用克鲁斯卡尔算法表示的图的最小生成树函数Kruskal()各函数间关系如下：

3．详细设计实现概要设计中定义的所有的数据类型，对每个操作给出算法代码。对主程序和其他模块也都需要写出算法的C++代码。

1)包含文件说明部分:

#include<iostream.h>#include<stdlib.h>constintMaxValue=10000;2)元素类型和结构类型说明部分:

//定义邻接矩阵类型typedefint**adjmatrix;//定义邻接表中的边结点类型structedgenode{ intadjvex;//邻接点域 intweight;//权值域 edgenode*next;//指向下一个边结点的链域};//定义邻接表类型typedefedgenode**adjlist;//定义边集数组中的元素类型structedge{ intfromvex;//起点域 intendvex;//终点域 intweight;//权域};//定义边集数组的类型typedefedge*edgeset;3)基本操作的实现voidCheck(intn,int&i,int&j);voidInitGEdge(edgeset&GE,inte){ GE=newedge[e]; for(inti=0;i<e;i++) GE[i].weight=0;}voidOutputEdgeSet(edgesetGE,inte){ cout<<'{'; for(inti=0;i<=e-2;i++) { cout<<'('<<GE[i].fromvex<<','<<GE[i].endvex<<')'; cout<<GE[i].weight<<","; } if(e>0) { cout<<'('<<GE[e-1].fromvex<<','<<GE[e-1].endvex<<')'; cout<<GE[e-1].weight<<''; } cout<<'}'<<endl;}voidInitGAdjoin(adjlist&GL,intn){ GL=newedgenode*[n]; for(inti=0;i<n;i++) GL[i]=NULL;}voidDeleteAdjoin(adjlistGL,intn){ inti; edgenode*p; for(i=0;i<n;i++) p=GL[i]; while(p!=NULL) { GL[i]=p->next;deletep;p=GL[i]; } delete[]GL;}voidInitGMatrix(adjmatrix&GA,intn){ GA=newint*[n]; inti,j; for(i=0;i<n;i++) GA[i]=newint[n]; for(i=0;i<n;i++) for(j=0;j<n;j++)if(i==j)GA[i][j]=0; elseGA[i][j]=MaxValue;}voidCreateMatrix(adjmatrixGA,intn,int&e){ inti,j,k=0,w; cout<<"依次输入无向带权图的每条边的起点和终点序号及权值!"<<endl; cout<<"直到输入权植为0的边为止"<<endl; do { cin>>i>>j>>w; Check(n,i,j); if(w==0)break; GA[i][j]=GA[j][i]=w; k++; } while(1); e=k;}voidCheck(intn,int&i,int&j){ while(1) { if(i<0||i>=n||j<0||j>=n) cout<<"输入有误,请重输!"; elsereturn; cin>>i>>j; }}voidgraphChange(adjmatrixGA,adjlistGL,intn){ inti,j; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(GA[i][j]!=0&&GA[i][j]!=MaxValue) { edgenode*p=newedgenode; p->adjvex=j; p->weight=GA[i][j]; p->next=GL[i]; GL[i]=p; } } }}voidChangeEdgeSet(adjmatrixGA,edgesetGE,intn,inte){ inti,j,k=0; for(i=0;i<n;i++) for(j=i+1;j<n;j++) if(GA[i][j]!=0&&GA[i][j]!=MaxValue) { if(k==e) { cout<<"数组GE下标越界!"<<endl; exit(1); } GE[k].fromvex=i; GE[k].endvex=j; GE[k].weight=GA[i][j]; k++; }}voidSortEdgeSet(edgesetGE,inte){ inti,j; edgex; for(i=1;i<=e-1;i++) { x=GE[i]; for(j=i-1;j>=0;j--) if(x.weight<GE[j].weight) GE[j+1]=GE[j]; elsebreak; GE[j+1]=x; }}voidPrim(adjmatrixGA,edgesetCT,intn){ inti,j,k,min,t,m,w; for(i=0;i<n-1;i++) { CT[i].fromvex=0; CT[i].endvex=i+1; CT[i].weight=GA[0][i+1]; } for(k=1;k<n;k++) { min=MaxValue; m=k-1; for(j=k-1;j<n-1;j++) if(CT[j].weight<min) { min=CT[j].weight; m=j; } edgetemp=CT[k-1]; CT[k-1]=CT[m]; CT[m]=temp; j=CT[k-1].endvex; for(i=k;i<n-1;i++) { t=CT[i].endvex; w=GA[j][t]; if(w<CT[i].weight) { CT[i].weight=w; CT[i].fromvex=j; } } }}voidKruskal(edgesetGE,edgesetC,intn){ inti; edgenode*p; adjlists; InitGAdjoin(s,n); for(i=0;i<n;i++) { p=newedgenode; p->adjvex=i;p->next=NULL; s[i]=p; } intk=1; intd=0; intm1,m2; while(k<n) { for(i=0;i<n;i++) { p=s[i]; while(p!=NULL) { if(p->adjvex==GE[d].fromvex)m1=i; if(p->adjvex==GE[d].endvex)m2=i; p=p->next; } } if(m1!=m2) { C[k-1]=GE[d]; k++; p=s[m1]; while(p->next!=NULL) p=p->next; p->next=s[m2]; s[m2]=NULL; } d++; }} （四）、主函数的实现voidmain(){ intn,EdgeNum; cout<<"输入待处理图的顶点数:"; cin>>n;//定义一个邻接矩阵ga并初始化 adjmatrixga; InitGMatrix(ga,n);//根据键盘输入建立一个邻接矩阵gaCreateMatrix(ga,n,EdgeNum); //定义一个边集数组ge并初始化edgesetge; InitGEdge(ge,EdgeNum); //根据图的邻接矩阵ga得到图的边集数组geChangeEdgeSet(ga,ge,n,EdgeNum); //利用普里姆算法求图ga的最小生成树edgesetct; InitGEdge(ct,n); Prim(ga,ct,n); //输出ct中保存的最小生成树中的每条边OutputEdgeSet(ct,n-1); //利用克鲁斯卡尔方法求ge让所示图的最小生成树SortEdgeSet(ge,EdgeNum); Kruskal(ge,ct,n)