1.前言

深度优先搜索（缩写DFS）有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。

你可以跳过第二节先看第三节，:)

2.深度优先搜索VS广度优先搜索

还是引用上篇文章的样例图，起点仍然是V0，我们修改一下题目意思，只需要让你找出一条V0到V6的道路，而无需最短路。

图2-1 寻找V0到V6的一条路（无需最短路径）

假设按照以下的顺序来搜索：

1.V0->V1->V4，此时到底尽头，仍然到不了V6，于是原路返回到V1去搜索其他路径；

2.返回到V1后既搜索V2，于是搜索路径是V0->V1->V2->V6,，找到目标节点，返回有解。

这样搜索只是2步就到达了，但是如果用BFS的话就需要多几步。 [Read more...]

1.前言

广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。

一般可以用它做什么呢？一个最直观经典的例子就是走迷宫，我们从起点开始，找出到终点的最短路程，很多最短路径算法就是基于广度优先的思想成立的。

算法导论里边会给出不少严格的证明，我想尽量写得通俗一点，因此采用一些直观的讲法来伪装成证明，关键的point能够帮你get到就好。

2.图的概念

刚刚说的广度优先搜索是连通图的一种遍历策略，那就有必要将图先简单解释一下。

图2-1 连通图示例图

如图2-1所示，这就是我们所说的连通图，这里展示的是一个无向图，连通即每2个点都有至少一条路径相连，例如V0到V4的路径就是V0->V1->V4。

一般我们把顶点用V缩写，把边用E缩写。 [Read more...]