一般性图搜索算法

算法"/>

一般性图搜索算法

图搜索算法是一类重要的基于图的算法。本文 给出一般化的图搜索算法的框架。

图搜索算法的核心任务是从一个初始节点s，尽可能多的找到其他的点v。注意通常对于一个n个点，m条边的图，我们希望搜索算法的复杂度为，换言之，我们希望每一个点与边都不重复搜索两次。

老规矩，图搜索算法的一般步骤如下：

1. 初始化开始点s为explored，其他点为unexplored

2. 循环直到找不到未被搜索的点

3.         选择边(u,v),其中u explored，v unexplored

4.         标记节点v explored

Lemma 1： 如果搜索算法终止时，节点v explored，那么图中存在一条路径从s 到v。

Proof: 从图搜索算法的循环步骤可以看出，s 与 v最后都explored，显然s存在一条路径到v点。

反之，我们假设算法结束时v explored，但是不存在s到v的路径。

显然存在一个中间节点w，即s - w -v，w并没有explored。但是从图搜索算法的步骤可以看到，每一个经历过的点都会被标记为explored，因此矛盾。证明完毕。

常见的图搜索算法有 广度优先(BFS)和深度优先(DFS), 不同的算法有不同的用途。下一篇博客我们继续讲 BFS和DFS算法以及他们的应用