Swift 中的 DFS 与 BFS 算法

最近在开发过程中需要实现树形结构的选中状态联动（包括全选、部分选和未选状态），这里使用到了树的遍历算法。深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的图/树遍历算法，它们的主要区别在于访问节点的顺序：

深度优先搜索（DFS）：优先深入一条路径，直到访问到底再回溯。
广度优先搜索 (BFS)：逐层访问节点，优先处理同一层的所有节点。

代码实现

首先，我们定义一个节点的泛型协议：

protocol TreeNode: Identifiable {
    var id: String { get }
    var label: String { get }
    var children: [T]? { get }
    var parent: T? { get set }
}

深度优先搜索 (DFS)

深度优先遍历通常包括三种基本访问顺序：

前序遍历：遵循"根 → 左子树 → 右子树"的顺序，优先访问当前节点，再处理子树。此方法常用于复制树结构，其遍历序列的首元素必为根节点。
中序遍历：按"左子树 → 根 → 右子树"的顺序访问，适用于二叉搜索树生成升序序列。中序遍历序列可结合前序或后序序列唯一确定二叉树的结构。
后序遍历：采用"左子树 → 右子树 → 根"的顺序，适用于需要优先处理子节点的场景，如表示式求值等。

DFS 算法利用栈（Stack）的相关概念：

递归：隐式使用调用栈。
非递归：显式用数组模拟栈（使用 append 和 removeLast）。

以下是前序遍历的非递归与递归实现的 DFS 代码示例：

非递归实现

func dfs<T: TreeNode>(_ root: T) -> Set<T> {
    var stack: [T] = [root]
    var result = Set<T>()
    while !stack.isEmpty {
        let current = stack.removeLast()
        
        // 防止重复访问和循环
        if result.contains(current) { continue }
        result.insert(current)
        
        // 逆序压栈确保顺序一致
        for child in current.children?.reversed() ?? [] {
            if var item = child as? T {
                item.parent = current
                stack.append(item)
            }
        }
    }
    return result
}

递归实现

func dfsRecursive<T: TreeNode>(_ root: T, visited: inout Set<T>) {
    guard !visited.contains(root) else { return }
    visited.insert(root)
    for child in root.children ?? [] {
        if var item = child as? T {
            item.parent = root
            dfsRecursive(item, visited: &visited)
        }
    }
}

广度优先搜索 (BFS)

BFS 算法利用队列（Queue）的相关概念。可以使用数组模拟队列（使用 append 和 removeFirst），但需要注意 removeFirst() 在处理大型数据集时的性能问题。为此，可以使用两个数组交替存储层级，从而避免 removeFirst() 的 O(n) 开销，以下是优化后的版本：

func bfs<T: TreeNode>(_ root: T) -> Set<T> {
    var currentLevel: [T] = [root]
    var result = Set<T>()
    
    while !currentLevel.isEmpty {
        // 使用两个数组交替存储层级，避免 removeFirst() 的 O(n) 开销
        var nextLevel: [T] = []
        for node in currentLevel {
            result.insert(node)
            for child in node.children ?? [] {
                if var item = child as? T, !result.contains(item) {
                    item.parent = node
                    nextLevel.append(item)
                }
            }
        }
        currentLevel = nextLevel
    }
    return result
}

总结

DFS（深度优先搜索）和 BFS（广度优先搜索）不仅是遍历树的标准算法，更是遍历图（Graph）的基础和核心算法。树可以视作一种特殊类型的图（无环、连通的有向图或更严格的根树定义），因此针对树的遍历算法同样可以推广到更一般的图结构上。在进行图遍历以计算最短路径或最少步数时，建议优先选择广度优先搜索 (BFS)；而在需要枚举所有解或进行回溯时，则应首选深度优先搜索 (DFS)。同时，由于图的结构更为灵活，节点之间可能存在多条边，且没有层次关系，一个节点可以有多个父节点和子节点，因此之前定义的节点泛型协议需要进行相应修改。

Shaula Blog