算法导论--广度优先搜索和深度优先搜索

广度优先搜索

在给定图G=(V,E)和一个特定的源顶点s的情况下，广度优先搜索系统地探索G中的边，以期“发现”可从s 到达的所有顶点，并计算s 到所有这些可达顶点之间的距离（即最少的边数）。该搜索算法同时还能生成一棵根为s、且包括所有s 的可达顶点的广度优先树。对从s 可达的任意顶点v，广度优先树中从s 到v 的路径对应于图G中从s 到v 的一条最短路径，即包含最少边数的路径。该算法对有向图和无向图同样适用。

 具体算法详情见 算法—12.广度优先搜索

算法分析：

现在分析一下该算法在输入图G=(V,E)上的运行时间。此处采用聚集分析技术，在初始化后，再没有任何顶点被置为白色。因此，第13行中的测试保证了每个顶点至多只进入队列一次，因而至多只从队列中出来一次。入队和出队操作需要O(1)的时间，因此队列操作所需的全部时间为O(V)。因为只有当每个顶点将出队时，才会扫描其邻接表，因而每个顶点的邻接表至多被扫描一次。由于所有邻接表的长度和为O(E)，故扫描所有邻接表所花费的全部时间为O(E)。初始化操作的开销为O(V)，于是，过程BFS的总运行时间为O(V+E)。由此可见，广度优先搜索的运行时间是图G的邻接表大小的一个线性函数。

深度优先搜索

正如“深度优先搜索”这一名称所暗示的那样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续探测下去。当顶点v的所有边都已被探寻过后，搜索将回溯到发现顶点v 有起始点的那些边。这一过程一直进行到已发现从源顶点可达的所有顶点时为止。如果还存在未被发现的顶点，则选择其中一个作为源顶点，并重复以上过程。整个过程反复进行，直到所有的顶点都已被发现时为止。

算法—11.深度优先搜索

算法分析：

DFS中第1~3行和第5~7行中的循环占用的时间为O(V)，这不包括调用DFS-VISIT的时间。就像我们在处理广度优先搜索时一样，采用聚集分析。对于每个顶点vΕV，过程DFS-VISIT仅被调用一次，因为只有对白色顶点才会调用该过程，且该过程所做的第一件事就是将顶点置为灰色。在DFS-VISIT(v)的一次执行过程中，第4~7行中的循环被执行了| Adj[v] |次。因为有

故执行过程DFS-VISIT中第4~7行的总代价为O(E)。因此，DFS的运行时间为O(V+E)。