基于QT实现的图的遍历演示

Smilelove

发布日期: 2018-10-31 11:48:00 浏览量: 897
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

1 问题分析和任务定义

1.1 问题描述

很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序,演示在连通的无向图上访问全部结点的操作。

1.2 基本要求

以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。

1.3 测试数据

任选国内城市,起点为合肥,暂时忽略里程。

1.4 问题分析及任务定义

此程序需要完成以下操作:使用文件读取数据,以邻接多重表为存储结构,构成一个连通的图。用户输入一个起始点,从起始点开始对图分别进行深度优先和广度优先遍历。分别输出每种遍历下的结点访问序列和相应的生产树的边集。

程序的执行流程如下图所示。

1.5 实现本程序需要解决的问题

  • 如何利用从文件读取的数据构成无向图

  • 如何实现从用户指定的点开始遍历

  • 遍历完后如何输出遍历过得点的序列和边集

  • 如何利用图形化动态的演示遍历过程

  • 如何提高用户体验

本程序的难点在于如何创建邻接多重表,和如何遍历所有城市。

设图的结点20-30个,每个结点用一个编号表示(如果一个图有n个结点,则它们的编号分别为1,2,…,n)。通过输入图的全部边(存于数据文件中,从文件读写)输入一个图,每个边为一个数对,可以对边的输入顺序作出某种限制。注意,生成树的边是有向边,端点顺序不能颠倒。

2 数据结构的选择和概要设计

城市与城市之间是没有方向的,构成的无向图采用邻接多重表来实现,主要表示无向图的的各个边和结点,并通过对邻接多重表的操作实现对无向图的深度优先和广度优先遍历。
创建AMLGraph类,其包含的属性和方法如下图所示。

其中adjMulList是顶点数组指针,所用的顶点结点以顺序方式存储在一维数组中;vexnum和edgenum是无向图的结点个数和边个数;cityMap类是用来存储所有从文件中读取的城市名和坐标信息的类,points、dfs_str、bfs_str是用来存储遍历的城市的坐标和名称的变量。

GreatAMLGraph函数用来构建邻接多重表,LocationVex函数通过城市名找到该城市在表结点的位置。AMLGraph、~AMLGraph函数分别是类的构造函数和析构函数,BFS_Traverse、DFS_Traverse分别是广度优先和深度优先遍历的函数。

VexNode结构体是点结点(城市结点),name是城市的名称,firstEdge是EdgeNode类型的指针,指向该顶点的第一条边的结点。

EdgeNode结构体是边结点,isVisited为标志域,用来标记该条边是否已被访问过;ivex为顶点域,指示依附于这条边的一个顶点的位置(序号);jvex指示另一个顶点的位置;ilink为链域,指向依附于第一条边的结点。

3 详细设计和编码

3.1 邻接多重表的建立

从文件中读取所有城市名、坐标和线路信息。利用头插法建立邻接多重表。

  1. for (int i = 0; i < edgenum; ++i)
  2. {
  3. EdgeNode * e = new EdgeNode;
  4. e->isVisited = false;
  5. string v1, v2;
  6. inFile >> v1 >> v2;
  7. int a = LocationVex(v1);
  8. int b = LocationVex(v2);
  9. e->ivex = a;
  10. e->jvex = b;
  11. e->ilink = adjMulList[a].firstEdge;
  12. e->jlink = adjMulList[b].firstEdge;
  13. adjMulList[a].firstEdge = e;
  14. adjMulList[b].firstEdge = e;
  15. }

3.2 深度优先遍历

先调用DFS_Traverse函数,初始化visited[i]数组,再调用DFS(i),其中i为用户指定城市的索引。在DFS函数中,先访问表结点中第i个点,在判断该顶点的另一端是否被访问,如果没有访问,就在调用DFS(i->jvex),形成递归,直到访问到该顶点的另一端被访问过后,在访问与i相连的其它边,当与i相连的所有边都被访问完时,结束循环。

  1. while (e)
  2. {
  3. if (e->ivex == i)
  4. {
  5. if (!visited[e->jvex])
  6. DFS(e->jvex);
  7. e = e->ilink;
  8. }
  9. else
  10. {
  11. if (!visited[e->ivex])
  12. DFS(e->ivex);
  13. e = e->jlink;
  14. }
  15. }

