图的深度优先遍历实验报告.doc

《图的深度优先遍历实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.一．实验目的熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。二．实验原理深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。图的邻接表的存储表示：#defineMAX_VERTEX_NUM20#defineMA

2、XNAME10typedefcharVertexType[MAXNAME];typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{VertexTypedata;ArcNode*firstarc;页脚.}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;三．实验内容编写LocateVex函数，Create函数，print函

3、数，main函数，输入要构造的图的相关信息，得到其邻接表并输出显示。四。实验步骤1）结构体定义,预定义，全局变量定义。#include"stdio.h"#include"stdlib.h"#include"string.h"#defineFALSE0#defineTRUE1#defineMAX20typedefintBoolean;#defineMAX_VERTEX_NUM20页脚.#defineMAXNAME10typedefcharVertexType[MAXNAME];typedefstructArcNode{intadjvex;structArcNode

4、*nextarc;}ArcNode;typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;ALGraphG;Booleanvisited[MAX];intdegree[MAX_VERTEX_NUM];//定义一个数组求每一个顶点的总度数（无向图）或出度（有向图）。1）编写LocateVex函数，确定所输入的边在G中的位置，返回该

5、边所在的行数或或列数。intLocateVex(ALGraphG,VertexTypev)页脚.{inti,n;for(n=0;n

6、exnum,&G.arcnum);printf("请输入每一个顶点的名字：");for(i=0;i

7、r(i=0;iadjvex=j;p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;degree[i]++;}}页脚.if(G.

8、kind==0){for