很基础的 BFS 题目.
BFS 和 DFS 是相对应的两种算法. 其区别在于对于新发现的可能性, BFS 将其放入队列末尾, 稍后进行探索, 而 DFS 立即探索这种新情况, 等探索完之后再回到之前的状态继续枚举.
对于这道题目来说, 具体来讲, 状况可以用 (位置, 距离, 颜色) 这么一个 tuple 来表示. 最开始的时候, 有 (0, 0, blue) 和 (0, 0, red) 这两种情况. 假设 0到1 有一条蓝边, 0到2 有一条红边, 那么新的情况是 (1, 1, red) 和 (2, 1, blue).
如果我们使用 DFS, 那么当新发现 (1, 1, red) 这个状态的时候, 我会立即以 (1, 1, red) 为起点, 继续探索 1 号点的邻居, 比如找到了 (3, 2, blue) … 直到找完所有通过 (1, 1, red) 可以达到的状态之后, 再继续以 (2, 1, blue) 为基础进行枚举.
而 BFS 不同. BFS 会将 (3, 2, blue) 放到一个队列 q 的 末尾, 然后假装什么都没发生过, 继续从 q 的 队首 拿一个状态出来, 枚举它的邻居, 以此往复.
这样做的好处是, BFS 队列 q 中的所有状态一定是按距离升序排列的. 一但某个 (顶点, 颜色) 对出现在 q 中, 那么它一定是从起点到该顶点且下一步是该颜色的最短距离. 所以如果后面再遇到该 (顶点, 颜色) 对, 就可以不进行枚举了. 从而节省极大的时间.
下面是一个例子
如果使用 DFS, 那么一个搜索顺序如下:
(0, 0, blue)
(1, 1, red)
(3, 2, blue)
回到(1, 1, red)
(4, 2, blue)
回到(1, 1, red)
回到(0, 0, blue)
继续 (0, 0, red)
(2, 1, blue)
(4, 2, red)
回到(2, 1, blue)
(5, 2, red)
回到(2, 1, blue)
回到(0, 0, red)
结束
如果使用 BFS, 那么一个搜索顺序如下:
(0, 0, blue) # 使 (1, 1, red) 加入到队尾
(0, 0, red) # 使 (2, 1, blue) 加入到队尾
(1, 1, red) # 使 (3, 2, blue), (3, 4, blue) 加入到队尾
(2, 1, blue) # 使 (4, 2, red), (5, 2, red) 加入到队尾
(3, 2, blue) # 没新的状态可加了 下同
(3, 4, blue)
(4, 2, red)
(5, 2, red)
结束
下面是代码链接
在代码中, 我使用节点编号 k 和 k+n 分别代表下一步该走蓝边还是红边.