5.4 图的遍历★3◎3

5.4 图的遍历★3◎3

　　当我们从图的某一个顶点出发，依照某种规则访问图中的其他顶点，并要求所有的顶点被访问而且只被访问一次，这个过程就叫做图的遍历。
　　深度优先遍历和广度优先遍历是遍历图的两种最为常见和重要的规则，它们对无向图和有向图均适用。
　　1．访问判断向量
　　为了能够正确地描述顶点是否已经被访问，需要增加一个布尔向量visited[0．．n-1]，其元素与图的顶点一一对应，初值赋值为“假”（或0），代表该顶点尚未被访问。在图的访问过程中规定：
　　（1）每次只能访问向量中对应元素的值为“假”（或0）的顶点。
　　（2）每当顶点被访问后，都要设置其对应向量中的元素值为“真”（或1），代表该顶点已被访问。
　　以下是一个定义此布尔向量的例子：
　　
　　2．深度优先搜索
　　图的深度优先搜索（Depth-First Search，DFS）类似于树的先根遍历，是先根遍历的扩展，其基本搜索原则是尽可能先对纵深方向进行搜索。用深度优先搜索方法遍历到的顶点序列称为该图的深度优先遍历序列，或简称为DFS序列。
　　（1）图的深度优先搜索定义
　　初始时，图G的所有顶点均未被访问，任选一个顶点V为搜索的出发点，置顶点V为“已被访问”，再依次对所有与V相连且未被访问的顶点进行深度优先搜索，并设置所有被搜索到的顶点为“已被访问”，此时图中所有和顶点V有路径相通的顶点均将被访问。
　　如果图G中仍有未被访问的顶点，则另选一个尚未被访问的顶点作为新的搜索出发点，重复上述过程，直至图中所有顶点均已被访问。
　　（2）图的深度优先搜索递归算法
　　算法的步骤为：
　　①对顶点x置访问标识。
　　②查找与顶点x有边或弧相连接的顶点序列为Wi(1<i<D(x))，无向图中D(x)为顶点x的度，有向图中D(x)为顶点x的出度，当Wi非空时执行第③
　　步，否则执行第⑤步。
　　③依次在Wi中选择一个未被访问的顶点，对此顶点进行深度优先搜索。
　　④重复执行第③步，直到Wi中不存在未被访问的顶点为止。
　　⑤ 对x的深度优先搜索完成。
　　对整个图的深度优先搜索算法如下：
　　
　　其中，DFS是从顶点Vi开始的深度优先搜索，是算法的灵魂部分。
　　使用邻接矩阵存储法完成从顶点Vi开始的深度优先搜索：
　　
　　算法分析
　　当使用邻接矩阵存储时，查找顶点Vi的连接顶点过程需要查询n次，即调用一次DFS的时间复杂度是O(n)，而在整个图的深度优先遍历中，每个顶点都将深度搜索一次，故使用邻接矩阵存储法进行深度优先搜索的时间复杂度为
　　使用邻接表存储法，完成从顶点Vi开始的深度优先搜索：
　　
　　算法分析
　　当使用邻接表存储时，查找顶点Vi的连接顶点过程需要查询ei次（ei是与顶点Vi相连的边数），即调用一次DFS的时间复杂度是O(1+ei)，其中1代表搜索顶点Vi一次。而在整个图的深度优先遍历中，每个顶点都将深度搜索一次，故使用邻接表存储法进行深度优先搜索的时间复杂度为：
　　
　　（3）深度优先搜索非递归算法
　　可以通过栈来完成图的深度优先搜索，此时算法更改为：
　　①搜索起始点入栈。
　　②当栈不为空时，执行以下步骤，否则执行步骤⑦。
　　③栈顶元素x出栈。
　　④如果x已经被访问，则回到步骤②继续执行，否则访问顶点x。
　　⑤ 遍历顶点x的邻接表，遍历操作为：邻接表中的结点记载了从顶点x到另一顶点（假设为y）的一条边或弧，如果顶点y“未被访问”，则将顶点y入栈。
　　⑥ 回到步骤②继续执行。
　　⑦对顶点x的深度优先搜索完成。
　　例如，图5-8从V1开始深度优先搜索的流程如表5-3所示。

表5-3 图5-8深度优先搜索流程图

续表

　　注：① 虽然V2已经在栈中，但是由于“未被访问”，故仍然需要入栈。
　　　　② 虽然V5已经在栈中，但是由于“未被访问”，故仍然需要入栈。
　　　　③ V5已经在被访问，故出栈后不再处理。
　　　　④ V2已经在被访问，故出栈后不再处理。