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

《图的深度优先遍历实验报告.pdf》由会员分享，可在线阅读，更多相关《图的深度优先遍历实验报告.pdf（20页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、AXNAME 10typedef char VertexTypeMAXNAME;typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNodeVertexType data;ArcNode *firstarc;图的深度优先遍历实验报告VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;int kind;ALGraph;三实验内容编写 LocateVex 函数，Create 函数，prin

3、t 函数，构造的图的相关信息，得到其邻接表并输出显示。四。实验步骤1）结构体定义,预定义，全局变量定义。#includestdio.h#includestdlib.h#includestring.h#define FALSE 0#define TRUE 1#define MAX 20typedef int Boolean;#define MAX_VERTEX_NUM 20main 函数，输入要#define MAXNAME 10typedef char VertexTypeMAXNAME;typedef struct ArcNodeint adjvex;struct ArcNode *next

4、arc;ArcNode;typedef struct VNodeVertexType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;int kind;ALGraph;ALGraph G;Boolean visitedMAX;int degreeMAX_VERTEX_NUM;/定义一个数组求每一个顶点的总度数（无向图）或出度（有向图） 。2）编写 LocateVex 函数，确定所输入的边在 G 中的位置，返回该边所在的行数或或列数。int Lo

5、cateVex(ALGraph G,VertexType v)int i,n;for(n=0;nG.vexnum;n+)if(strcmp(v,G.verticesn.data)=0)i=n;return i;3）编写 Create 函数，采用邻接表构造图 G，返回结构体变量 G 的值，并统计每一个顶点的总度数或出度。ALGraph Create(ALGraph G)int i,j,k;VertexType v1,v2;ArcNode *p;printf(请输入要构造的图的顶点数和弧数：n);scanf(%d%d,&G.vexnum,&G.arcnum);printf(请输入每一个顶点的名字：

6、n);for(i=0;iG.vexnum;i+)scanf(%s,&G.verticesi.data);G.verticesi.firstarc=NULL;printf(各顶点的位置以及名称为：n);for(i=0;iG.vexnum;i+)printf(%6d%6sn,i,G.verticesi.data);printf(请输入要构造的是无向图还是有向图：无向用 0 表示，有向用 1 表示：n);scanf(%d,&G.kind);for(i=0;iG.vexnum;i+)degreei=0;printf(请输入每条弧的始点和终点：n);if(G.kind=1)for(k=0;kadjvex

7、=j;p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p;degreei+;if(G.kind=0)for(k=0;kadjvex=j;p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p;degreei+;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=i;p-nextarc=G.verticesj.firstarc;G.verticesj.firstarc=p;degreej+;return G;4）编写 print 函数，实现对所构建的图

8、的邻接表的输出。void print(ALGraph G)int i;ArcNode *p;for(i=0;inextarc)printf(%6d,p-adjvex);printf(n);if(G.kind=1)printf(出度为：%6dn,degreei);if(G.kind=0)printf(总度数为：%6dn,degreei);5）编写 FirstAdjVex 函数，返回 v 的第一个邻接点的编号。int FirstAdjVex(ALGraph G,int v)ArcNode *p;p=G.verticesv.firstarc;if(p)return(p-adjvex);elseret

9、urn -1;6） 编写 NextAdjVex 函数， 返回 v 第一个之后未被访问过的下一个邻接点。int NextAdjVex(ALGraph G,int v,int w)ArcNode *p;int i;for(p=G.verticesv.firstarc;p;p=p-nextarc)if(w!=p-adjvex)i=0;else i=1;if(i&p)return p-nextarc-adjvex;elsereturn -1;7）编写 DFS 函数，从第 i 个顶点出发递归地深度优先遍历图 G。void DFS(ALGraph G,int v)int w;visitedv=TRUE;p

10、rintf(%sn,G.verticesv.data);for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);8）编写 DFSTraverse 函数，对图 G 作深度优先遍历。void DFSTraverse(ALGraph G)int v;for(v=0;vG.vexnum;+v)visitedv=FALSE;for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);9）编写 main 函数，把以上几个函数结合到一起，用邻接表实现对一个图的构造，输入要构造的边的相关信息（总弧数，顶点

11、数，边的两个顶点的名称，有向图还是无向图） ，对其进行输出显示，并用深度优先搜索的方法遍历所构建的图。 main()ALGraph G;G=Create(G);printf(邻接表为：n);print(G);printf(深度遍历的结果为：DFSTraverse(G);五 实验结果源程序代码：#includestdio.h#includestdlib.h#includestring.h#define FALSE 0#define TRUE 1#define MAX 20typedef int Boolean;#define MAX_VERTEX_NUM 20#define MAXNAME 10

12、n);typedef char VertexTypeMAXNAME;typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNodeVertexType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;int kind;ALGraph;ALGraph G;Boolean visitedMAX;int degreeMAX_VERTEX_NUM

13、;int LocateVex(ALGraph G,VertexType v)int i,n;for(n=0;nG.vexnum;n+)if(strcmp(v,G.verticesn.data)=0)i=n;return i;ALGraph Create(ALGraph G)int i,j,k;VertexType v1,v2;ArcNode *p;printf(请输入要构造的图的顶点数和弧数：n);scanf(%d%d,&G.vexnum,&G.arcnum);printf(请输入每一个顶点的名字：n);for(i=0;iG.vexnum;i+)scanf(%s,&G.verticesi.da

14、ta);G.verticesi.firstarc=NULL;printf(各顶点的位置以及名称为：n);for(i=0;iG.vexnum;i+)printf(%6d%6sn,i,G.verticesi.data);printf(请输入要构造的是无向图还是有向图：无向用 0 表示，有向用 1 表示：n);scanf(%d,&G.kind);for(i=0;iG.vexnum;i+)degreei=0;printf(请输入每条弧的始点和终点：n);if(G.kind=1)for(k=0;kadjvex=j;p-nextarc=G.verticesi.firstarc;G.verticesi.fi

15、rstarc=p;degreei+;if(G.kind=0)for(k=0;kadjvex=j;p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p;degreei+;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=i;p-nextarc=G.verticesj.firstarc;G.verticesj.firstarc=p;degreej+;return G;void print(ALGraph G)int i;ArcNode *p;for(i=0;inextarc)printf(%6d,p-ad

16、jvex);printf(n);if(G.kind=1)printf(出度为：%6dn,degreei);if(G.kind=0)printf(总度数为：%6dn,degreei);int FirstAdjVex(ALGraph G,int v)ArcNode *p;p=G.verticesv.firstarc;if(p)return(p-adjvex);elsereturn -1;int NextAdjVex(ALGraph G,int v,int w)ArcNode *p;int i;for(p=G.verticesv.firstarc;p;p=p-nextarc)if(w!=p-adjv

17、ex)i=0;else i=1;if(i&p)return p-nextarc-adjvex;elsereturn -1;void DFS(ALGraph G,int v)int w;visitedv=TRUE;printf(%sn,G.verticesv.data);for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);void DFSTraverse(ALGraph G)int v;for(v=0;vG.vexnum;+v)visitedv=FALSE;for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);main()ALGraph G;G=Create(G);printf(邻接表为：n);print(G);printf(深度遍历的结果为：DFSTraverse(G);构造一个无向图 G，如图所示。n);V2V4V5V8运行结果截图：V1V3V6V7图 G实验结果显示：遍历的结果为：v1-v3-v7-v6-v2-v5-v8-v4。运行成功。六 实验结论可以运用深度优先搜索的方法遍历一个用邻接表构建的图。