5.3 图的遍历演示

第3讲图的遍历——教学讲义图的遍历就是从图中的某个顶点出发，按某种方法对图中的所有顶点访问且仅访问一次。

图的遍历比起树的遍历要复杂得多。

由于图中顶点关系是任意的，即图中顶点之间是多对多的关系，图可能是非连通图，图中还可能有回路存在，因此在访问了某个顶点后，可能沿着某条路径搜索后又回到该顶点上。

为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，因此要为图设置一个访问标志数组visited[n]，用于标示图中每个顶点是否被访问过，它的初始值为0(假)，一旦顶点v i访问过，则置visited[i]为1(真)，以表示该顶点已访问。

对于图的遍历，通常有两种方法，即深度优先搜索和广度优先搜索。

1 深度优先搜索深度优先搜索（Depth_First Search，DFS）是指按照深度方向搜索，它类似于树的先根遍历，是树的先根遍历的推广。

深度优先搜索的基本思想是：（1）从图中某个顶点v0出发，首先访问v0。

（2）找出刚访问过的顶点的第一个未被访问的邻接点，然后访问该顶点。

以该定点为新顶点，重复此步骤，直到刚访问过的顶点没有未被访问的邻接点为止。

（3）返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。

然后执行步骤（2）。

下图给出了一个深度优先搜索的过程图示，其中实箭头代表访问方向，虚箭头代表回溯方向，箭头旁边的数字代表搜索顺序，A为起始顶点。

首先访问A，然后按图中序号对应的顺序进行深度优先搜索。

图中序号对应步骤的解释如下：（1）顶点A的未访邻接点有B、E、D，首先访问A的第一个未访邻接点B；（2）顶点B的未访邻接点有C、E，首先访问B的第一个未访邻接点C；（3）顶点C的未访邻接点只有F，访问F；（4）顶点F没有未访邻接点，回溯到C；（5）顶点C已没有未访邻接点，回溯到B；（6）顶点B的未访邻接点只剩下E，访问E；（7）顶点E的未访邻接点只剩下G，访问G；（8）顶点G的未访邻接点有D、H，首先访问G的第一个未访邻接点D；（9）顶点D没有未访邻接点，回溯到G；（10）顶点G的未访邻接点只剩下H，访问H；（11）顶点H的未访邻接点只有I，访问I；（12）顶点I没有未访邻接点，回溯到H；（13）顶点H已没有未访邻接点，回溯到G；（14）顶点G已没有未访邻接点，回溯到E；（15）顶点E已没有未访邻接点，回溯到B；（16）顶点B已没有未访邻接点，回溯到A。

