北邮数据结构实验-第二次实验-图

数据结构实验报告1．实验要求（1）实验目的通过选择下面5个题目之一进行实现，掌握如下内容：掌握图基本操作的实现方法了解最小生成树的思想和相关概念了解最短路径的思想和相关概念学习使用图解决实际问题的能力(2)实验内容根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小生成树7、求指定顶点到其他各顶点的最短路径8、其他：比如连通性判断等自定义操作编写测试main()函数测试图的正确性2.程序分析2.1存储结构图：(1)带权值的无向图V096V12V2(2)带权值的有向图V06394V12V22.2关键算法分析（1）深度优先遍历intvisited[MAXSIZE]={false};templateclassTvoidMGraphT::DFS(intv){coutvertex[v];visited[v]=true;for(intj=0;jvNum;j++)if(arc[v][j]==1&&!visited[j])DFS(j);}时间复杂度：O(n²)（2）广度优先遍历intqueue[MAXSIZE];intf=0,r=0;coutvertex[v];visit[v]=true;queue[++r]=v;while(f!=r){v=queue[++f];for(intj=0;jvNum;j++){if(arc[v][j]==1&&!visit[j]){coutvertex[j];visit[j]=true;queue[++r]=j;}时间复杂度：O（n²）（3）普利姆算法intadjvex[MAXSIZE];intlowcost[MAXSIZE];intMAX=10000;templateclassTintmininum(MGraphTG,inta[]){intmin=MAX;intk=0;for(inti=0;iG.vNum;i++){if(a[i]!=0&&a[i]min)//寻找U-{V-U}中边权值最小的顶点{min=a[i];k=i;}}returnk;}templateclassTvoidMGraphT::Prim(MGraphG){for(inti=0;iG.vNum;i++){adjvex[i]=0;lowcost[i]=G.arcs[0][i];}lowcost[0]=0;//初始化U={vo}for(inti=1;iG.vNum;i++){intk=mininum(G,lowcost);//求下一个边权值最小的邻接点cout'V'adjvex[k]-Vkendl;lowcost[k]=0;for(intj=0;jG.vNum;j++){if(lowcost[j]!=0&&G.arcs[k][j]lowcost[j]){lowcost[j]=G.arcs[k][j];adjvex[j]=k;}}}}时间复杂度：O(n²)（4）克鲁斯卡尔算法templateclassTvoidGenSortEdge(MGraphTG,VEdgeE[])//获取EdgeList{intk=0,i,j;for(i=0;iG.vNum;i++)//边赋值for(j=i;jG.vNum;j++)if(G.arcs[i][j]!=MAX){E[k].fromV=i;E[k].endV=j;E[k].weight=G.arcs[i][j];k++;}for(i=0;iG.arcNum-1;i++){for(j=i+1;jG.arcNum;j++)if(E[i].weightE[j].weight){VEdget=E[i];E[i]=E[j];E[j]=t;}}}constintMAX_VERTEXT=20;templateclassTvoidMGraphT::Kruskal(VEdgeE[],intn,inte){intvset[MAX_VERTEXT];for(inti=0;in;i++)vset[i]=i;//初始化vsetintk=0,j=0;while(kn-1){intm=E[j].fromV,n=E[j].endV;intsn1=vset[m];//m所属的集合intsn2=vset[n];//n所属的集合if(sn1!=sn2){cout'V'm-Vnendl;k++;for(inti=0;in;i++){if(vset[i]==sn2)//集合编号为sn2的全部改为sn1vset[i]=sn1;时间复杂度：O(n²)（5）求最短路径，连通性判断intdist[MAXSIZE][MAXSIZE];intpath[MAXSIZE][MAXSIZE];templateclassTvoidFloyd(MGraphTG){for(inti=0;iG.vNum;i++)//寻找最短路径for(intj=0;jG.vNum;j++){dist[i][j]=G.arcs[i][j];if(dist[i][j]!=MAX_VALUE)path[i][j]=i;elsepath[i][j]=-1;}for(intk=0;kG.vNum;k++)for(inti=0;iG.vNum;i++)for(intj=0;jG.vNum;j++)if(dist[i][k]+dist[k][j]dist[i][j])//更新迭代数组Disk[][]{dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=k;}cout任意两点间的最短路径长度(以矩阵表示）：endl;intl=1;for(inti=0;iG.arcNum;i++)for(intj=0;jG.arcNum;j++){coutdist[i][j];l++;if(lG.arcNum){coutendl;l=1;}}}时间复杂度：O(n³)3.程序运行结果（1）流程图：初始化带权值的无向图深度优先遍历，广度优先遍历用普利姆算法求最小生成树用克鲁斯卡尔算法求最小生成树初始化带权值的有向图用Floyd算法求任意两点间最短路径，并判断连通性删除图（2）本程序所用的图带权值的无向图V096V12V2带权值的有向图V06394V12V2（3）程序结果4.总结（1）遇到的问题：私有数据访问权的问题，在编程时应该注意（2）心得体会：通过这次实验，我掌握了图基本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念等等。（3）改进：可以适当对某些步骤进行合并或省略，使程序更加简洁。源代码：#includeiostreamusingnamespacestd;constintMAXSIZE=20;constintMAX_EDGE=20;constintMAX_VALUE=1000;structVEdge{intfromV;//起始顶点intendV;//终止顶点intweight;//边的权值};VEdgeEdgeList[MAX_EDGE];templateclassTclassMGraph{public:MGraph(Ta[],intn,inte);MGraph(Ta[],intn,inte,inth);voidDFS(intv);voidBFS(intv);voidPrim(MGraphG);voidKruskal(VEdgeE[],intn,inte);intvNum,arcNum;intarcs[MAXSIZE][MAXSIZE];//用于储存权值的数组intarc[MAXSIZE][MAXSIZE];private:Tvertex[MAXSIZE];};templateclassT//构造带权值的有向图MGraphT::MGraph(Ta[],intn,inte,inth){inti,j,k,l;vNum=n;arcNum=e;for(k=0;kn;k++)vertex[k]=a[k];for(k=0;kn;k++)for(j=0;jn;j++)arc[k][j]=0;for(inti=0;iMAXSIZE;i++){for(intj=0;jMAXSIZE;j++){arcs[i][j]=MAX_VALUE;}}cout请输入连通的两顶点下标(弧头-弧尾）及弧的权值(1000)：endl;for(inti=0;iMAXSIZE;i++){arcs[i][i]=0;}for(k=0;kh;k++){cinijl;arcs[i][j]=l;arc[i][j]=1;}}templateclassT//带权值的无向图MGraphT::MGraph(Ta[],intn,inte){inti,j,k,l;vNum=n;arcNum=e;for(k=0;kn;k++)vertex[k]=a[k];for(k=0;kn;k++)for(j=0;jn;j++)arc[k][j]=0;cout请输入连通的两顶点下标及边的权值(1000)：endl;for(k=0;ke;k++){cinijl;arcs[i][j]=l;arcs[j][i]=arcs[i][j];arc[i][j]=1;arc[j][i]=arc[i][j];}}//深度广度遍历intvisited[MAXSIZE]={false};templateclassTvoidMGraphT::DFS(intv){coutvertex[v];visited[v]=true;for(intj=0;jvNum;j++)if(arc[v][j]==1&&!visited[j])DFS(j);}intvisit[MAXSIZE]={false};templateclassTvoidMGraphT::BFS(intv){intqueue[MAXSIZE];intf=0,r=0;coutvertex[v];visit[v]=true;queue[++r]=v;while(f!=r){v=queue[++f];for(intj=0;jvNum;j++){if(arc[v][j]==1&&!visit[j]){coutvertex[j];visit[j]=true;queue[++r]=j;}}}}//普利姆算法intadjvex[MAXSIZE];intlowcost[MAXSIZE];intMAX=10000;templateclassTintmininum(MGraphTG,inta[]){intmin=MAX;intk=0;for(inti=0;iG.vNum;i++){if(a[i]!=0&&a[i]min)//寻找U-{V-U}中边权值最小的顶点{min=a[i];k=i;}}returnk;}templateclassTvoidMGraphT::Prim(MGraphG){for(inti=0;iG.vNum;i++){adjvex[i]=0;lowcost[i]=G.arcs[0][i];}lowcost[0]=0;//初始化U={vo}for(inti=1;iG.vNum;i++){intk=mininum(G,lowcost);//求下一个边权值最小的邻接点cout'V'adjvex[k]-Vkendl;lowcost[k]=0;for(intj=0;jG.vNum;j++){if(lowcost[j]!=0&&G.arcs[k][j]lowcost[j]){lowcost[j]=G.arcs[k][j];adjvex[j]=k;}}}}//克鲁斯卡尔算法templateclassTvoidGenSortE