Depth First Search vs Width First Search in Python¶

Keywords: DFS, WFS, 深度优先, 广度优先

深度优先 (DFS) 和广度优先 (WFS) 是算法中两种常用的搜索算法. 在很多场景都有着广泛应用:

Serialization (序列化):

把一个复杂数据结构序列化, 数据结构的 attribute 有可能是另一个复杂的数据结构. 所以一个序列化算法通常需要用 DFS 搜索到最终叶节点, 从叶节点到根节点一直回溯序列化回来, 才算是完成了一个完整的序列化.

Prefix Tree Search:

给定一个字符串, 从一堆字符串中找到有着最长前缀的字符串. 比如给定一个文件路径和一堆文件夹路径, 这个文件到底是属于哪个文件夹的呢? 这个算法就要用到 WFS 搜索.

DFS, WFS 在 Python 中的主要实现方法是递归.

这里有个 DFS 和 WFS 的简单实现:

# -*- coding: utf-8 -*-

"""
A simple implementation of depth first search / width first search::

    t
    |--- t1
        |--- t11
        |--- t12
    |--- t2
        |--- t21
        |--- t22

    # depth first search result
    t11, t12, t1, t21, t22, t2, t

    # width first search result
    t, t1, t2, t11, t12, t21, t22
"""

from typing import List


class Node:
    def __init__(self, name: str, children: List['Node'] = None):
        self.name = name
        if children is None:
            children = list()
        self.children = children

    def __repr__(self):
        return f"'{self.name}'"


t11 = Node("t11")
t12 = Node("t12")
t21 = Node("t21")
t22 = Node("t22")
t1 = Node("t1", [t11, t12])
t2 = Node("t2", [t21, t22])
t = Node("t", [t1, t2])


def depth_first_search(node: Node):
    for n in node.children:
        yield from depth_first_search(n)
    yield node


def width_first_search(node: Node, _is_root=True):
    if _is_root:
        yield node
    for n in node.children:
        yield n
    for n in node.children:
        yield from width_first_search(n, _is_root=False)


print(list(depth_first_search(t)))  # ['t11', 't12', 't1', 't21', 't22', 't2', 't']
print(list(width_first_search(t)))  # ['t', 't1', 't2', 't11', 't12', 't21', 't22']