程彩凤+林德树

摘 要： 数据结构课程中图论算法抽象复杂，传统的板书或PPT演示算法程序语句的教学方法不利于学生理解和掌握。在Visual Studio 2013环境下，基于MFC平台研究并设计了一款数据结构课程关于图论算法动态智能演示的教学辅助软件。动态演示了包括图的深度优先遍历、广度优先遍历算法，求最小生成树的Prim算法和Kruskal算法，最短路径Dijkastra算法和Floyd算法的执行过程。软件界面简洁美观，操作简单友好，算法执行过程一目了然，图形界面与算法流程、算法数据信息同步显示。

关键词： 数据结构； 图论算法； 动态演示； MFC； CAI

中图分类号： TN915.5?34； TP39 文献标识码： A 文章编号： 1004?373X（2017）18?0040?03

Research on dynamic intelligent demonstration of graph?theoretical

algorithm in data structure

CHENG Caifeng1， LIN Deshu2

（1. College of engineering and technology， Yangtze University， Jingzhou 434020， China；

2. College of Computer Science， Yangtze University， Jingzhou 434023， China）

Abstract： The graph?theoretical algorithm in data structure course is complex. The teaching method of traditional blackboard?writing or algorithm program statements of PPT demonstration is not conducive to the students to understand and master. With the Visual Studio 2013， a teaching assistant software about the graph theory algorithms dynamic intelligent demonstration was designed on the basis of MFC platform. The dynamic intelligent demonstration includes the executing process of the depth?first traversal and the breadth?first traversal algorithm， Prim algorithm and Kruskal algorithm for deriving the minimum spanning tree， and the shortest path Dijkastra algorithm and Floyd algorithm. The software interface is concise and artistic， and its operation is simple and friendly. The executing process of the algorithm is clear at a glance. The graphical interface is synchronically displayed with algorithm flow and algorithm data information.

Keywords： data structure； graph?theoretical algorithm； dynamic demonstration； MFC； CAI

计算机辅助教学（CAI）是目前计算机应用领域的一个新内容，是一种新型的现代化教学手段，也是当前教学手段改革的主要趋势[1]。

数据结构课程中图问题始终渗透整个计算机科学，应用非常广泛。图论可以应用于电路网络分析、运筹学、计算机网络、信息论、控制论等各个领域[2]。而該课程涉及大量深奥、抽象的概念和算法，特别是图中经典算法的思想涉及到很多递归算法，其执行过程更为抽象难懂。目前在大多数高校对于算法内容的教学方式，主要以教师板书和PPT演示算法语句为主，没有将算法在实验中验证，这样的教学方式更增加了学生学习的难度。与这种传统的教学方法相比，算法动态智能演示解决了上述问题，它主要是利用可视化技术和多媒体工具，以生动直观的画面显示方式辅助数据结构课程的教学，能够提高教学效率，有利于培养学生动手实践的能力、学习和科研的能力[3]。

1 动态智能演示软件的总体设计

软件设计的目的是实现一个动态智能演示深度优先遍历、广度优先遍历、最小生成树和最短路径问题算法的教学辅助系统，从而帮助学生轻松直观地学习各种算法。因此简洁美观的界面、简单方便的操作及一目了然的执行过程是非常必要的。

1.1 软件体系结构

数据结构算法的可视化主要是对数据结构的图形再现，也就是在数据结构变动的同时，图形界面也要做出同步的变化，进而也就确定了两者之间的关系，非耦合但在变化逻辑上相关。考虑到工程量，采用迭代式开发，整体上就可以分为三层：实体层、算法功能层、图形绘制层。

在MFC窗体上进行绘制图形有两种方案可供选择，一种是使用文档视图类结构，另一种是直接使用对话框类结构；文档视图类结构方便文档的读取、保存和查看，且架构清晰[4]。但考虑到软件实际需求无需保存、与文件无关，所以使用更为简洁的对话框结构，直接在对话框上进行绘制图形，消除冗余的文档视图类结构，简化软件的开发过程。endprint

1.2 功能模块

功能模块主要包括算法介绍和算法演示两部分：

（1） 算法介绍。主要介绍深度优先遍历、广度优先遍历算法、Prim算法、Kruskal算法、Dijkastra算法和Floyd算法。

（2） 算法演示。通过具体实例，动态演示图的遍历问题、最小生成树问题及最短路径问题的相关算法的执行过程和运算结果，以及算法的一些核心操作步骤。

1.3 界面设计

为了程序的清晰和方便管理，采用一个

主对话框作为基本容器，里面可以容纳各种算法需要的控件，使用一个tab控件来容納三个无边框子对话框来作为绘制区，三个绘制区相互隔离，功能也相互隔离，方便单个处理和显示，在主对话框上有着公共的数据控件，三个子对话框通过主对话框指针来各自输出自己的信息，互不干扰。

2 系统功能模块的具体实现

2.1 相关技术背景

（1） MFC的GDI类库[4]。在VS平台下，借助MFC库来快速实现Windows窗体上的无向带权图的动态可视化与可交互化，在图节点中加入坐标属性并利用Windows的GDI对象完成可视化，利用强制刷新无效窗口区域和内存双缓冲绘图的原理完成图的遍历、最小生成树、单源最短路径的动态生成。

（2） 多线程同步[5]。在软件演示系统中，为了实现代码段执行的动态效果和图形演示动画同步进行，可以随时运行和暂停动态效果，需用到多线程的同步。使得最终运行效果达到图形界面与算法流程、算法数据信息同步，算法速度可调整、可中断。

