BLOG
Enjoy when you can, and endure when you must.
MAR 31, 2016/数据结构
图的基础遍历:深度优先和广度优先

通常情况下,一个图结构的遍历过程主要包括:维护一个用来存放待探索节点的 to-do 列表(一种队列),并从中去除我们已访问过的节点。最初,该列表中只有遍历的起点,在之后的每一步,我们都会访问并去除其中一个节点,并将其邻居节点加入到该列表中。而在该列表中,项目的(调度)顺序则很大程度上决定了我们所实现的遍历类型。如采用了 LIFO 列(Stack 类型),那么执行的就是深度优先搜索(DFS);而要是采用的是 FIFO 队列,执行的就是广度优先搜索(BFS)。这就是本文的两位主人公。

 

深度优先搜索

深度优先搜索我们可以简单的理解为始终优先往最深处探寻,当无路可走的时候,才退而求其次。一个更专业的说法是:深度优先搜索总是对最近才发现的节点的出发边进行探索,直到该节点的所有出发便都被发现为止。一旦当前结点的所有出发边都被发现,搜索则“回溯”到其前驱结点,来搜索该前驱节点的出发边。该过程一直持续到从源节点可以达到的所有节点都被发现为止。如果还存在尚未发现的节点,则深度优先搜索将从这些未被发现的节点中任选一个作为新的源节点,斌重复同样的搜索过程。这样一直重复,直到图中所有的节点都被发现为止。

基于此和前一段落中对遍历过程的总结,我们可以尝试得到这样的遍历方法:

def dfs(graph, node):
    """
    深度优先搜索
    """

    # searched 用于存放已探索的节点
    # query_queue 是用来存放待探索节点的 to-do 列表,并将其模拟成 LIFO
    searched, query_queue = set(), []

    # 最初,to-do 列表中只有遍历的起点
    query_queue.append(node)

    while query_queue:
        # 总是从 to-do 列表的最后弹出一个待探索的节点
        q_node = query_queue.pop()

        if query_queue in searched:
            continue

        searched.add(q_node)

        for neighbor in graph[q_node]:
            # 将邻居节点推入 to-do 列表
            query_queue.append(neighbor)

        yield q_node

 

广度优先搜索

广度优先搜索是对图中的边进行系统性的探索来发现可以从源节点出发到达的所有节点。该算法能够计算从源节点到每个可到达的节点的最短距离(无权值)。其广度优先则体现在始终是对图进行逐层探索,当当前所在层探索完毕后才进入到邻居节点进一步探索。

广度优先搜索从实现上来看,与深度优先搜索的唯一区别就是将 LIFO 替换为 FIFO 即可。

from collections import deque


def bfs(graph, node):
    """
    广度优先搜索
    """

    # parents 记录所有可达节点与对应的父节点,这里是一个字典,我们将其 可达节点 作为 key,而将其 父节点 作为 value
    # query_queue 是用来存放待探索节点的 to-do 列表,这里是一个 FIFO
    parents, query_queue = {node: None}, deque([node])

    while query_queue:
        # 总是从 FIFO 的左侧弹出待探索的节点
        q_node = query_queue.popleft()

        for neighbor in graph[q_node]:
            if neighbor in parents:
                continue

            # 记录探索到的邻居节点及其父节点
            parents[neighbor] = q_node

            # 将其邻居节点推入 to-do 列表
            query_queue.append(neighbor)

    return parents

如需获取某个节点到源节点的路径,只需从该节点开始“往回倒”即可找到。

 

拓展阅读

《算法导论》(第三版)第 22 章

《Python 算法教程》

COMMENTS
17/09From flaneur

深搜的代码:
while query_queue:
# 总是从 to-do 列表的最后弹出一个待探索的节点
q_node = query_queue.pop()

if query_queue in searched: # 这里应该是q_node吧
continue

LEAVE COMMNT