沈阳理工大学课程设计专用纸PAGEII0摘要本文采用图的邻接矩阵实现了最短路径问题中图的存储；采用队列实现了图的广度优先搜索（BFS），用类的成员函数实现了其各个功能。本C++程序实现了图的最短路径存储及BFS遍历，采用VisualC++6.0的控制台工程和MFC工程分别实现了邻接矩阵在桌面上的的显示以及实现对图的广度遍历程序，通过对两种程序的测试结果表明：基于BFS算法的图的遍历算法原理正确，两种程序均能正确求解给定的图的遍历问题。关键词:邻接矩阵；队列；广度优先搜索；控制台工程；MFC图形界面目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc406600256"1需求分析PAGEREF_Toc406600256\h1HYPERLINK\l"_Toc406600257"2算法基本原理PAGEREF_Toc406600257\h1HYPERLINK\l"_Toc406600258"2.1邻接矩阵PAGEREF_Toc406600258\h1HYPERLINK\l"_Toc406600259"2.2图的遍历——广度优先搜索(BFS）PAGEREF_Toc406600259\h2HYPERLINK\l"_Toc406600260"3类设计PAGEREF_Toc406600260\h3HYPERLINK\l"_Toc406600261"3.1类的概述PAGEREF_Toc406600261\h3HYPERLINK\l"_Toc406600262"3.2类的接口设计PAGEREF_Toc406600262\h4HYPERLINK\l"_Toc406600263"3.3类的实现PAGEREF_Toc406600263\h5HYPERLINK\l"_Toc406600264"4基于控制台的应用程序PAGEREF_Toc406600264\h9HYPERLINK\l"_Toc406600265"4.1主函数设计PAGEREF_Toc406600265\h9HYPERLINK\l"_Toc406600266"4.2运行结果及分析PAGEREF_Toc406600266\h10HYPERLINK\l"_Toc406600267"5基于MFC的应用程序PAGEREF_Toc406600267\h12HYPERLINK\l"_Toc406600268"5.1图形界面设计PAGEREF_Toc406600268\h12HYPERLINK\l"_Toc406600269"5.2程序代码设计PAGEREF_Toc406600269\h14HYPERLINK\l"_Toc406600270"5.3运行结果及分析PAGEREF_Toc406600270\h20HYPERLINK\l"_Toc406600271"结论PAGEREF_Toc406600271\h22HYPERLINK\l"_Toc406600272"参考文献PAGEREF_Toc406600272\h23需求分析(1)图的应用和研究可追溯到18世纪。1736年，被称为图论之父的欧拉解决了哥尼斯堡（Konigsberg）问题，从而奠定了图论这门学科及其应用的基础。(2)图作为一种非线性数据结构，被广泛应用与多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、人工智能、编译系统等领域，在这些技术领域中把图结构作为解决的数学手段之一。(3)程序测试数据来自姜学军李筠主编的《数据结构（C语言描述）》中，所选的无向图是:13265748图1算法基本原理2.1邻接矩阵邻接矩阵是表示节点之间的相邻接关系的矩阵。若G是有n个节点的图，则G的邻接矩阵是如下定义的nXn矩阵。如图所示图G的邻接矩阵如下：21011110101101101043图GG的邻接矩阵2.2图的遍历——广度优先搜索(BFS）例如，有如下无向图：13265748操作步骤如下：=1\*GB3①先输出1（1为起点）,将1入队；=2\*GB3②1出队，由于1的邻接顶点2和3未被访问过，输出2和3并将2和3入队；=3\*GB3③2出队,2的邻接顶点1;=4\*GB3④3出队，由于3的邻接顶点1被访问过，而邻