实验四 图的深度优先与广度优先遍历 实验时间：2011年5月12日，12:50 -15:50（地点：7-215） 实验目的：理解图的逻辑特点；掌握理解图的两种主要存储结构（邻接矩阵和邻接表），掌握图的构造、深度优先遍历、广度优先遍历算法。 具体实验题目：（任课教师根据实验大纲自己指定） 每位同学按下述要求实现相应算法： 根据从键盘输入的数据创建图（图的存储结构可采用邻接矩阵或邻接表），并对图进行深度优先搜索和广度优先搜索 1）问题描述：在主程序中提供下列菜单： 1… 图的建立 2… 深度优先遍历图 3… 广度优先遍历图 0… 结束 2）实验要求：图的存储可采用邻接表或邻接矩阵；定义下列过程： CreateGraph(): 按从键盘的数据建立图 DFSGrahp()：深度优先遍历图 BFSGrahp()：广度优先遍历图 算法设计思路简介： 图的深度优先搜索是个回溯过程，采用递归遍历，用数组 visit来记录邻接点是否被访问过，遍历算法是通过 DFSTraverse函数对所有点循环，防止图是非连通的（或非强连通）； 图的广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，故可用队列来储存顶点。 算法描述： S1：自定义图的类型 AG,AN,DG,DN，以及邻接表的存储结构类型 ArcNode； S2：创建图graph，其中包含头节点数组 vertex[],邻接点个数 vexnum,边（弧）的个数 arcnum,以及图的类型 kind; S3:为图的广度优先搜索建立队列，并对队列进行必要的操作（入队，出队，队空，队满）； S4：创建图函数 CreateGraph(Graph &G,int n,int e,string kind),建立需要的图或者网络，期中创建过程中是利用头结点插入法； S5：visit(Graph G,int u)函数用来访问图的邻接点，输出节点信息； S6：FirstAdjVex(Graph G,int v)函数用来返回头节点的第一个边节点，NextAdjVex(Graph G,int v,int w)用来返回头节点的v 节点后的节点； S7：深度优先搜索函数 DFSGraph(Graph G,int v)递归搜索图，在函数 DFSTraverse(Graph G)中循环调用深度优先搜索函数，实现图的深度优先搜索函数； S8：BFSGraph(Graph G)广度优先搜索图，搜索过程中将未被访问的点一次入队，在节点出队过程中将与该节点的邻接点依次入队； S9：在主函数中调用以上函数创建图，深度、广度优先搜索图，记录结果； 源代码： #include #include #include using namespace std; #define MAX_VERTEX_NUM 20 #define ...
VIP
