数据结构 图的遍历

1、实 验 报 告 一学号: 姓名: 完成日期:题目 图的遍历一.问题描述从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问, 并且使图中的每个顶点仅被访问一次的过程。 图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。试编写一个程序，完成对图的遍历。二.算法设计2.1 设计思想1以邻接矩阵为存储结构，实现无向图的深度优先遍历和广度优先遍历。 2分别输出每种遍历下的结点访问序列.从图中某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是

2、许多图的算法的基础。2.1.1图的遍历介绍 2.1.2基本概念 图的遍历: 图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问, 并且使图中的每个顶点仅被访问一次的过程。 图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。 2.1.3 分类 按照搜索途径的不同，图的遍历可分为：深度优先遍历（Depth-First Traverse）和广度优先遍历（Breadth-First Traverse）两大类。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法

3、。 （1）深度优先遍历 (Depth-First Traverse) 特点：尽可能先对纵深方向的顶点进行访问 深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。图的深度优先遍历类似于树的前序遍历。

4、采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。 . 深度优先搜索的过程 a 基本思想: 首先访问图中某一个指定的出发点Vi； 然后任选一个与顶点Vi相邻的未被访问过的顶点Vj； 以Vj为新的出发点继续进行深度优先搜索，直至图中所有顶点均被访问过。 b具体过程: 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已

5、访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。(2)广度优先遍历（Breadth-First Traverse）: 特点：尽可能先从指定的出发点，横向地访问图中各个顶点。 广度优先遍历的定义 在访问了起始点之后,首先依次访问起始点的各个

6、邻接点,然后依次访问那些顶点中未被访问过的邻接点.依此类推,直到所有被访问到的顶点的邻接点都被访问过为止. 广度优先搜索的过程a算法基本思想： 首先访问图中某一指定的出发点Vi； 然后依次访问Vi的所有接点Vi1，Vi2Vit； 再次访问Vi1，Vi2，Vit的邻接点中未经访问过的顶点，依此类推，直到图中所有顶点均被访问为止。b具体过程： 从广度优先搜索遍历方法可知，先被访问的顶点的邻接点也被访问，即假设顶点V在W之前被访问，那么顶点V的所有未经访问的邻接点也在顶点W的所有未经访问的邻接点之前被访问。这样可以在广度优先遍历的算法中设置一个队列结构，用以保存已访问过的顶点的序号，访问该顶点的所有

7、未经访问的顶点。 广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样会出现回退的现象。因此它不是个递归的过程。为了实现逐层访问，算法中使用了一个队列以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。为了避免重复访问，需要一个辅助函数visitvex给被访问过的顶点加标记。 2.2 概要设计规格说明：数据类型及函数定义 定义图typedef struct int VM; int RMM; int vexnum; Graph;创建图void creatgraph(Graph *g,int n)打印图的邻接矩阵 void printgraph(Graph *

8、g)访问顶点 void visitvex(Graph *g,int vex)深度递归遍历 void dfs(Graph *g,int vex)队列的基本操作定义队列 typedef struct int VM; int front; int rear; Queue; 判断队列是否为空 quempty(Queue *q) 入队操作 enqueue(Queue *q,int e)出队操作 dequeue(Queue *q)广度遍历 void BESTraverse(Graph *g)本程序包含四个模块：主程序模块void main ()构造一个图；打印图的邻接矩阵进行深度优先遍历图；进行广度优先遍

9、历图；2.3 功能注释本程序划分为三个不同的模块分别编译。其优点在于编译时如果有错误，只需要对出错的模块进行重新编译，无错的模块则不必再编译。因而可以明显地节约整个程序的编译调试时间。用预处理命令#include可以包含有关文件的信息。#inlcude命令经过预处理命令（即在编译前进行的处理）后，会将其后有关文件的内容拷贝到命令所在的源程序文件中。该文件里包括常量的定义、结构的定义、函数原型的说明（即函数的返回类型、函数名以及函数参数类型的说明）等2.4 详细设计 算法思想算法一： 存在的问题：图中可能存在回路，且图的任一顶点都可能与其他顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾

