数据结构实验一图剖析Word下载.docx

1、 存储结构：1.不带权值的无向图邻接矩阵 2.带权值的无向图邻接矩阵 3.带权值的有向图邻接矩阵 1不带权值的无向图邻接矩阵2带权值的无向图邻接矩阵.3.带权值的有向图邻接矩阵备注：1. 在使用打印元素、BFS、DFS 采用无权值的无向图邻接矩阵存储方式2. 在使用PRIM、KRUSKAL、3. 在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式2.2 关键算法分析一图的邻接矩阵构造函数：1.关键算法：templateGraph:Graph（f a, int n, int e） /带权值的图的构造函数 int i, j, k, height; f s1, s2; vnum = n; a

2、rcnum = e; for （k = 0; k n; k+） vertexk = ak; /初始化顶点 kn; k+） for （i = 0; i i+） arcki = -1; if （i = k） arcki = 0; /初始化权值的大小 visitedk = 0; cout endl;e; k+） /初始化边 cout s1 s2 height; arcconvert（s1）convert（s2） = height; arcconvert（s2）convert（s1） = arcconvert（s1）convert（s2）; /采用无向图带权值的邻接矩阵所得邻接矩阵为： if （arc

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

4、 /当存在回路时，则连通深一层遍历 4.时间复杂度 时间复杂度：空间复杂度：栈的深度O（n）辅助空间O（n）三广度遍历BFS访问顶点v依次访问v的所有未被访问的邻接点v1,v2,v3分别从v1,v2,v3出发依次访问它们未被访问的邻接点反复 ，直到所有和v路径相通的顶点都被访问到；2.代码图解3.代码详解1.初始化队列Q 2.访问顶点v， visitedv=1 3. while（队列非空） 3.1 v=队头元素出队 3.2 访问队头元素的所有未访问的邻接点4.时间复杂度 时间复杂度： 空间复杂度：四.最小生成树普里姆算法1,关键思路一般情况下，假设n个顶点分成两个集合：U（包含已落在生成树上的

5、结点）和V-U（尚未落在生成树上的顶点），则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。主数据结构： 邻接矩阵辅助数据结构： int adjvexMAXSIZE; / U集中的顶点序号 int lowcostMAXSIZE; / U（V-U）的最小权值边3;代码详解Prim（） for （int i = 0; i+） /辅助数组存储所有到的V0边 adjvexi = 0; lowcosti = arc0i; lowcost0 = 0; for （int j = 1; j+） /循环n-1次 int k = Mininum（lowcost）; /求下一个顶点 vertexadjvex

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

7、E; i+） vseti = i; int k = 0, j = 0; while （k vnum - 1） int m = vedgelistj.fromv, n = vedgelistj.endv; int sn1 = vsetm; int sn2 = vsetn; /两个顶点分属不同的集合 if （sn1 != sn2） cout vertexm vertexn k+; for （int i = 0; if （vseti = sn2） vseti = sn1; /集合sn2全部改成sn1 j+; 时间复杂度O（nlogn），适合稀疏图六最短路径Dijkstra算法1.关键代码 按路径长度

8、递增的次序产生源点到其余各顶点的最短路径。 1）设置集合s存储已求得的最短路径的顶点， 2）初始状态：s=源点v 3）叠代算法： 直接与v相连的最近顶点vi,加入s 从v经过vi可以到达的顶点中最短的，加入semplatearcvj + diskv） diskj = arcvj + diskv; pathj = v; Print（）; /打印路径长度和遍历 时间复杂度为：n2七判断连通图算法bool Graphjudgegraph（） DFS（convert（vertex0）; if（count=vnum） 该图为连通图！*输入成功！ return false; else该图不为连通图！*请重

9、新输入 return true;3. 程序运行结果 1. 测试主函数流程：函数流程图：1. 输入图的连接边并打印构造下面所示图的邻接矩阵：2.判断图连通是否成功3.BFS DFS PRIM算法的实现4.克鲁斯卡尔算法实现过程4. 有向图邻接矩阵的构建插入V0位置后打印距离并开始回溯总结1.调试时出现的问题及解决的方法 问题一：prim算法中 解决方法：调整循环条件，修正函数体注意有无Next的区别 问题二：BFS和DFS同时在一个类里作用时会输出错误 解决方案：每次BFS/DFS使用时都把visited数组初始化一遍 问题三：在最短路径，经常出现了停止输入的情况改return为continue

10、，并修改打印算法2.心得体会 通过本次实验，基本熟练掌握了c+基本语句，尤其对图的结构及应用有了较深了解；调试代码时尽量做到完成一个代码段调试一次，可以最快检测出错误所在；类的封装和调用，类的共有成员和私有成员的设置。3.下一步的改进 第一，设置增加图节点和边的函数 第二，实现图形化输出图的路径的功能 第三，主函数设计简单，不要过于累赘4.程序中出现的亮点1） 利用dfs算法衍生生成判断是否为连通图的连通算法2） 采用graph类实现所有图的所有算法，所需的数据类型均在私有成员内，封装3） 利用convert函数采取象意输入，采用ABCD的节点输入方式而并非转化成01234再输入。4） BFS中采用c+标准库的。5） 打印邻接矩阵时，打印出非链接的符号和与自身路径的0距离6） 判断图为非连通图后，提示输入错误，重新输入图元素