【问题描述】
从图中某个顶点出发访问图中所有顶点,且使得每一顶点仅被访问一次,这个过程称为图的遍历。图的遍历是从图中某个顶点出发,沿着某条搜索路径对图中其余每个顶点进行访问, 并且使图中的每个顶点仅被访问一次的过程。
图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。试编写一个程序,完成对图的遍历。
【基本要求】
1.以邻接矩阵为存储结构,实现无向图的深度优先遍历和广度优先遍历。
2.分别输出每种遍历下的结点访问序列.从图中某个顶点出发,沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。
【图的遍历介绍】
一、基本概念
图的遍历: 图中某个顶点出发访问图中所有顶点,且使得每一顶点仅被访问一次,这个过程称为图的遍历。图的遍历是从图中某个顶点出发,沿着某条搜索路径对图中其余每个顶点进行访问, 并且使图中的每个顶点仅被访问一次的过程。
图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。
二、 分类
按照搜索途径的不同,图的遍历可分为:深度优先遍历(Depth-First Traverse)和广度优先遍历(Breadth-First Traverse)两大类。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。
深度优先遍历 (Depth-First Traverse)
特点:尽可能先对纵深方向的顶点进行访问
1.深度优先遍历的递归定义
假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。
2. 深度优先搜索的过程
a 基本思想:
首先访问图中某一个指定的出发点Vi;
然后任选一个与顶点Vi相邻的未被访问过的顶点Vj;
以Vj为新的出发点继续进行深度优先搜索,直至图中所有顶点均被访问过。
b具体过程:
设x是当前被访问顶点,在对x做过访问标记后,选择一条从x出发的未检测过的边(x,y)。若发现顶点y已访问过,则重新选择另一条从x出发的未检测过的边,否则沿边(x,y)到达未曾访问过的y,对y访问并将其标记为已访问过;然后从y开始搜索,直到搜索完从y出发的所有路径,即访问完所有从y出发可达的顶点之后,才回溯到顶点x,并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时,若x不是源点,则回溯到在x之前被访问过的顶点;否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过,若图G是连通图,则遍历过程结束,否则继续选择一个尚未被访问的顶点作为新源点,进行新的搜索过程。
1