哈工大数据结构-图的建立与遍历

《哈工大数据结构-图的建立与遍历》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项0名称：图的建立与遍历实验题目：图的建立与遍历设计成绩报告成绩指导老师一、实验目的1.学会用邻接表、邻接矩阵构建有向图和无向图2.加深对深度优先搜索和广度优先搜索的理解，并能够在邻接表和邻接矩阵上进行深度优先和广度优遍历。二、实验要求及实验环境（1）能够建立（有向和无向）图的邻接矩阵和邻接表存储结构（2）能够在邻接矩阵和邻接表存储结构上对（有向和无向）图进行深度优先（递归和非递归都要求）和广度优先搜索（3）能够存储和显示相应的搜索结果（深度优先或广度

2、优先生成森林（或生成树）、深度优先或广度优先序列和编号）（4）以文件形式输入图的顶点和边，并显示相应的结果。要求顶点不少于10个，边不少于13个本程序在win7下codeblock上运行三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）1.逻辑设计定义图邻接矩阵的结构体：typedefstruct{charvertexLNumVerticesJ;//顶点向量intedge[NumVertices][NumVertices];//邻接矩陈intn,e;//图当前的顶点数，边数JMTGraph;t

3、ypedefstructnode{//弧所指向的顶点位置"权值//指14下一条弧的指针定义邻接表的结构体:intadjvex;intcost;structnode*next;JEdgeNode;typedef1.学会用邻接表、邻接矩阵构建有向图和无向图2.加深对深度优先搜索和广度优先搜索的理解，并能够在邻接表和邻接矩阵上进行深度优先和广度优遍历。二、实验要求及实验环境（1）能够建立（有向和无向）图的邻接矩阵和邻接表存储结构（2）能够在邻接矩阵和邻接表存储结构上对（有向和无向）图进行深度优先（递归和非递归都要求）和广度优先搜索（3）能够

4、存储和显示相应的搜索结果（深度优先或广度优先生成森林（或生成树）、深度优先或广度优先序列和编号）（4）以文件形式输入图的顶点和边，并显示相应的结果。要求顶点不少于10个，边不少于13个本程序在win7下codeblock上运行三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）1.逻辑设计定义图邻接矩阵的结构体：typedefstruct{charvertexLNumVerticesJ;//顶点向量intedge[NumVertices][NumVertices];//邻接矩陈intn,e;//

5、图当前的顶点数，边数JMTGraph;typedefstructnode{//弧所指向的顶点位置"权值//指14下一条弧的指针定义邻接表的结构体:intadjvex;intcost;structnode*next;JEdgeNode;typedefstruct{charvertex;//顶点fe息EdgeNode*fir$tedge;//指向第一条依附于该顶点的弧的指针}VertexNode;typedefstruct{VertexNodevexlistlNumVerticesJ;intn,e;//顶点数弧数}AdjGraph;邻接表

6、构建图1.物理设计程序模块的调川：邻接矩阵构建阁_rI用调度先归索深优递搜-用调度先递搜深优非归I用调度先索•d广优搜voiT-用调度先索•d广优搜VO1度先归索深优递搜有向图void无向图void有向图void无向图voidCreateMGraphCreateMGraphCreateGraph2(CreateGraph1(2(MTGraphKMTGraphAdjGraphG)AdjGraphG)*G)*G)voidDFSvoidDFS1voidDFS索voidvoidBFS1BFSTraversvoidBFS2BFSTraversv

7、oidDFS1voidDFSTM(M(NonrDFS2(MTel(M(Adje2(Ad(AdjraversTGraMTGrecur((MTGGrapTGraGrapjGrapGrapel(AdphaphMTGraphhphhh*G)hjGrap*G,in*G)raph*G)int*G)*G，in*G，inh*G)ti，int*G,ink，inttk)ti,intcounttcountcount)index))•intcount四、测试结果J

8、graph:gy^文件(F)编辑(E)格式(O)查看(V)帮助(KJHGFED5C1±B122

9、42568587888wAoo11223344ro567、v递归深度优先遍历为：ABCFEJDGHK顶点的编号：0125483679非递归深度优先遍历为：ABCFEJDGHK顶点的编号：0125483679非递归广度优先