约瑟夫环实验报告一．需求分析1、以邻接多重表为存储结构；2、实现连通和非连通的无向图的深度优先和广度优先遍历；3、要求利用栈实现无向图的深度优先遍历；4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集；5、用凹入表打印生成树；6、求出从一个结点到另外一个结点，但不经过另外一个指定结点的所有简单路径；二．概要设计1.设定图的抽象数据类型2. 栈的抽象数据类型定义3.队列的抽象数据类型定义三．详细设计程序设计如下：#include<stdio.h>#include <stdlib.h>#include<conio.h>#define MAXQUEUE 70 /* 伫列的最大容量*/struct node /* 图形顶点结构宣告*/{int vertex; /* 顶点资料*/struct node *nextnode; /* 指下一顶点的指标*/};typedef struct node *graph; /* 图形的结构新型态*/struct node head[61]; /* 图形顶点结构数组*/int visited[61]; /* 遍历记录数组*/int queue[MAXQUEUE]; /* 伫列的数组宣告*/int front = -1; /* 伫列的前端*/int rear = -1; /* 伫列的后端/* ---------------------------------------- *//* 建立图形*/ /* ---------------------------------------- */void creategraph(int *node,int num){graph newnode; /* 新顶点指标*/graph ptr;int from; /* 边线的起点*/int to; /* 边线的终点*/int i;for ( i = 0; i < num; i++ ) /* 读取边线的回路*/{from = node[i*2]; /* 边线的起点*/to = node[i*2+1]; /* 边线的终点/* 建立新顶点记忆体*/newnode = ( graph ) malloc(sizeof(struct node));newnode->vertex = to; /* 建立顶点内容*/newnode->nextnode = NULL; /* 设定指标初值*/ptr = &(head[from]); /* 顶点位置*/while ( ptr->nextnode != NULL ) /* 遍历至链表尾*/ptr = ptr->nextnode; /* 下一个顶点*/ptr->nextnode = newnode; /* 插入结尾*/}}/* ---------------------------------------- *//* 伫列资料的存入*/ /* ---------------------------------------- */int enqueue(int value)if ( rear >= MAXQUEUE ) /* 检查伫列是否全满*/return -1; /* 无法存入*/rear++; /* 后端指标往前移*/queue[rear] = value; /* 存入伫列*/}/* ---------------------------------------- *//* 伫列资料的取出*/ /* ---------------------------------------- */int dequeue(){if ( front == rear ) /* 检查伫列是否是空*/return -1; /* 无法取出*/front++; /* 前端指标往前移*/return queue[front]; /* 伫列取出*/}/* ---------------------------------------- *//* 图形的广度优先搜寻法*/ /* ---------------------------------------- */void bfs(int current){graph ptr;/* 处理第一个顶点*/enqueue(current); /* 将顶点存入伫列*/visited[current] = 1; /* 记录已遍历过*/printf("[%d] ",current); /* 印出遍历顶点值*/while ( front != rear ) /* 伫列是否是空的*/{current = dequeue(); /* 将顶点从伫列取出*/ptr = head[current].nextnode; /* 顶点位置*/while ( ptr != NULL ) /* 遍历至链表尾*/{if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过*/{enqueue(ptr->vertex); /* 递回遍历呼叫*/visited[ptr->vertex] = 1; /* 记录已遍历过*//* 印出遍历顶点值*/printf("[%d] ",ptr->vertex);}ptr = ptr->nextnode; /* 下一个顶点*/}}}/* ---------------------------------------- *//* 图形的深度优先搜寻法*/ /* ---------------------------------------- */void dfs(int current){graph ptr;visited[current] = 1; /* 记录已遍历过*/printf("[%d] ",current); /* 印出遍历顶点值*/ptr = head[current].nextnode; /* 顶点位置*/while ( ptr != NULL ) /* 遍历至链表尾*/{if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过*/dfs(ptr->vertex); /* 递回遍历呼叫*/ptr = ptr->nextnode; /* 下一个顶点*/}}/* ---------------------------------------- *//* 主程式: 建立图形后,将遍历内容印出. */ /* ---------------------------------------- */int main(){//clrscr();while(1){char c,a;graph ptr;int i;int node [60] [2] = { {1, 10}, {10, 1}, /* 边线数组*/{2, 10}, {10, 2},{2, 3}, {3, 2},{3, 4}, {4, 3},{3, 12}, {12, 3},{4, 13}, {13, 4}, {4, 5}, {5, 4}, {5, 6}, {6, 5}, {5, 7}, {7, 5}, {7, 8}, {8, 7}, {9, 10}, {10, 9}, {10, 11}, {11, 10}, {11, 14}, {14, 11}, {11, 12}, {12, 11}, {12, 15}, {15, 12}, {12, 13}, {13, 12}, {13, 16}, {16, 13}, {14, 17}, {17, 14}, {14, 18}, {18, 14}, {15, 19}, {19, 15}, {16, 20}, {20, 16}, {17, 18}, {18, 17}, {18, 23}, {23, 18}, {18, 19}, {19, 18}, {19, 23}, {23, 19}, {19, 24}, {24, 19}, {19, 20}, {20, 19},{20, 21}, {21, 20},{22, 23}, {23, 22},{24, 25}, {25,24}};//clrscr();printf("\n\n\n");printf(" 图的深度遍历和广度遍历? Y/N?\n");c=getch();if(c!='y'&&'Y')exit(0);//clrscr();printf("\n\n");printf("以下为各城市的代码:\n\n");printf("1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳; \n");printf("6:大连; 7:长春; 8:哈尔滨; 9:西宁; 10:兰州;\n");printf("11:西安; 12:郑州; 13:徐州; 14:成都; 15:武汉; \n");printf("16:上海; 17:昆明; 18:贵阳; 19:株州; 20:南昌;\n");printf("21:福州; 22:南宁; 23:柳州; 24:广州; 25:深圳.\n");for (i=1;i<=25;i++ ){head[i].vertex=i; /* 设定顶点值*/head[i].nextnode=NULL; /* 清除图形指标*/visited[i]=0; /* 设定遍历初值*/}creategraph(node,60); /* 建立图形*/printf("图形的邻接链表内容:\n");for (i=1;i<=25;i++){ if(i%3==0)printf("\n");printf("顶点%d=>",head[i].vertex); /* 顶点值*/ptr=head[i].nextnode; /* 顶点位置*/while(ptr!=NULL) /* 遍历至链表尾*/{printf("%d ",ptr->vertex); /* 印出顶点内容*/ptr=ptr->nextnode; /* 下一个顶点*/}}printf("\n\n");printf("请选择你需要的操作\n");printf("1、图形的广度优先遍历请输入:'g'或'G'\n"); printf("2、图形的深度优先遍历请输入:'s'或'S'\n");c=getch();switch(c){case'g':case'G':printf("\n请你输入你需要的起始顶点:\n");scanf("%d",&i);///clrscr();printf("\n\n");printf("以下为各城市的代码:\n\n");printf("1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳; \n");printf("6:大连; 7:长春; 8:哈尔滨; 9:西宁; 10:兰州;\n");printf("11:西安; 12:郑州; 13:徐州; 14:成都; 15:武汉; \n");printf("16:上海; 17:昆明; 18:贵阳; 19:株州; 20:南昌;\n");printf("21:福州; 22:南宁; 23:柳州; 24:广州; 25:深圳.\n");printf("图形的广度优先遍历的顶点内容:\n");bfs(i); /* 印出遍历过程*/printf("\n"); /* 换行*/break;case's':case'S':printf("\n请输入你需要的起始顶点:\n");scanf("%d",&i);//clrscr();printf("\n\n");printf("以下为各城市的代码:\n\n");printf("1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳; \n");printf("6:大连; 7:长春; 8:哈尔滨; 9:西宁; 10:兰州;\n");printf("11:西安; 12:郑州; 13:徐州; 14:成都; 15:武汉; \n");printf("16:上海; 17:昆明; 18:贵阳; 19:株州; 20:南昌;\n");printf("21:福州; 22:南宁; 23:柳州; 24:广州; 25:深圳.\n");printf("图形的深度优先遍历的顶点内容:\n");dfs(i); /* 印出遍历过程*/printf("\n"); /* 换行*/break;}printf("\n请问你是否要继续:y/n");a=getch();if(a!='y'&&'Y')exit(0);}}四．调试分析1、本程序以邻接多重表为存储结构。

