采用邻接表表示法创建图并进行图的深度优先搜索遍历

1、东华理工大学长江学院信息工程系数据结构课题设计专业：计算机科学与技术姓名：赵进城学号：20173031308日期：2018/05/24课程名称数据结构实验地点信工楼三楼机房308实验名称图的基本操作与应用指导教师成绩2.采用邻接表表示法创建图并进行图的深度优先搜索遍历实验内容用邻接表表示图进行 HYPERLINK /s?wd=%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao t /question/_blank 深度优先遍历时，通常采用栈来

2、实现算法邻接表是图的一种链式 HYPERLINK /s?wd=%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao t /question/_blank 存储结构。在邻接表中，对图中每个顶点建立一个带头结点的单链表，所有的头结点构成一个数组，第i个单链表中的结点表示依附于顶点vi的边。也就是说指的是点，表示的是边，因为两点决定了一条边。以下图为例：与0号点相连的有2条边，一条与1号点相连，一条与3号点相连。所以v0后面有两个结点，前面的序号分别为1、3，3后没有了，为空；与1号点

3、相连的有3条边，分别与0、2、3号点相连。所以v0后面有3个结点，前面的序号分别为0、2、3，3后没有了，为空；与2号点相连的有1条边，与1号点相连。所以v0后面有1个结点，前面的序号为1，1后没有了，为空。二、实验目的1.掌握图的基本概念和邻接表存储结构。2.掌握图的邻接表存储结构的基本算法实现。3.掌握图在邻接表存储结构上遍历算法的实现。三、代码运行截图四、附源代码：/ data.cpp : Defines the entry point for the console application./#include stdafx.h#include using namespace std;#

4、define MVNum 100/最大顶点数typedef char VerTexType;/假设顶点的数据类型为字符型 /-图的邻接表-typedef struct ArcNode /边结点 int adjvex; /该边所指向的顶点的位置 struct ArcNode *nextarc; /指向下一条边的指针 ArcNode; typedef struct VNode VerTexType data; /顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的边的指针 VNode, AdjListMVNum; /AdjList表示邻接表类型 typedef struct A

5、djList vertices; /邻接表 int vexnum, arcnum; /图的当前顶点数和边数 ALGraph;bool visitedMVNum; /访问标志数组，其初值为false int LocateVex(ALGraph G , VerTexType v)/确定点v在G中的位置for(int i = 0; i G.vexnum; +i)if(G.verticesi.data = v)return i;return -1;/LocateVexvoid CreateUDG(ALGraph &G) /采用邻接表表示法，创建无向图Gint i , k;cout G.vexnum G

6、.arcnum;/输入总顶点数，总边数 cout endl;cout 输入点的名称，如a endl;for(i = 0; i G.vexnum; +i) /输入各点，构造表头结点表cout 请输入第 (i+1) G.verticesi.data; /输入顶点值 G.verticesi.firstarc=NULL;/初始化表头结点的指针域为NULL /forcout endl; cout 输入边依附的顶点，如a b endl;for(k = 0; k G.arcnum;+k) /输入各边，构造邻接表VerTexType v1 , v2;int i , j;cout 请输入第 (k + 1) v1

7、 v2; /输入一条边依附的两个顶点i = LocateVex(G, v1); j = LocateVex(G, v2);/确定v1和v2在G中位置，即顶点在G.vertices中的序号 ArcNode *p1=new ArcNode; /生成一个新的边结点*p1 p1-adjvex=j; /邻接点序号为j p1-nextarc= G.verticesi.firstarc; G.verticesi.firstarc=p1; /将新结点*p1插入顶点vi的边表头部ArcNode *p2=new ArcNode; /生成另一个对称的新的边结点*p2 p2-adjvex=i; /邻接点序号为i p2

8、-nextarc= G.verticesj.firstarc; G.verticesj.firstarc=p2; /将新结点*p2插入顶点vj的边表头部 /for /CreateUDGvoid DFS(ALGraph G, int v) /图G为邻接表类型 cout G.verticesv.data adjvex; /表示w是v的邻接点 if(!visitedw) DFS(G, w); /如果w未访问，则递归调用DFS p = p-nextarc; /p指向下一个边结点 /DFSint main()cout *采用邻接表表示图的深度优先搜索遍历* endl endl;ALGraph G;CreateUDG(G);cout endl;cout 无向连通图G创建完成！ endl endl;cout c;int i;for(i = 0 ; i G.vexnum ; +i)if(c = G.verticesi.data)break;cout = G.vexnum)cout 该点不存在，请