10、经访问过的顶点解决办法: 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助标志visitvex 辅助数组visitvex 的初始状态为0，在图的遍历过程中，一旦此顶点被访问，就立刻让visitvex为1，防止它被多次访问Visitevex0n-1的设置： 图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visitvex0n-1，其初值为假，一旦访问了顶点Vi之后，便将visitvexi置为真。算法二：以邻接矩阵为存储结构的图的深度优先搜索遍历的算法 void dfs(Gra

11、ph *g,int vex) int w; visitedvex=1; 标记vex已被访问过 visitvex(g,vex); 访问图g的顶点 for(w=firstadjvex(g,vex);w0;w=nextadjvex(g,vex,w) if(!visitedw) dfs(g,w); 从初始点vex出发广度优先搜索由邻接矩阵R表示的图 void dfstraverse(Graph *g) int i; for(i=1;ivexnum;i+) visitedi=0; for(i=1;ivexnum;i+) if(!visitedi) dfs(g,i); 算法三：以邻接矩阵为存储结构的图的广

12、度优先搜索遍历的算法 从初始点vex出发广度优先搜索由邻接矩阵R表示的图void BESTraverse(Graph *g) int i; Queue *q=(Queue *)malloc(sizeof(Queue); 定义一个队列q，其元素类型应为Queue型 for(i=1;ivexnum;i+) visitedi=0; 标记初始点i未被已访问过 initqueue(q); 初始化队列 for(i=1;ivexnum;i+) if(!visitedi) visitedi=1; 标记初始点i已访问过 visitvex(g,g-Vi); 访问顶点i enqueue(q,g-Vi); 将已访问过

13、的初始点序号i入队 while(!quempty(q) 当队列非空时进行循环处理 依次搜索i的每一个可能的邻接点 int u,w; u=dequeue(q); for(w=firstadjvex(g,u);w0;w=nextadjvex(g,u,w) if(!visitedw) visitedw=1; 访问一个未被访问过的邻接点 visitvex(g,w); 访问顶点w enqueue(q,w); 顶点w出队 三.用户手册:3.1运行环境本程序在windows环境下的Visual C+ 6.0的编译环境下执行。 3.2执行文件四.测试数据及结果分析 4.1.1调试过程中遇到的问题以及对设计与实

14、现的回顾讨论和分析：一个图的DFS序列不一定惟一:当从某顶点x出发搜索时，若x的邻接点有多个尚未访问过，则我们可任选一个访问之；源点和存储结构的内容均已确定的图的DFS序列惟一；邻接矩阵表示的图确定源点后，DFS序列惟一；DFS算法中，当从vi出发搜索时，是在邻接矩阵的第i行上从左至右选择下一个未曾访问过的邻接点作为新的出发点，若这样的邻接点多于一个，则选中的总是序号较小的那一个。4.2运行结果五.调试报告: 上机实验是对我们的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个环节。通常，我们在上机实验中遇到的问题比平时的习题复杂得多，也更接近实际,所以能从很大程度上提高我们的

15、综合能力。一方面，实验着眼于原理与应用的结合点，使我们学会如何把书上学到的知识用于解决实际的问题，从而培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握课堂上所讲授的内容的目的。通过这一次的课程设计，我们同学之间相互交流了许多的专业知识，在查阅文献资料时不知不觉中就学习到许多专业方面的知识，让我们学习到的知识得到了实践，而且同学之间的相互合作能力也得到加强。同时明白到在往后的学习当中，当编译程序遇到了错误的时候，不能慌乱，要认真阅读程序，找出错误，当错误无法排除的时候，要查阅各种文献，对于我们的程序调试有很大的帮助。附录: #include #include

16、 #define INF 32767 /*INF表示*/typedef int InfoType;#defineMAXV 100/*最大顶点个数*/#define MAXQUEUE 10 /* 队列的最大容量 */struct node /* 图的顶点结构定义 */ int vertex; struct node *nextnode;typedef struct node *graph; /* 图的结构指针 */struct node head9; /* 图的顶点数组 */ int visit9; /* 遍历标记数组 */int queueMAXQUEUE; /* 定义序列数组 */int f

17、ront = -1; /* 序列前端 */int rear = -1; /* 序列后端 */*二维数组向邻接表的转化*/void creategraph(int node202,int num) graph newnode; /* 顶点指针 */ graph ptr; int from; /* 边起点 */ int to; /* 边终点 */ int i; for ( i = 0; i vertex = to; /* 顶点内容 */ newnode-nextnode = NULL; /* 设定指针初值 */ ptr = &(headfrom); /* 顶点位置 */ while ( ptr-n

18、extnode != NULL ) /* 遍历至链表尾 */ ptr = ptr-nextnode; /* 下一个顶点 */ ptr-nextnode = newnode; /* 插入第i个节点的链表尾部 */ /* 数值入队列*/int enqueue(int value)if ( rear = MAXQUEUE ) /* 检查伫列是否全满 */ return -1; /* 无法存入 */ rear+; /* 后端指标往前移 */ queuerear = value; /* 存入伫列 */ return 0;/* 数值出队列*/int dequeue()if ( front = rear )

19、 /* 队列是否为空 */ return -1; /* 为空，无法取出 */ front+; /* 前端指标往前移 */ return queuefront; /* 从队列中取出信息 */* 图形的广度优先遍历*/void bfs(int current)graph ptr; /* 处理第一个顶点 */ enqueue(current); /* 将顶点存入队列 */ visitcurrent = 1; /* 已遍历过记录标志置疑1*/ printf( Vertex%dn,current); /* 打印输出遍历顶点值 */ while ( front != rear ) /* 队列是否为空 */

20、current = dequeue(); /* 将顶点从队列列取出 */ ptr = headcurrent.nextnode; /* 顶点位置 */ while ( ptr != NULL ) /* 遍历至链表尾 */ if ( visitptr-vertex = 0 ) /*顶点没有遍历过*/ enqueue(ptr-vertex); /* 将定点放入队列 */ visitptr-vertex = 1; /* 置遍历标记为1 */ printf( Vertex%dn,ptr-vertex);/* 印出遍历顶点值 */ ptr = ptr-nextnode; /* 下一个顶点 */ /*以下

21、定义邻接矩阵类型*/typedef struct int no;/*顶点编号*/InfoType info;/*顶点其他信息*/ VertexType;/*顶点类型*/typedef struct /*图的定义*/ int edgesMAXVMAXV; /*邻接矩阵*/ int vexnum,arcnum; /*顶点数，弧数*/VertexType vexsMAXV;/*存放顶点信息*/ MGraph;/*图的邻接矩阵类型*/*以下定义邻接表类型*/typedef struct ANode /*弧的结点结构类型*/int adjvex; /*该弧的终点位置*/ struct ANode *ne

22、xtarc; /*指向下一条弧的指针*/ InfoType info; /*该弧的相关信息,这里用于存放权值*/ ArcNode;typedef int Vertex;typedef struct Vnode /*邻接表头结点的类型*/Vertex data; /*顶点信息*/ ArcNode *firstarc; /*指向第一条弧*/ VNode;typedef VNode AdjListMAXV;/*AdjList是邻接表类型*/typedef struct AdjList adjlist; /*邻接表*/ int n,e; /*图中顶点数n和边数e*/ ALGraph; /*图的邻接表类

23、型*/int visitedMAXV;void MatToList(MGraph g,ALGraph *&G)/*将邻接矩阵g转换成邻接表G*/int i,j,n=g.vexnum;/*n为顶点数*/ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph);for (i=0;iadjlisti.firstarc=NULL;for (i=0;i=0;j-)if (g.edgesij!=INF)/*邻接矩阵的当前元素不为0*/ p=(ArcNode *)malloc(sizeof(ArcNode);/*创建一个结点*p*/p-adjvex=j;p-info=g.

24、edgesij;p-nextarc=G-adjlisti.firstarc;G-adjlisti.firstarc=p;G-n=n;G-e=g.arcnum;void ListToMat(ALGraph *G,MGraph &g)/*将邻接表G转换成邻接矩阵g*/int i,j,n=G-n;ArcNode *p;for (i=0;in;i+) /*g.edgesij赋初值0*/ for (j=0;jn;j+)g.edgesij=INF;for (i=0;iadjlisti.firstarc; while(p!=NULL)g.edgesip-adjvex=p-info;p=p-nextarc;g

25、.vexnum=n;g.arcnum=G-e;void DispMat(MGraph g)/*输出邻接矩阵g*/int i,j; for (i=0;ig.vexnum;i+)for (j=0;jg.vexnum;j+)if (g.edgesij=INF)printf(%3s,);else printf(%3d,g.edgesij); printf(n);void DispAdj(ALGraph *G)/*输出邻接表G*/int i;ArcNode *p;for (i=0;in;i+)p=G-adjlisti.firstarc;if (p!=NULL) printf(%3d: ,i);while

26、(p!=NULL)printf(%3d,p-adjvex);p=p-nextarc;printf(n);void DFS(ALGraph *G,int v) ArcNode *p;visitedv=1; /*置已访问标记*/printf(%3d,v); /*输出被访问顶点的编号*/p=G-adjlistv.firstarc; /*p指向顶点v的第一条弧的弧头结点*/while (p!=NULL) if (visitedp-adjvex=0)/*若p-adjvex顶点未访问,递归访问它*/DFS(G,p-adjvex); p=p-nextarc; /*p指向顶点v的下一条弧的弧头结点*/void

27、 DFS1(ALGraph *G,int v)int i,visitedMAXV,StMAXV,top=-1;ArcNode *p; for (i=0;in;i+) visitedi=0;/*结点访问标志均置成0*/ printf(%3d,v);/*访问顶点v*/top+;/*v入栈*/Sttop=v;visitedv=1;while (top=-1)/*栈不空时循环*/v=Sttop;top-;/*取栈顶顶点*/p=G-adjlistv.firstarc; while (p!=NULL & visitedp-adjvex=1) p=p-nextarc; if (p=NULL)/*若没有退到前

28、一个*/ top-;else/*若有,选择一个*/v=p-adjvex;printf(%3d,v);/*访问顶点*/visitedv=1;top+;/*入栈*/Sttop=v;printf(n);void main()int i,j;MGraph g,g1;ALGraph *G;graph ptr;/* 边信息数组 */int node202 = 1, 2, 2, 1, 6, 3, 3, 6,2, 4, 4, 2; 1, 5, 5, 1, 3, 7, 7, 3,1, 7, 7, 1,4, 8, 8, 4,5, 8, 8, 5,2, 8, 8, 2,7, 8, 8, 7 ;int AMAXV6=INF,5,INF,7,INF,INF,INF,INF,4,INF,INF,INF,8,INF,INF,INF,INF,9,INF,INF,5,INF,INF,6,INF,INF,INF,5,INF,INF,3,INF,INF,INF,1,INF;g.vexnum=6;g.arcn