图的遍历演示一、需求分析1. 以邻接多重表为存储结构；2. 实现连通和非连通的无向图的深度优先和广度优先遍历；3. 要求利用栈实现无向图的广度和深度优先遍历；4. 以用户指定的节点为起点，分别输出每种遍历下的节点访问序列和生成树的边表；5. 用凹入表打印生成树；6. 求出从一个节点到另一个节点，但不经过另外一个指定节点的所有简单路径。

二、概要设计ADT Queue {数据对象：D={ai|ai属于Elemset，i=1，2，……，n，n>=0}数据关系：R1={<ai-a,ai>ai-1属于D，i=1,2,…,n}约定ai为端为队列头，an为队列尾基本操作：InitQueue（&Q）操作结果：构造一个空队列QDestroyQueue（&Q）初始条件：队列Q已存在操作结果：队列Q被销毁，不再存在ClearQueue（&Q）初始条件：队列Q已存在操作结果：将Q清为空队列QueueEmpty(Q)初始条件：队列Q已存在操作结果：若Q为空队列，则返回TRUE，否则FALSEQueueLength（Q）初始条件：队列Q已存在操作结果：返回Q的元素个数，即队列的长度GetHead（Q，&e）初始条件：Q为非空队列操作结果：用e返回Q的队头元素EnQueue（&Q,e）初始条件：队列Q已存在操作结果：插入元素e为Q的新的队尾元素DeQueue（&Q，&e）初始条件：Q为非空队列操作结果：删除Q的队头元素，并用e返回其值三、详细设计1、顶点,边和图类型#define MAX_INFO 10 /* 相关信息字符串的最大长度+1 */#define MAX_VERTEX_NUM 20 /* 图中顶点数的最大值*/typedef char InfoType; /*相关信息类型*/typedef char VertexType; /* 字符类型 */typedef enum{unvisited,visited}VisitIf;typedef struct EBox{VisitIf mark; /* 访问标记 */int ivex,jvex; /* 该边依附的两个顶点的位置 */struct EBox *ilink,*jlink; /* 分别指向依附这两个顶点的下一条边 */ InfoType *info; /* 该边信息指针 */}EBox;typedef struct{VertexType data;EBox *firstedge; /* 指向第一条依附该顶点的边 */}VexBox;typedef struct{VexBox adjmulist[MAX_VERTEX_NUM];int vexnum,edgenum; /* 无向图的当前顶点数和边数 */}AMLGraph;2. 其它部分代码void BFSTraverse(AMLGraph G,VertexType start,int(*Visit)(VertexType)) { /*从start顶点起,广度优先遍历图G*/for(v=0;v<G.vexnum;v++)Visited[v]=0; /* 置初值 */InitQueue(Q);z=LocateVex(G,start); /*先确定起点start在无向图中的位置*/for(v=0;v<G.vexnum;v++)if(!Visited[(v+z)%G.vexnum]) /* v尚未访问 */{Visited[(v+z)%G.vexnum]=1; /* 设置访问标志为TRUE(已访问) */ Visit(G.adjmulist[(v+z)%G.vexnum].data);EnQueue(Q,(v+z)%G.vexnum);while(!QueueEmpty(Q)) /* 队列不空 */{DeQueue(Q,u);for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data)) if(!Visited[w]){Visited[w]=1;Visit(G.adjmulist[w].data);EnQueue(Q,w);}}}DestroyQueue(Q); /*销毁队列,释放其占用空间*/}3. 队列的基本操作：Status InitQueue(LinkQueue &Q)；//构造一个空队列Q。

数据结构课程设计--图的遍历内蒙古科技大学本科生课程设计论文题目：图的遍历2013年07月05日内蒙古科技大学课程设计任务书目录第一章图的遍历原理51.1总述61.2深度优先遍历61.3广度优先遍历6第二章需求分析7第三章总体设计 (7)3.1程序设计思路 (7)3.2 功能视图 (8)第四章类的设计 (8)4.1 GraphUDN类的设计 (9)4.2 Queue类的设计 (10)第五章详细设计 (10)5.1 工程视图和类视图 (10)5.2 主要算法的流程图 (11)5.2.1 主函数的流程图 (11)5.2.2 深搜流程图 (12)5.2.3 广搜流程图 (13)第六章测试 (14)6.1 菜单界面 (15)6.2 创建无向网 (15)6.3 输出图 (16)6.4 输出顶点V的第一个邻接点 (16)6.5 输出顶点V的下一个邻接点 (17)6.6 深搜 (17)6.7 广搜 (18)第七章总结 (18)附录：程序代码 (20)参考文献 (29)第一章图的遍历原理1.1总述图的遍历：从图中某一顶点出发访遍图中其余顶点，且使得每一个顶点仅被访问一次。

这一过程就叫做图的遍历。

1.2深度优先遍历深度优先遍历类似于树的先根遍历，是树的先根遍历的推广。

假如初始状态是图中所有顶点未曾被访问，则深度优先遍历可从图中某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直到图中所有和V有路径相通的顶点都被访问到；若图中此时尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。

以图1.1为例，假如从顶点V1出发进行搜索，在访问了顶点V1之后，选择邻接点V2。

因为V2未曾访问，则从V2出发进行搜索。

以此类推，接着从V4，V8，V5出发进行搜索。

在访问了V5之后，由于V5的邻接点都已被访问，则搜索回到V8。

由于同样的理由，搜索回到V4，V2直到V1，此时由于V1的另一个邻接点未被访问，则搜索又从V1到V3，再继续进行下去。

inputt.close();
}
}
三、实验结果:
1.输入图
2. 遍历图：（先深度，后广度）
四、结果分析:
数据结构顾名思义讲求的是一种存储结构，一路走来先后学习了表、树，最后学习的是图，对于每种存储结构学习之初都会学习一些基本操作，而操作之中又以创建和遍历为最基本的操作，只有熟练掌握了以后才能对其他操作进行研究和学习。

