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

数据结构实验报告1 实验要求（1）实验目的通过选择下面5个题目之一进行实现，掌握如下内容： 掌握图基本操作的实现方法 了解最小生成树的思想和相关概念 了解最短路径的思想和相关概念 学习使用图解决实际问题的能力(2)实验内容根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图 5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小生成树7、求指定顶点到其他各顶点的最短路径8、其他：比如连通性判断等自定义操作编写测试main()函数测试图的正确性2. 程序分析2.1 存储结构 图：(1) 带权值的无向图V0 9 6 V1 2 V2 (2) 带权值的有向图 V0 6 3 9 4 V1 2 V22.2 关键算法分析（1）深度优先遍历int visitedMAXSIZE=false;templatevoid MGraph:DFS(int v)coutvertexv;visitedv=true;for(int j=0;jvNum;j+)if(arcvj=1&!visitedj)DFS(j);时间复杂度：O(n)（2）广度优先遍历int queueMAXSIZE;int f=0,r=0;coutvertexv;visitv=true;queue+r=v;while(f!=r)v=queue+f;for(int j=0;jvNum;j+)if(arcvj=1&!visitj) coutvertexj;visitj=true;queue+r=j;时间复杂度：O（n）（3）普利姆算法int adjvexMAXSIZE;int lowcostMAXSIZE;int MAX=10000;templateint mininum(MGraph G,int a)int min=MAX;int k=0;for(int i=0;iG.vNum;i+)if(ai!=0&aimin)/寻找U-V-U中边权值最小的顶点min=ai;k=i;return k;templatevoid MGraph: Prim(MGraph G) for(int i=0;iG.vNum;i+) adjvexi=0; lowcosti=G.arcs0i; lowcost0=0;/初始化U=vo for(int i=1;iG.vNum;i+) int k=mininum(G,lowcost);/求下一个边权值最小的邻接点 coutVadjvexkVkendl; lowcostk=0; for(int j=0;jG.vNum;j+) if(lowcostj!=0&G.arcskjlowcostj) lowcostj=G.arcskj; adjvexj=k; 时间复杂度：O(n)（4）克鲁斯卡尔算法templatevoid GenSortEdge(MGraph G,VEdge E)/获取EdgeListint k=0,i,j;for(i=0;iG.vNum;i+)/边赋值for(j=i;jG.vNum;j+)if(G.arcsij!=MAX)Ek.fromV=i;Ek.endV=j;Ek.weight=G.arcsij;k+;for(i=0;iG.arcNum-1;i+)for(j=i+1;jEj.weight)VEdge t=Ei;Ei=Ej;Ej=t;const int MAX_VERTEXT=20;templatevoid MGraph: Kruskal(VEdge E,int n,int e)int vsetMAX_VERTEXT;for(int i=0;in;i+) vseti=i;/初始化vsetint k=0,j=0;while(kn-1)int m=Ej.fromV,n=Ej.endV;int sn1=vsetm;/m所属的集合int sn2=vsetn;/n所属的集合if(sn1!=sn2)coutVmVnendl;k+;for(int i=0;in;i+)if(vseti=sn2)/集合编号为sn2的全部改为sn1vseti=sn1;时间复杂度：O(n)（5）求最短路径，连通性判断int distMAXSIZEMAXSIZE;int pathMAXSIZEMAXSIZE;templatevoid Floyd(MGraph G)for(int i=0;iG.vNum;i+) /寻找最短路径for(int j=0;jG.vNum;j+)distij=G.arcsij;if(distij!=MAX_VALUE) pathij=i;else pathij=-1;for(int k=0;kG.vNum;k+)for(int i=0;iG.vNum;i+)for(int j=0;jG.vNum;j+)if(distik+distkjdistij)/更新迭代数组Diskdistij=distik+distkj;pathij=k;cout任意两点间的最短路径长度(以矩阵表示）：endl;int l=1;for(int i=0;iG.arcNum;i+)for(int j=0;jG.arcNum;j+)coutdistijG.arcNum) coutendl;l=1;时间复杂度：O(n)3. 程序运行结果 （1）流程图：初始化带权值的无向图深度优先遍历，广度优先遍历用普利姆算法求最小生成树用克鲁斯卡尔算法求最小生成树初始化带权值的有向图用Floyd算法求任意两点间最短路径，并判断连通性删除图（2）本程序所用的图 带权值的无向图V0 9 6 V1 2 V2 带权值的有向图 V0 6 3 9 4 V1 2 V2（3）程序结果4. 总结（1）遇到的问题：私有数据访问权的问题，在编程时应该注意（2）心得体会：通过这次实验，我掌握了图基本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念等等。（3）改进：可以适当对某些步骤进行合并或省略，使程序更加简洁。源代码：#includeusing namespace std;const int MAXSIZE=20;const int MAX_EDGE=20;const int MAX_VALUE=1000;struct VEdgeint fromV;/起始顶点int endV;/终止顶点int weight;/边的权值;VEdge EdgeListMAX_EDGE;template class MGraphpublic:MGraph(T a,int n,int e);MGraph(T a,int n,int e,int h);void DFS(int v);void BFS(int v);void Prim(MGraph G);void Kruskal(VEdge E,int n,int e);int vNum,arcNum;int arcsMAXSIZEMAXSIZE;/用于储存权值的数组int arcMAXSIZEMAXSIZE;private:T vertexMAXSIZE;template /构造带权值的有向图MGraph:MGraph(T a,int n,int e,int h)int i,j,k,l;vNum=n;arcNum=e;for(k=0;kn;k+) vertexk=ak;for(k=0;kn;k+)for(j=0;jn;j+) arckj=0;for(int i=0;iMAXSIZE;i+)for(int j=0;jMAXSIZE;j+)arcsij=MAX_VALUE; cout请输入连通的两顶点下标(弧头-弧尾）及弧的权值(1000)：endl;for(int i=0;iMAXSIZE;i+)arcsii=0;for(k=0;kijl;arcsij=l; arcij=1; template /带权值的无向图MGraph:MGraph(T a,int n,int e)int i,j,k,l;vNum=n;arcNum=e;for(k=0;kn;k+) vertexk=ak;for(k=0;kn;k+)for(j=0;jn;j+) arckj=0; cout请输入连通的两顶点下标及边的权值(1000)：endl;for(k=0;kijl;arcsij=l; arcsji=arcsij; arcij=1;arcji=arcij; /深度广度遍历int visitedMAXSIZE=false;templatevoid MGraph:DFS(int v)coutvertexv;visitedv=true;for(int j=0;jvNum;j+)if(arcvj=1&!visitedj)DFS(j);int visitMAXSIZE=false;templatevoid MGraph:BFS(int v)int queueMAXSIZE;int f=0,r=0;coutvertexv;visitv=true;queue+r=v;while(f!=r)v=queue+f;for(int j=0;jvNum;j+)if(arcvj=1&!visitj) coutvertexj;visitj=true;queue+r=j;/普利姆算法int adjvexMAXSIZE;int lowcostMAXSIZE;int MAX=10000;templateint mininum(MGraph G,int a)int min=MAX;int k=0;for(int i=0;iG.vNum;i+)if(ai!=0&aimin)/寻找U-V-U中边权值最小的顶点min=ai;k=i;return k;templatevoid MGraph: Prim(MGraph G) for(int i=0;iG.vNum;i+) adjvexi=0; lowcosti=G.arcs0i; lowcost0=0;/初始化U=vo for(int i=1;iG.vNum;i+) int k=mininum(G,lowcost);/求下一个边权值最小的邻接点 coutVadjvexkVkendl; lowcostk=0; for(int j=0;jG.vNum;j+) if(lowcostj!=0&G.arcskjlowcostj) lowcostj=G.arcskj; adjvexj=k; /克鲁斯卡尔算法templatevoid GenSortEdge(MGraph G,VEdge E)/获取EdgeListint k=0,i,j;for(i=0;iG.vNum;i+)/边赋值for(j=i;jG.vNum;j+)if(G.arcsij!=MAX)Ek.fromV=i;Ek.endV=j;Ek.weight=G.arcsij;k+;for(i=0;iG.arcNum-1;i+)for(j=i+1;jEj.weight)VEdge t=Ei;Ei=Ej;Ej=t;const int MAX_VERTEXT=20;templatevoid MGraph: Kruskal(VEdge E,int n,int e)int vsetMAX_VERTEXT;for(int i=0;in;i+) vseti=i;/初始化vsetint k=0,j=0;while(kn-1)int m=Ej.fromV,n=Ej.endV;int sn1=vsetm;/m所属的集合int sn2=vsetn;/n所属的集合if(sn1!=sn2)coutVmVnendl;k+;for(int i=0;in;i+)if(vseti=sn2)/集合编号为sn2的全部改为sn1vseti=sn1;j+;/求最短路径/连通性判断int distMAXSIZEMAXSIZE;int pathMAXSIZEMAXSIZE;templatevoid Floyd(MGraph G)for(int i=0;iG.vNum;i+) /寻找最短路径for(int j=0;jG.vNum;j+)distij=G.arcsij;if(distij!=MAX_VALUE) pathij=i;else pathij=-1;for(int k=0;kG.vNum;k+)for(int i=0;iG.vNum;i+)for(int j=0;jG.vNum;j+)if(distik+distkjdistij)/更新迭代数组Diskdistij=distik+distkj;pathij=k;cout任意两点间的最短路径(以矩阵表示）：endl;int l=1;for(int i=0;iG.arcNum;i+)for(int j=0;jG.arcNum;j+)coutdistijG.arcNum) coutendl;l=1;void main()int v,e;cout请输入顶点数(21)和边数(ve;if(v20|v0|e20)cout输入错误！endl;char ch20=a,b,c,d,e,f,g,h,i,j,k,l,