北邮数据结构第三次实验图实验报告.doc

发布时间：2022-06-15 发布人：admin 分类：说明书资料大小：26.24M 资料格式：doc 举报版权申诉

6859fcde-bf53-43e5-8a17-dc738d6a5447.doc.pdf-第1页.png

第1页 / 共16页

6859fcde-bf53-43e5-8a17-dc738d6a5447.doc.pdf-第2页.png

第2页 / 共16页

6859fcde-bf53-43e5-8a17-dc738d6a5447.doc.pdf-第3页.png

第3页 / 共16页

6859fcde-bf53-43e5-8a17-dc738d6a5447.doc.pdf-第4页.png

第4页 / 共16页

6859fcde-bf53-43e5-8a17-dc738d6a5447.doc.pdf-第5页.png

第5页 / 共16页

6859fcde-bf53-43e5-8a17-dc738d6a5447.doc.pdf-第6页.png

第6页 / 共16页

6859fcde-bf53-43e5-8a17-dc738d6a5447.doc.pdf-第7页.png

第7页 / 共16页

6859fcde-bf53-43e5-8a17-dc738d6a5447.doc.pdf-第8页.png

第8页 / 共16页

文本预览

北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验三——图学生姓名：班级：班内序号：学日号：期： 2017 年 12 月 23 日 1．实验要求根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能： 1、图的建立 2、图的销毁 3、深度优先遍历图 4、广度优先遍历图 5、使用普里姆算法生成最小生成树 6、使用克鲁斯卡尔算法生成最小生成树 7、求指定顶点到其他各顶点的最短路径编写测试 main()函数测试图的正确性思考问题（选作）： 1、若测试数据量较大，如何使得栈不溢出？使用非递归方式编写新的深度优先遍历函数。提示：可以使用 STL 中的 stack 来辅助实现。 2、最短路径 D 算法，是否可以优化？请写出优化的思路并计算时间复杂度，同时实现一个新的优化的最短路径算法。 2. 程序分析 2.1 存储结构第 1页

北京邮电大学信息与通信工程学院邻接矩阵：可以使用二维数组表示顶点之间相邻关系。用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还要用一个顺序表来存储顶点信息 2.2 关键算法分析 1:邻接矩阵的建立 a:初始化顶点：vertex[k] = a[k]; b:初始化边：arcs[k][j] = 0; c:输入边的权值：cin >> data; arcs[i][j] = data; d:矩阵对称：arcs[j][i] = arcs[i][j]; 时间复杂度：O(n2) 2:深度优先遍历 a:初始状态，结点均未被访问：bool visited[MAXSIZE]={false}; b:从结点 v 开始访问：visited[v]=true; c:连通图：for （int j=0;j

北京邮电大学信息与通信工程学院 3:广度优先遍历 a:初始状态，结点均未被访问：bool visited[MAXSIZE]={false}; b:从结点 v 开始访问：visited[v]=true; c:v 入队：quene[++r] = v; d:队头元素出队：v = quene[++f]; e:打印出队元素：cout << vertex[v]; f:新元素入队：if （arc[v][j]）！=0&&!visited[j]) 时间复杂度：O(n) 空间复杂度：O(n) quene[++r] = j; 第 3页

北京邮电大学信息与通信工程学院 4:普里姆算法 a:初始化辅助数组：adjvex[i] = 0; lowcost[i] = G.arcs[0][i]; b:通过函数，求辅助数组最小值：int k = mininum(G, lowcost); c:打印此条路径：cout << 'V' << adjvex[k] << "->V" << k << endl; e:判断新结点各边权值的条件：if (lowcost[j] != 0 && G.arcs[k][j] < lowcost[j]) f:满足条件则更新辅助数组：lowcost[j] = G.arcs[k][j]; adjvex[j] = k; 时间复杂度：O(n2) 第 4页

北京邮电大学信息与通信工程学院 5:克鲁斯卡尔算法 a:获取 EdgeList，并对其排序：A.GenSortEdge(A, Edgelist); b:判断两个顶点的连接边是否构成回路：if (sn1 != sn2) c:构成回路后打印路径：cout << 'V' << m << "->V" << l << endl; d:将集合编号 sn2 的更新为 sn1：if (vset[i] == sn2) vset[i] = sn1; 时间复杂度：O(n2) 第 5页

北京邮电大学信息与通信工程学院 6: Dijkstra 算法 a:初始化辅助数组：Disk[i] = G.arcs[v][i]; if (Disk[i] != MAXSIZE) P[i] = v; else P[i] = -1; b:寻找离 v0 最近的顶点：if ((v = FindMin(Disk, S, G.vNum)) == -1) 第 6页

北京邮电大学信息与通信工程学院 c:更新辅助数组：Disk[j] = G.arcs[v][j] + Disk[v]; P[j] = v; d:打印路径：Print(Disk, P, G.vNum); 时间复杂度：O(n2) 2.3 其他 3. 程序运行结果 1、测试主函数流程：开始循环输入边和权值输入遍历起点深度优先遍历广度优先遍历普里姆算法最小生成树克鲁斯卡尔算法最小生成树输入求最短路径的起点输出最短路径结束第 7页

北京邮电大学信息与通信工程学院 2、测试条件：设置五个顶点：char a[5] = { 'A','B','C','D','E' }，然后假设有 7 条边 int sides = 7。通过循环，分别输入每条边的两个顶点以及该边的权值，然后输入遍历的起始点下标，依次打印出深度优先遍历，广度优先遍历，普里姆最小生成树路径和克鲁斯卡尔最小生成树路径。最后，通过输入起始点，分别生成各点到起始点的最短路径。最后，结束程序。 3、测试结论： 4. 总结 1、调试时出现的问题及解决的方法：书上的代码有很多小问题，包括 if 条件语句的判定有些小问题，或者前后命名的不统一导致报错之类的。并且，书上的各个函数是没有写到类的 public 里面的，导致很多时候访问的时候回报错。改进后，将各个函数写进了 public 里面，然后对 if 条件语句的判定条件进行了一些修改，将命名进行了统一后，调试成功。 2、心得体会：图这一部分，是很难的一部分。尤其是难在对代码的理解上面。普里姆算法，克鲁斯卡尔算法以及最短路径的算法，每一个算法都包含了许多辅助数组或者一些其他的函数来帮助运算，理解起来不容易。不过认真完成本次实验后，发第 8页

分享到：

赞收藏

资料库

北邮数据结构第三次实验图实验报告.doc

相关推荐

后端

热门标签

最新资料