6.3 图 的 遍 历

所谓“图的遍历”，即是指从图的某一个顶点出发访问图中的所有顶点，且每个顶点只被访问一次的这样一个过程。

按图中结点的访问顺序，图的遍历分两种：一种深度优先遍历，另一种是广度优先遍历。

6.3.1 图的深度优先搜索

深度优先搜索(Depth_First Search)是指按照深度方向搜索，它类似于树的先根遍历。

深度优先搜索的基本思想是：

⑴ 从图中某个顶点vi出发，首先访问vi 。

⑵ 找出顶点vi的第一个未被访问的邻接点v j，然后访问顶点v j。找出顶点v j的第一个未被访问的邻接点vj1，……,重复本步骤，直到顶点v j1的所有的邻接点都被访问为止。          

6.3.2、广度优先搜索遍历图

从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。

 遍历应用举例

1. 求一条从顶点 i 到顶点 s  的简单路径

2. 求两个顶点之间的一条路径长度最短的路径