沈阳理工大学课程设计专用纸
0
摘 要
本文采用图的邻接矩阵实现了最短路径问题中图的存储；采用队列实现了图的广度优先搜索（BFS），用类的成员函数实现了其各个功能。本C++程序实现了图的最短路径存储及BFS遍历，采用Visual C++ 6.0的控制台工程和MFC工程分别实现了邻接矩阵在桌面上的的显示以及实现对图的广度遍历程序，通过对两种程序的测试结果表明：基于BFS算法的图的遍历算法原理正确，两种程序均能正确求解给定的图的遍历问题。
关键词:邻接矩阵；队列；广度优先搜索；控制台工程；MFC图形界面
I
沈阳理工大学课程设计专用纸
目 录
1 2
需求分析 ............................................................................................................................. 1 算法基本原理 ..................................................................................................................... 2 2.1邻接矩阵 ........................................................................................................................... 2 2.2图的遍历——广度优先搜索(BFS） .............................................................................. 3 3
类设计 ................................................................................................................................. 4 3.1 类的概述 .......................................................................................................................... 4 3.2 类的接口设计 .................................................................................................................. 4 3.3 类的实现 .......................................................................................................................... 4 4
基于控制台的应用程序 ..................................................................................................... 9 4.1 主函数设计 .................................................................................... 错误！未定义书签。 4.2 运行结果及分析 ............................................................................ 错误！未定义书签。 5
基于MFC的应用程序 ....................................................................................................... 9 5.1 图形界面设计 ................................................................................................................ 11 5.2 程序代码设计 ................................................................................................................ 14 5.3 运行结果及分析 ............................................................................................................ 19 结 论 ...................................................................................................................................... 21 参考文献 .................................................................................................................................. 22
II
沈阳理工大学课程设计专用纸
1 需求分析
(1)图的应用和研究可追溯到18世纪。1736年，被称为图论之父的欧拉解决了哥尼斯堡（Konigsberg）问题，从而奠定了图论这门学科及其应用的基础。
(2) 图作为一种非线性数据结构，被广泛应用与多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、人工智能、编译系统等领域，在这些技术领域中把图结构作为解决的数学手段之一。
(3)程序测试数据来自姜学军 李筠主编的《数据结构（C语言描述）》中，所选的无向图是:
图 1
8 4 5 6 7 2 3 1 1