e为EdgeNode类型的指针变量。时间复杂度为O(n+edgeNum)。

3.3 广度优先遍历

先调用BFS_Traverse函数,初始化visited[i]数组,再调用BFS(i),其中i为用户指定城市的索引。BFS函数中,先访问表结点中第i个点,并将该点放入队列q中,在循环中不断取出队列的第一个元素,直到队列为空时,所以点遍历完成,结束该循环。取出队列第一个元素后,再判断该顶点的另一端是否被访问,如果没有访问,就遍历该点,并将该点放入队列,当队列第一个元素的所有相连的点都被访问过后,循环结束,再从队列中取出第一个元素,进行循环遍历。

  1. while (!q.empty())
  2. {
  3. p = q.front();
  4. q.pop();
  5. EdgeNode * e = adjMulList[p].firstEdge;
  6. while(e)
  7. {
  8. if (e->ivex == p)
  9. {
  10. if (!visited[e->jvex])
  11. {
  12. visited[e->jvex] = 1;
  13. //std::cout << adjMulList[e->jvex].name + " ";
  14. bfs_str.append(adjMulList[e->jvex].name.substr(0, 2) + "->");
  15. q.push(e->jvex);
  16. }
  17. e = e->ilink;
  18. }
  19. else if (e->jvex == p)
  20. {
  21. if (!visited[e->ivex])
  22. {
  23. visited[e->ivex] = 1;
  24. bfs_str.append(adjMulList[e->ivex].name.substr(0, 2) + "->");
  25. q.push(e->ivex);
  26. }
  27. e = e->jlink;
  28. }
  29. }
  30. }

分析上面算法,每个顶点至多进一次队列,遍历过程实质上仍是寻找每个顶点的邻接点的过程,因此时间复杂度和深度优先搜素一样。

4 上机调试过程

调试过程中,一方面是解决产生的bug,另一个面是调整文件中的数据,保证数据的合理性。

点的名称及坐标

无向图的边

5 测试结果及其分析

程序运行界面

遍历演示

本程序以图形化的形式演示,用户能够任意指定起始点开始遍历,遍历的结果也清晰可见。其中显示了两种遍历的城市编号的序列和遍历的边集。

6 用户使用说明

本程序是在windows7下的Qt creator5.4.1环境下编写的,因为Qt本身就是跨平台图形界面软件,所以本程序支持跨平台运行,支持的平台包括Windows、Mac OS、Linux等桌面操作系统。

执行本程序后,窗口上回现实所有城市的名称、编号和路线,输入框中默认填写的合肥的编号,该输入框支持模糊查询,可以输入城市名称、城市编号或编号加名称。点击按钮“演示”后,会以文本形式显示遍历城市的序列,以图形化的方式,显示遍历的城市之间的连线。并且可以反复搜索遍历,具有良好的用户体验。在该可执行文件目录下的map.txt是本程序的所依赖的数据来源,文件中的数据可供用户或开发者调整修改。

参考文献

[1] 王昆仑, 李红. 数据结构与算法. 北京: 中国铁道出版社, 2006年5月

[2] Kay_Sprint. 邻接多重表存储无向图以及有关操作[EB/OL]. http://www.2cto.com/database/201111/110964.html, 2011-11-13/2017-2-16

上传的附件 cloud_download 基于QT实现的图的遍历演示.7z ( 459.99kb, 29次下载 )
error_outline 下载需要9点积分

发送私信

即使是不成熟的尝试,也胜于胎死腹中的策略

7
文章数
9
评论数
最近文章
eject