数据结构实验一图剖析

1、数据结构实验报告实验名称： 实验二图学生姓名： 佘晨阳班 级： 2014211117班内序号： 20学 号： 2014210491日 期： 2015年12月05日1实验要求根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小生成树7、求指定顶点到其他各顶点的最短路径8、其他：比如连通性判断等自定义操作编写测试main()函数测试图的正确性2. 程序分析 本实验要求掌握图基本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念，学

2、习使用图解决实际问题的能力。2.1 存储结构 存储结构：1.不带权值的无向图邻接矩阵 2.带权值的无向图邻接矩阵 3.带权值的有向图邻接矩阵 1不带权值的无向图邻接矩阵2带权值的无向图邻接矩阵.3.带权值的有向图邻接矩阵备注：1. 在使用打印元素、BFS、DFS 采用无权值的无向图邻接矩阵存储方式2. 在使用PRIM、KRUSKAL、3. 在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式2.2 关键算法分析一图的邻接矩阵构造函数：1.关键算法：template<class f>Graph<f>:Graph(f a, int n, int e) /带权值的图的构

3、造函数int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for (k = 0; k < n; k+) vertexk = ak; /初始化顶点for (k = 0; k<n; k+)for (i = 0; i < n; i+)arcki = -1;if (i = k) arcki = 0; /初始化权值的大小visitedk = 0;cout << endl;for (k = 0; k<e; k+) /初始化边cout << "请输入线性链接节点:"cin >> s1

4、 >> s2 >> height;arcconvert(s1)convert(s2) = height;arcconvert(s2)convert(s1) = arcconvert(s1)convert(s2); /采用无向图带权值的邻接矩阵cout << endl;cout << "所得邻接矩阵为：" << endl; for (k = 0; k<n; k+)for (i = 0; i < n; i+)if (arcki = -1)cout << "" <<

5、 " "else cout << arcki << " " /打印邻接矩阵的格式cout << endl;cout << endl2.算法的时间复杂度有构造可知，初始化时其时间复杂度：O(n2)二深度优先便利DFS:1.关键算法从某顶点v出发并访问访问v的第一个未访问的邻接点w， 访问w的第一个未访问的邻接点u， 若当前顶点的所有邻接点都被访问过，则回溯，从上一级顶点的下一个未访问过的顶点开始深度优先遍历直到所有和v路径相通的顶点都被访问到；2.代码图解：深度优先遍历示意图3.代码详解：template&l

6、t;class f>void Graph<f>:DFS(int v)cout << vertexv;visitedv = 1; for (int j = 0; j < vnum; j+) /连通图 if (visitedj = 0) && (arcvj >= 1) DFS(j); /当存在回路时，则连通深一层遍历 4.时间复杂度 时间复杂度：O(n2)空间复杂度：栈的深度O(n)辅助空间O(n)三广度遍历BFS1.关键算法访问顶点v依次访问v的所有未被访问的邻接点v1,v2,v3分别从v1,v2,v3出发依次访问它们未被访问的邻接点反复

7、 ，直到所有和v路径相通的顶点都被访问到；2.代码图解3.代码详解1.初始化队列Q 2.访问顶点v， visitedv=1 3. while(队列非空) 3.1 v=队头元素出队 3.2 访问队头元素的所有未访问的邻接点4.时间复杂度 时间复杂度：O(n2) 空间复杂度：辅助空间O(n)四.最小生成树普里姆算法1,关键思路一般情况下，假设n个顶点分成两个集合：U(包含已落在生成树上的结点)和V-U(尚未落在生成树上的顶点)，则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。主数据结构： 邻接矩阵辅助数据结构： int adjvexMAXSIZE; / U集中的顶点序号 int lowc

8、ostMAXSIZE; / Uà(V-U)的最小权值边2.代码图解 3;代码详解template<class f>void Graph<f>:Prim()for (int i = 0; i < vnum; i+) /辅助数组存储所有到的V0边adjvexi = 0; lowcosti = arc0i; lowcost0 = 0;for (int j = 1; j < vnum; j+) /循环n-1次int k = Mininum(lowcost); /求下一个顶点cout << vertexadjvexk << "

9、;->" << vertexk << endl; lowcostk = 0; /U=U+Vkfor (int j = 0; j < vnum; j+) /设置辅助数组 if (lowcostj != 0 && arckj < lowcostj)lowcostj = arckj;adjvexj = k;4,时间复杂度：时间复杂度O(n2)，适合稠密图五.最小生成树-克鲁斯卡尔算法1,关键思路先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为

10、止。2.代码图解： 3.代码详解template<class f>void Graph<f>:Kruskal() /最小生成树kruskal算法 cout<<"Krusal算法结果为："<<endl;int vsetMAXSIZE;for (int i = 0; i < vnum; i+) vseti = i; int k = 0, j = 0; while (k < vnum - 1)int m = vedgelistj.fromv, n = vedgelistj.endv;int sn1 = vsetm;int

11、 sn2 = vsetn; /两个顶点分属不同的集合if (sn1 != sn2)cout << vertexm << "->" << vertexn << endl;k+;for (int i = 0; i < vnum; i+)if (vseti = sn2)vseti = sn1; /集合sn2全部改成sn1j+;4.时间复杂度 时间复杂度O(nlogn)，适合稀疏图六最短路径Dijkstra算法1.关键代码 按路径长度递增的次序产生源点到其余各顶点的最短路径。 1)设置集合s存储已求得的最短路径的顶点， 2

12、)初始状态：s=源点v 3)叠代算法： 直接与v相连的最近顶点vi,加入s 从v经过vi可以到达的顶点中最短的，加入s 2.代码图解3.代码详解emplate<class f>void Graph<f>:ShotPath(f x) /关于最短路径的初始化int v=convert(x); for (int i = 0; i < vnum; i+) /初始化路径和点 si=0; diski = arcvi;if (diski != maxs) pathi = v; else pathi = -1;sv = 1; diskv = 0;pathv=-1;for (int

13、 i = 0; i < vnum; i+) /反复经过从该点到其他点的路径 if (v = FindMin() = -1) continue; sv = 1;for (int j = 0; j < vnum; j+)if (!sj && (diskj>arcvj + diskv)diskj = arcvj + diskv;pathj = v;Print(); /打印路径长度和遍历 4.时间复杂度时间复杂度为：n2七判断连通图算法template<class f>bool Graph<f>:judgegraph()DFS(convert(

14、vertex0);if(count=vnum) cout<<"该图为连通图！*输入成功！"<<endl; return false; else cout<<"该图不为连通图！*请重新输入"<<endl; return true; 时间复杂度：n23. 程序运行结果 1. 测试主函数流程：函数流程图：1. 输入图的连接边并打印构造下面所示图的邻接矩阵： 2.判断图连通是否成功3.BFS DFS PRIM算法的实现4.克鲁斯卡尔算法实现过程4. 有向图邻接矩阵的构建插入V0位置后打印距离并开始回溯总结1.调试时出现的问题及解决的方法 问题一：prim算法中 解决方法：调整循环条件，修正函数体注意有无Next的区别 问题二：BFS和DFS同时在一个类里作用时会输出错误 解决方案：每次BFS/DFS使用时都把visited数组初始化一遍 问题三：在最短路径，经常出现了停止输入的情况 解决方法：改return为continue，并修改打印算法2.心得体会 通过本次实验，基本熟练掌握了c+基本语句，尤其对图的结构及应用有了较深了解；调试代码时尽量做到完成一个代码段调试一次，可以最快检测出错误所在；类的封装和调用，类的共有成员和私有成员的设置。3.下一步的改进 第一，设置增加图节点和边的