data structure

图的遍历是指从图中的某一顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图,所以树的遍历实际上也可视为一种特殊的图的遍历。图的遍历是图的一种最基本的操作,其他操作都建立在图的遍历操作基础之上。

图的遍历主要有两种算法:广度优先搜索和深度优先搜索。包括广度优先搜索和深度优先搜索在内的几乎所有图的搜索算法,都可以抽象为优先级搜索或最佳优先搜索。广度优先搜索会优先考虑最早被发现的顶点,也就是说离起点越近的顶点其优先级越高。深度优先搜索会优化考虑最后被发现的顶点。广度优先搜索算法在研究迷宫路径问题时被发现;深度优先搜索在人工智能方面得广泛应用。

1. 广度优先搜索

广度优先搜索(Breadth First Search,BFS)类似于二叉树的层序遍历算法,其基本思想是:首先访问起始顶点 v,接着由 v 出发,依次访问 v 的各个未访问过的邻接顶点 wi ,然后从 wi 开始访问未访问过的邻接结点,以此类推,直到图中所有顶点都被访问过为止。Dijkstra 单源最短路径算法和 Prim 最小生成树算法也应用了类似的思想。

广度优先算法是一种分层的查找过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况,因此它不是一个递归的算法。为了实现逐层的访问,算法必须借助一个辅助队列,以记忆正在访问的顶点的下一层顶点。

1.1 BFS 算法的性能分析

无论是邻接表还是邻接矩阵的存储方式,BFS 算法都需要借助一个辅助队列 Q,n 个顶点均需入队一次,在最坏的情况下,空间复杂度为 O(|V|)

采用邻接表存储方式时,每个顶点均需要搜索一次(或入队一次),故时间复杂度为 O(|V|) ,在搜索任一顶点的邻接点时,每条边至少访问一次,故时间复杂度为 O(|E|) ,算法总的时间复杂度为 O(|V|+|E|) 。采用邻接矩阵存储方式时,查找每个顶点的邻接点所需时间为 O(V) ,故算法总的时间复杂度为 O(|V|^2)

1.2 BFS 算法求解单源最短路径问题

若图 G=(V,E) 为非带权图,定义从顶点 u 到顶点 v 的最短路径 d(u,v) 为从 u 到 v 的任何路径中最少的边数;若从 u 到 v 没有通路,则 d(u,v) = ∞ 。

使用 BFS ,我们可以求解一个满足上述定义的非带权图的单源最短路径问题,这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。

1.3 广度优先生成树

在广度遍历的过程中,我们可以得到一棵遍历树,称为广度优先生成树。需要注意的是,一给定图的邻接矩阵存储表示是唯一的,故其广度优先生成树也是唯一的,但由于邻接表存储表示不唯一,故其广度优先生成树也是不唯一的。

2. 深度优先搜索

与广度优先搜索不同,深度优先搜索(Depth First Search,DFS)类似于树的先序遍历。如其名称所暗含的意思一样,这种搜索算法所遵循的搜索策略是尽可能 “深” 地搜索一个图。它的基本思想如下 :首先访问图中某一起始顶点 v,然后由 v 出发,访问与 v 邻接且未被访问的任一顶点 w1 ,再访问与 w1 邻接且未被访问的任一顶点 w2 ,重复上述过程。当不能再继续向下访问时,依次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,直到图中所有顶点均被访问过为止。

注意 :图的邻接矩阵表示是唯一的,但对于邻接表来说,若边是输入次序不同,生成树的邻接表也不同。因此,对于同样一个图,基于邻接矩阵的遍历所得到的 DFS 序列和 BFS 序列是唯一的,基于邻接表的遍历所得到的 DFS 序列和 BFS 序列是不唯一的。

2.1 DFS 算法的性能分析

DFS 算法是一个递归算法,需要借助一个递归工作栈,故其空间复杂度为 O(|V|)

遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所用的存储结构。以邻接矩阵表示时,查找所有顶点的邻接点所需的时间为 O(|V|) ,故总的时间复杂度为 O(|V|^2) 。以邻接表表示时,查找所有顶点的邻接点所需的时间为 O(|E|) ,访问顶点所需的时间为 O(|v|) ,此时,总的时间复杂度为 O(|V|+|E|)

2.2 深度优先的生成树和生成森林

与广度优先搜索一样,深度优先搜索也会产生一棵深度优先生成树。当然,这是有条件的,即对连通图调用 DFS 才能产生深度优先生成树,否则产生的将是深度优先生成森林。与 BFS 类似,基于邻接表存储的深度优先生成树是不唯一的。

3. 图的遍历与图的连通性

图的遍历算法可以用来判断图的连通性。

对于无向图来说,若无向图是连通的,则从任一结点出发,仅需一次遍历就能够访问图中的所有顶点;若无向图是非连通的,则从某一个顶点出发,一次遍历只能访问到该顶点所在连通分量的所有顶点,而对于图中其他连通分量的顶点,则无法通过这次遍历访问。对于有向图来说,若从初始点到图中的每一个顶点都有路径,则能够访问到图中的所有顶点,否则不同访问到所有顶点。

故在 BFSTraverse()DFSTraverse() 中添加了第二个 for 循环,再选取初始点,继续进行遍历,以防止一次无法遍历图的所有顶点。对于无向图,上述两个函数调用 BFS(G,i)DFS(G, i) 的次数等于该图的连通分量数;而对于有向图则不是这样,因为一个连通的有向图分为强连通的和非强连通的,它的连通子图也分为强连通分量和非强连通分量,非强连通分量一次调用 BFS(G, i)DFS(G, i) 无法访问到该连通分量的所有顶点 。