4 图的走访 - BFS 篇

如果要好好地探索一张图，最经典的方法莫过於深度优先搜索(Depth First Search) 以及广度优先搜索(Breadth First Search)了！深度优先搜索 DFS 是利用堆叠的概念，如果有发现一条道路通往尚未探索过的点，那麽就先把这个点的状态暂时堆叠起来，先行探索下一个点，直到无路可进以後才回溯。广度优先搜索 BFS 则是预先勘查好所有与目前这个点相连的所有点，将之标记後放入一个待处理的伫列，然後从这个伫列逐一重复相同的探索动作。

这两种演算法有着非常非常多的应用，我们今天先来举几个简单的例子。
（备注：我们今天讨论的图，都是无向、无权重的图，是最单纯的那类图。）

4.1 寻找最短路线

想像一下我们有一些房间，而房间与房间之间有走廊连结着。

如果我们今天要从点A走到点B，这时候就可以从 A 开始利用广度优先搜索，逐步探查 A 走一步可以到的点、然後到走两步可以到的点、等等依此类推。如果我们将「探查谁从而发现谁」这样的关系描绘出来，不难发现这样会形成一个树状结构（我们通常称它为 BFS 搜索树）

不是重点的参考程序码(Python)：

from queue import Queue
import networkx as nx

def get_bfs_tree(G, start_node):
    """回传从 start_node 开始搜索的 BFS 搜索树、以及每个点的父节点。"""
    prev = dict()                 # prev 纪录每个点是谁走过来的。
    prev[start_node] = start_node # 做个标记，表示走过了。
    q = Queue()
    q.put(start_node)
    H = nx.Graph()
    while not q.empty():
        u = q.get()
        for v in G.neighbors(u):
            if v not in prev:
                H.add_edge(u, v)
                prev[v] = u
                q.put(v)
    return H, prev

4.2 保持双顶点连通分量的子图

接下来跟大家分享一个把 BFS 演算法反过来应用在图论中的有趣例子。
想像一下，如果这张图 G 代表一个网路。每一条边都代表连接两个节点的某条网路线，我们想要找出这个图的子图 H（也就是保留某些网路线），使得任两点之间仍然可以进行资料传输（可以是直接或间接的资料传输）。显然随便找一棵生成树就可以了，如果我们想要额外增加条件：如果某个节点坏掉了，在原本的图 G 上面仍然连通，在这个子图 H 上也必须要连通。

在这样的条件之下，我们说这个子图 H 是保有图 G 的双连通分量特性的！要怎麽实作呢？想必各位也已经猜到了，没错就是使用 BFS！如果我们对这张图 G 做两次 BFS（第二次的时候可能有些地方会断开，就对每个连通分量各自做一次 BFS 就行了），这些蒐集起来的边，可以经过神奇的数学证明，它满足我们想要的保持双顶点连通分量的条件！

4.X 冷笑话

为什麽把一张图烧掉以後，时间很快就过了呢？因为，这一切都太图燃了啊...