9.5.3　图的遍历

9.5.3　图的遍历

从图的某个顶点出发，遍历图中其余顶点，且使每个顶点仅被访问一次，这个过程叫做图的遍历（Traversing Graph）。对于图的遍历通常有两种方法：深度优先遍历和广度优先遍历。

1.深度优先遍历

深度优先遍历（Depth First Search，简称DFS），也成为深度优先搜索。

遍历思想：基本思想：首先从图中某个顶点V0出发，访问此顶点，然后依次从V相邻的顶点出发深度优先遍历，直至图中所有与v路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中选一个顶点作为起始点，重复上述过程，直到所有的顶点都被访问。

深度优先遍历用递归实现比较简单，只需用一个递归方法来遍历所有顶点，在访问某一个顶点时：

·将它标为已访问；

·递归的访问它的所有未被标记过的邻接点。

深度优先遍历的过程，如图9-37所示：

2.广度优先遍历

广度优先遍历（Breadth First Search，简称BFS），又称为广度优先搜索

遍历思想：首先，从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。

广度优先遍历的过程，如图9-38所示：