哇塞码农编程题系列 -- 搜索

更新于2024-11-05 08:00:005 分钟2 千字143362600

摘要

DFS与BFS

深度优先搜索（DFS）和广度优先搜索（BFS）是两种常见的图搜索算法，用于在图中查找特定节点或路径。它们在解决许多图问题时都非常有用，如路径查找、连通性检测、拓扑排序等。

深度优先搜索（DFS）：

工作原理：
- 从起始节点开始，尽可能深地探索每个分支，直到达到最深的节点，然后回溯到上一个节点，继续探索其他分支。
实现方式：
- 可以通过递归或使用栈来实现。
- 递归方式是最常见的实现方式，它自然地利用了函数调用栈来存储中间状态。
应用：
- 解决连通性问题，如图的连通性检测。
- 在迷宫问题中寻找通路。
- 解决图的拓扑排序问题。

广度优先搜索（BFS）：

工作原理：
- 从起始节点开始，先访问其所有的相邻节点，然后依次访问这些相邻节点的相邻节点，以此类推，直到找到目标节点或遍历完整个图。
实现方式：
- 使用队列来实现。
- 从起始节点开始，将其加入队列，然后不断从队列中取出节点，将其相邻节点加入队列。
应用：
- 解决最短路径问题，如在无权图中找到两个节点之间的最短路径。
- 查找图中的连通分量。
- 广度优先搜索也被用于处理树的层级遍历。

区别：

遍历顺序：
- DFS沿着图的深度遍历，BFS沿着图的广度遍历。
数据结构：
- DFS通常使用递归或栈来实现，而BFS通常使用队列来实现。
搜索策略：
- DFS更适合用于查找深度方面的问题，而BFS更适合用于查找广度方面的问题。
空间复杂度：
- 在某些情况下，DFS可能需要更少的空间，因为它通常只需要存储当前路径上的节点，而BFS需要存储整个层级上的节点。

总的来说，DFS和BFS都是强大的工具，在解决不同类型的问题时各有优势，理解它们的工作原理和适用场景对于解决问题非常重要。

模板代码


    // 广度优先搜索
    public void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();

        visited.add(start);
        queue.offer(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            // 遍历当前节点的邻居节点
            for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }


    // 深度优先搜索
    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        dfsUtil(start, visited);
    }

    private void dfsUtil(int node, Set<Integer> visited) {
        visited.add(node);
        System.out.print(node + " ");

        // 遍历当前节点的邻居节点
        for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
            if (!visited.contains(neighbor)) {
                dfsUtil(neighbor, visited);
            }
        }
    }