图的存储结构的建立与遍历.doc

哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：图型结构及其应用实验题目：图的存储结构的建立与遍历（搜索）班级：1103102学号：1110310208姓名：张红阳设计成绩报告成绩指导老师一、 实验目的1.学会有向图和无向图数据结构的用法，掌握有向无向图的存储结构，包括邻接矩阵和邻接表。2.熟练掌握在邻接矩阵和邻接表存储结构上对（有向和无向）图进行深度优先（递归和非递归都要求）和广度优先搜索的算法。3.熟练掌握存储和显示（有向和无向）图的算法，包括生成森林(树)、序列和编号。4.学会以文件形式建立图的方法。二、实验要求及实验环境1.实验要求：(1)能够建立（有向和无向）图的邻接矩阵和邻接表存储结构(2)能够在邻接矩阵和邻接表存储结构上对（有向和无向）图进行深度优先（递归和非递归都要求）和广度优先搜索(3)能够存储和显示相应的搜索结果（深度优先或广度优先生成森林（或生成树）、深度优先或广度优先序列和编号）(4)以文件形式输入图的顶点和边，并显示相应的结果。要求顶点不少于10个，边不少于13个(5)软件功能结构安排合理，界面友好，便于使用2.实验环境：Windows下的vs2010。三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）1逻辑设计：(1)、主程序流程图：(2)、图的存储结构定义：const int NumVertices = 50;typedef structchar vertex NumVertices;int edgeNumVerticesNumVertices;int n, e;MTGraph;2物理设计：四、测试结果Graphdata.txt :测试结果：五、系统不足与经验体会1.只用了邻接矩阵表示图，没有用邻接表。2.图的顶点表示只能单个字符，不能多个字符。3.注意数据要及时初始化，如visited的初始化。4.要时刻注意栈的状态，注意栈空的条件判断，否则会出现溢出栈的错误，导致程序崩溃。5.写程序时要及时的加上注释，便于修改。六、附录：源代码（带注释）#include#include #include#includeusing namespace std;const int NumVertices = 50;typedef structchar vertex NumVertices;/顶点表int edgeNumVerticesNumVertices;/邻接矩阵边表, 可视为边之间的关系int n, e;/图的顶点数与边数MTGraph;void CreateMGragh(MTGraph *G) /建立图的邻接矩阵 for (int i=0; in; i+)for (int j=0; jn; j+) G -edgeij = 0; /邻接矩阵初始化ifstream in(Graphdata.txt);if(!in) coutfail to open the file. G -n G -e;for(int i = 0; i n; i+)in G -vertexi;for(int i = 0; i e; i+)int a, b;in a b;G -edgeab = 1;G -edgeba = 1;/如建立有向图则删去此句in.close();typedef enumFALSE,TRUE Boolean;Boolean visitedNumVertices;int bfnNumVertices;int dnf1NumVertices;int dnf2NumVertices;int Count;void ShowFS(int Fn, MTGraph *G)cout 顶点的编号: ;for(int i=0; in; i+)cout Fni ;cout endl;/=DFS：深度优先遍历的递归算法=void DFSM(MTGraph *G,int i) /以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵int j;cout vertexi ;visitedi = TRUE; /置已访问标志dnf1Count+ = i;for(j=0; jn; j+) /依次搜索Vi的邻接点if(G -edgeij = 1 & !visitedj)DFSM(G,j); /（Vi，Vj）E，且Vj未访问过，故Vj为新出发点void DFS1(MTGraph *G) int i;Count = 0;for(i=0; in; i+)visitedi = FALSE; /标志向量初始化for(i=0;in;i+)if(!visitedi) /Vi未访问过DFSM(G,i); /以Vi为源点开始DFS搜索cout endl;ShowFS(dnf1, G);/=DFS：深度优先遍历的非递归算法=void DFSNonrecur(MTGraph *G,int index) int i; stack s;cout vertexindex ;visitedindex = TRUE;dnf2Count+ = index;s.push(index);while(!s.empty() for(i = 0; i n; +i) if(G -edgeiindex = 1) & (visitedi = FALSE) index = i;cout vertexindex n) & (!s.empty() s.pop();if(!s.empty()index = s.top(); void DFS2(MTGraph *G) int i;Count = 0;for(i=0; in; i+)visitedi = FALSE; /标志向量初始化for(i=0;in;i+)if(!visitedi) /Vi未访问过DFSNonrecur(G,i); /以Vi为源点开始DFS搜索cout endl;ShowFS(dnf1, G);/=BFS：广度优先遍历=void BFSX(MTGraph *G, int k) /以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索int i;queue Q;cout vertexk ;/访问vkvisitedk = TRUE;bfnCount+ = k; /对vk进行编号Q.push(k);while(!Q.empty()i = Q.front();Q.pop();/vi出队for (int j = 0; j n; j+)if(G -edgeij = 1) & (visitedj = FALSE)cout vertexj ;visitedj = TRUE;bfnCount+ = j;/对vj进行编号Q.push(j);void BFS(MTGraph *G)/ 先广搜索一邻接表表示的图G；而以邻接矩阵表示G时，算法 完全相同 */int i; Count = 0;for ( i = 0; i n; i+) visited i =FALSE; /标志数组初始化for ( i = 0; i n; i+) if (!visitedi) BFSX (G, i); /从顶点 i 出发的一次搜索，DFSX (G, i )cout endl;ShowFS(bfn, G);void Initialization(MTGraph *G)/初始化G for(int i=0; iNumVertices; i+) for(int j=0; jedgeij = 0; for(int k=0; kvertexk = NULL;int main()MTGraph *G;G =