|
图的遍历概念 图的遍历 和树的遍历类似图的遍历也是从某个顶点出发沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问它是许多图的算 法的基础 深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法它们对无向图和有向图均适用 注意 以下假定遍历过程中访问顶点的操作是简单地输出顶点 布尔向量visited[n]的设置 图中任一顶点都可能和其它顶点相邻接在访问了某顶点之后又可能顺着某条回路又回到了该顶点为了避免重复访问同一个 顶点必须记住每个已访问的顶点为此可设一布尔向量visited[n]其初值为假一旦访问了顶点V i 之后便将 visited[i]置为真 深度优先遍历(DepthFirst Traversal) 图的深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过在G中任选一顶点v为初始出发点(源点)则深度优先遍历可定义如下首先访问出 发点v并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w若w未曾访问过则以w为新的出发点继续进行深度优先遍历 直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止若此时图中仍有未访问的顶点则另选一个 尚未访问的顶点作为新的源点重复上述过程直至图中所有顶点均已被访问为止 图的深度优先遍历类似于树的前序遍历采用的搜索方法的特点是尽可能先对纵深方向进行搜索这种搜索方法称为深度优先搜 索(DepthFirst Search)相应地用此方法遍历图就很自然地称之为图的深度优先遍历 深度优先搜索的过程 设x是当前被访问顶点在对x做过访问标记后选择一条从x出发的未检测过的边(xy)若发现顶点y已访问过则重新选择另 一条从x出发的未检测过的边否则沿边(xy)到达未曾访问过的y对y访问并将其标记为已访问过;然后从y开始搜索直到搜索 完从y出发的所有路径即访问完所有从y出发可达的顶点之后才回溯到顶点x并且再选择一条从x出发的未检测过的边上述过程 直至从x出发的所有边都已检测过为止此时若x不是源点则回溯到在x之前被访问过的顶点;否则图中所有和源点有路径相通的 顶点(即从源点可达的所有顶点)都已被访问过若图G是连通图则遍历过程结束否则继续选择一个尚未被访问的顶点作为新源点 进行新的搜索过程 |