在这次实验中，我也得到了很多收获，比如链表的应用，以前弄不太明白，通过这次实验，在链表这一方面我懂了很多，虽然还不能运用自如，但在这次实验中，对本学期所学习的内容也是一次巩固，让我加深了对学过知识的记忆。

总之，这次实验让我既发现了自身的很多不足，又增长了很多知识。

5.3 图的遍历和树的遍历类似，在此，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。

这一过程就叫做图的遍历(TraversingGraph)。

图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

然而，图的遍历要比树的遍历复杂得多。

因为图的任一顶点都可能和其余的顶点相邻接。

所以在访问了某个顶点之后，可能沿着某条路径搜索之后，又回到该顶点上。

[例如]图7.1(b)中的G2，由于图中存在回路，因此在访问了v1,v2,v3,v4之后，沿着边(v4 , v1)又可访问到v1。

为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。

为此，我们可以设一个辅助数组visited[0..n-1]，它的初始值置为“假”或者零，一旦访问了顶点vi，便置visited[i]为“真”或者为被访问时的次序号。

通常有两条遍历图的路径：深度优先搜索和广度优先搜索。

它们对无向图和有向图都适用。

5.3.1 深度优先搜索深度优先搜索(Depth-First Search)遍历类似于树的先根遍历，是树的先根遍历的推广。

其基本思想如下：假定以图中某个顶点vi为出发点，首先访问出发点，然后选择一个vi的未访问过的邻接点vj，以vj为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。

显然，这是一个递归的搜索过程。

现以图5-3-1中G为例说明深度优先搜索过程。

假定v0是出发点，首先访问v0。

因v0有两个邻接点v1、v2均末被访问过，可以选择v1作为新的出发点，访问v1之后，再找v1的末访问过的邻接点。

同v1邻接的有v0、v3和v4，其中v0已被访问过，而v3、v4尚未被访问过，可以选择v3作为新的出发点。

重复上述搜索过程，继续依次访问v7、v4 。

访问v4之后，由于与v4相邻的顶点均已被访问过，搜索退回到v7。

由于v7、v3和v1都是没有末被访问的邻接点，所以搜索过程连续地从v7退回到v3，再退回v1，最后退回到v0。