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

《北邮数据结构实验第二次实验图》由会员分享，可在线阅读，更多相关《北邮数据结构实验第二次实验图（8页珍藏版）》请在装配图网上搜索。

1、数据结构实验报告1.实验要求(1)实验目的通过选择下面5个题目之一进行实现，掌握如下内容：掌握图基本操作的实现方法了解最小生成树的思想和相关概念了解最短路径的思想和相关概念学习使用图解决实际问题的能力(2)实验内容根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小生成树7、求指定顶点到其他各顶点的最短路径8、其他：比如连通性判断等自定义操作编写测试main()函数测试图的正确性2.程序分析存储结构图：(1)带权值的无向图V096V1 2V2(2)带权

2、值的有向图V0V1 2V2关键算法分析(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(n2)(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&!vi

3、sitj)coutvertexj;visitj=true;queue+r=j; 时间复杂度：O (n2)(3)普利姆算法int adjvexMAXSIZE;int lowcostMAXSIZE;int MAX=10000;templateint mininum(MGraph G,int a口) int min=MAX;int k=0;for(int i=0;i;i+) if(ai!=0&aimin)romV=i;Ek.endV=j;Ek.weight=ij; k+;for(i=0;i;i+) for(j=i+1;jEj.weight) VEdge t=Ei;Ei=Ej； Ej=t； const

4、 int MAX_VERTEXT=20;template void MGraph: Kruskal(VEdge E,int n,int e) int vsetMAX_VERTEXT;for(int i=0;in;i+) vseti=i;romV,n=Ej.endV;int sn1=vsetm;程序运行结果(1)流程图：初始化带权值的无向图深度优先遍历，广度优先遍历!用普利姆算法求最小生成树I用克鲁斯卡尔算法求最小生成树初始化带权值的有向图用Floyd算法求任意两点间最短路径，并判断连通性删除图(2)本程序所用的图带权值的无向图V0 9V12V2带权值的有向图/ V0V1 2V2(3)程序结果4

5、.总结(1)遇到的问题：私有数据访问权的问题，在编程时应该注意(2)心得体会：通过这次实验，我掌握了图基本操作的实现方法，了解最小生成树的思想 和相关概念，了解最短路径的思想和相关概念等等。(3)改进：可以适当对某些步骤进行合并或省略，使程序更加简洁。源代码：#includeusing namespace std;const int MAXSIZE=20;const int MAX_EDGE=20;const int MAX_VALUE=1000;struct VEdgeint fromV;romV=i;Ek.endV=j;Ek.weight=ij;k+;for(i=0;i;i+)for(j=

6、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;romV,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 的全部改为 sn1vset

7、i=sn1;j+;/ 求最短路径/ 连通性判断int distMAXSIZEMAXSIZE;int pathMAXSIZEMAXSIZE;templatevoid Floyd(MGraph G)for(int i=0;i;i+)/ 寻找最短路径for(int j=0；j；j+)(distij=ij;if(distij!=MAX_VALUE) pathij=i;elsepathij=-1;for(int k=0;k;k+)for(int i=0;i;i+)for(int j=0;j;j+) if(distik+distkjdistij)/更新迭代数组 Disk叩(distij=distik+di

8、stkj;pathij=k;cout任意两点间的最短路径(以矩阵表示)：endl;int l=1;for(int i=0;i;i+)for(int j=0;j;j+)(coutdistij 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,T,m,n,o,p,q,r,s,t; MGraph A(ch,v,e);couts;cout深度优先遍历：endl;(s);coutendl;coutk;cout广度优先遍历：endl;(k);coutendl;cout普利姆算法求最小生成树：endl;(A);cout克鲁斯卡尔算法求最小生成树：endl;VEdge EdgeListMAX_EDGE;GenSortEdge(A,EdgeList);(EdgeList,v,e);/ 初始化带权值的有向图couth;MGraph B(ch,v,e,h);Floyd(B);