算法比较：深度优先搜索 vs 广度优先搜索

一、概述

A. 问题背景

深度优先搜索和广度优先搜索是两种搜索算法，在图或树中查找特定节点或路径的过程中经常使用。

B. 问题描述

在一个图或树中，查找某个节点或路径。

C. 算法思路

深度优先搜索：从开始节点出发，一直向其相邻未访问过的节点前进，直到找到目标节点或已经完全探索整个图或树。

广度优先搜索：从开始节点出发，首先访问其相邻节点，然后依次访问它们的相邻节点，直到找到目标节点或已经完全探索整个图或树。

二、深度优先搜索

A. 深度优先搜索原理

深度优先搜索从某个节点（通常是根节点）开始遍历图或树，在搜索时，尽可能深地访问每个节点，直到无法继续或找到目标节点为止。

B. 深度优先搜索实现

可以使用递归实现深度优先搜索。 也可以使用栈模拟递归过程来实现非递归的深度优先搜索。 JAVA代码：

递归实现：

public void dfs(Node node, boolean[] visited) {
    visited[node.val] = true;
    System.out.println(node.val);
    for (Node n : node.next) {
        if (!visited[n.val]) {
            dfs(n, visited);
        }
    }
}

非递归实现：

public void dfs(Node node, boolean[] visited) {
    Stack<Node> stack = new Stack<>();
    stack.push(node);

    while (!stack.empty()) {
        Node curr = stack.pop();
        visited[curr.val] = true;
        System.out.println(curr.val);

        for (Node n : curr.next) {
            if (!visited[n.val]) {
                stack.push(n);
            }
        }
    }
}

C. 深度优先搜索优缺点

优点：

• 实现简单明了，易于理解和实现。
• 占用的空间较少，当找到目标节点时，就可以停止搜索。

缺点：

• 可能会陷入死循环，需要避免重复访问节点。

三、广度优先搜索

A. 广度优先搜索原理

广度优先搜索从某个节点开始遍历图或树，在搜索时，尽可能宽地访问每个节点，即先访问与开始节点相邻的所有节点，然后依次访问第二层相邻节点，直到找到目标节点为止。

B. 广度优先搜索实现

可以使用队列实现广度优先搜索。 JAVA代码：

public void bfs(Node node, boolean[] visited) {
    Queue<Node> queue = new LinkedList<>();
    queue.offer(node);

    while (!queue.isEmpty()) {
        Node curr = queue.poll();
        visited[curr.val] = true;
        System.out.println(curr.val);

        for (Node n : curr.next) {
            if (!visited[n.val]) {
                queue.offer(n);
            }
        }
    }
}

C. 广度优先搜索优缺点

优点：

• 可以找到最短路径（路径上所有节点数量最少），因为搜索顺序是逐层依次进行的。

缺点：

• 实现相对较复杂，需要使用队列进行实现。
• 占用的空间较多，需要一次性存储所有等待访问的节点。

四、比较深度优先搜索和广度优先搜索

A. 时间复杂度分析

在最坏情况下，在n个节点的图或树中找到特定节点或路径的时间复杂度，深度优先搜索为O(n)，广度优先搜索为O(n^2)。

B. 空间复杂度分析

在最坏情况下，在n个节点的图或树中找到特定节点或路径的空间复杂度，深度优先搜索为O(h)，其中h为最大深度；广度优先搜索为O(n)，需要存储每层节点。

C. 应用场景比较

深度优先搜索适合用于查找目标节点深度较大的图或树，或者需要遍历整个图或树的情况。广度优先搜索适合用于查找目标节点深度较小的图或树，或者需要找到最短路径的情况。

五、算法优化

A. 减少空间复杂度

可以使用双向广度优先搜索来减少空间复杂度，它在开始节点和目标节点分别进行广度优先搜索，直到发现两边都访问了某个节点，此时可以得出最短路径。

B. 优化代码实现

可以使用位运算来减少代码实现中的比较操作，提高代码执行效率。例如，使用按位与运算代替布尔值相乘运算。

六、扩展点

A. 二叉树遍历方式

在二叉树中，有三种遍历方式：先序遍历、中序遍历、后序遍历。先序遍历是指先访问根节点，然后依次访问左子树和右子树；中序遍历是指先访问左子树，然后访问根节点，最后访问右子树；后序遍历是指先访问左子树，然后访问右子树，最后访问根节点。

B. 二叉树节点值的计算方式

在二叉树中，每个节点都有一个值，可以通过不同的方式计算节点值。例如，可以计算二叉树叶节点的总和，或者二叉树中每个节点与根节点的差值的绝对值的总和。

七、总结

深度优先搜索和广度优先搜索都是常用的图或树搜索算法，它们分别适用于不同的特定情况。在实际应用中，可以根据具体问题的特点选用适合的算法。除此之外，还可以通过算法优化来提高代码执行效率和减少空间复杂度。