（3） 数据交互。在演示系统中，为了实现人机交互，主要是解决操作者对对象的操作以及该操作能被对象所识别，需要借助鼠标点击的坐标位置判断操作者的操作是落在哪个对象的可视范围内，进而确定操作对象。然后对象反应出相应的操作结果，此结果的产生期间，数据结构与图形界面的变化是同步的，并有相应的数据信息输出可供操作者理解算法的流程和步骤。实现方法是使用鼠标右键点击区域定位和右键菜单来实现节点和边的交互。

2.2 算法演示模块

算法演示程序主要采用MFC库图对话框来实现算法可视化，主要负责对图中的节点、边及权值进行插入、删除和更新。在绘制图形方面，主要算法函数分为界面辅助类算法、图论算法函数及算法辅助函数、信息输出函数。相关算法函数的设计如图1所示。

（1） 深度优先遍历算法。从鼠标右键选定的节点开始访问当前节点，然后深度优先访问其邻接节点，并设置访问标识，在图形界面上就对此节点进行着色以表示被访问过，直到当前节点的相邻节点均已被访问过则退出函数，向上一层回溯。算法程序运行截图如图2所示。动态演示过程中在右侧数据显示区域动态显示遍历的各节点值，遍历结束后在信息输出区显示状态及最终遍历的序列列表。

（2） 广度优先遍历算法。从鼠标右键选定的节点开始每次访问一个节点前先将节点入队，然后将队头元素出队，进行访问着色和设置访问标识位，然后再将与此节点相邻的未被访问过的节点入队，然后再进行循环操作[6]。算法程序运行截图如图3所示。

（3） Prim算法函数。Prim算法对连通图生成一个最小生成树，先选择一个起点节点，每次选择与当前最小生成树相邻的节点中权值最小的点加入最小生成树中，直到所有节点都被加入生成树中为止[2，6]。由于采用的是链表结构存储图，所以图的节点可以动态变化，灵活性很强，但是在进行此类算法时，使用链表效率会稍稍降低，不能像矩阵那样进行随机存储和读取[7]。

在这个算法内部要用到两个容器，一个是节点容器，用来保存最小生成树的节点指针，另一个是边容器，用来保存最小生成树的边指针[8?9]。最开始是将选定节点加入最小生成树的节点容器中，然后对其进行访问和着色。接下来，从节点容器中进行遍历，找出各个节点相邻未访问过的节点中边权值最小的一个，然后将这个节点和连接此节点的边加入容器中去，并进行访问和着色。算法程序运行截图如图4所示。

（4） Dijkastra算法函数。加入一个链表转矩阵的函数，将现有的链表结构转换成相应的矩阵存储形式，然后对矩阵执行算法，还要加入一个处理矩阵和链表对应关系的函数，即根据索引获取节点指针和根据指针获取节点索引函数[10?11]。算法执行完毕后输出路径向量和距离向量中的值。算法程序运行截图如图5所示。在右侧数据显示区域动态显示算法执行过程中源点到各节点的距离。

3 结 论

针对目前数据结构中图算法实现过程可视化的问题，在分析图论遍历问题、生成树问题和最短路径问题算法的概念和原理的基础上，提出了一种基于MFC的动态绘制图形的方法，能智能动态地演示图论复杂的算法执行过程。通过软件实验演示，使用该教学辅助软件改进了原有的板书、PPT演示文稿的教学模式，降低了教师的讲解难度，增加了学生的兴趣，提高了教学效率。结果验证了动态智能演示软件的有效性和实用性。程序中采用的算法具有高效性、可行性，设计的动态智能演示软件能满足数据结构课堂演示的要求。

参考文献

[1] 徐新黎，胡磊.智能搜索算法在线教学实验平台的设计与实现[J].实验技术与管理，2012，29（5）：112?117.

[2] 周忠玉，方欢，方贤文.图论最短路径算法的图形化演示及系统设计[J].电脑知识与技术，2016，12（18）：159?160.

[3] 赵静.算法演示在“数据结构”课程教学中的应用探讨[J].黑龙江生态工程职业学院学报，2010（1）：109?110.

[4] 连远峰.基于MFC的可视化数据结构[M].北京：清华大学出版社，2014.

[5] 曹伟，刘风华，陈秋平.VC++环境下数据结构演示系统开发[J].科协论坛，2010（2）：54?55.

[6] CORMEN T H， LEISERSON C E， RIVEST R L， et al.算法导论[M].王刚，邹恒明，殷建平，等译.3版.北京：机械工业出版社，2013：362?391.

[7] WEISS M A. Data structures and algorithm analysis in C++ [M]. 3rd ed. BeiJing： Posts & Telecom Press， 2015.

[8] DROZDEK Adam. Data structures and algorithms in C++ [M]. 2nd ed. Beijing： Tsinghua University Press， 2003： 340?349.

[9] 严蔚敏，李冬梅，吴伟民.数据结构（C语言版）[M].北京：人民邮电出版社，2015.

[10] 郭伊.《数据结构》课程教学动态演示系统的设计与实现[D].杨凌：西北农林科技大学，2015.

[11] 王玢玥，李冬梅，李华颖，等.数据结构算法演示系统的设计[J].教育教学论坛，2016（28）：167?168.

[12] 李一春，王效东.两种UHF RFID标准标签数据结构差异对读写器设计的影响[J].物联网技术，2014，4（10）：15?16.endprint