深度优先搜索与广度优先搜索，你知道它们的区别吗？

不念不忘少年蓝@ 2024-05-01 05:09 44阅读 0赞

### 什么是深度优先搜索？ ###

深度优先搜索（DFS，Depth-First Search）是算法中的一种重要的搜索策略。它的核心思想是“深入探索，直至无路可走，然后再回溯”。这种策略在许多问题中都有着广泛的应用，例如图的遍历、路径查找、解决迷宫问题等等。

让我们通过一个生活中的例子来理解深度优先搜索。假设你正在玩一个迷宫游戏，你需要从迷宫的入口找到出口。你可以选择往前走，直到遇到死胡同，然后再回头，选择另外一个方向继续前进，直到找到出口。这个过程，就是深度优先搜索的一个形象展现。

深度优先搜索的过程就像是在一条路上不断探索，直到这条路走不通，然后再回溯，寻找其他的路。这种策略虽然可能会让我们走一些冤枉路，但它却能保证我们遍历到每一个可能的路口，不会漏掉任何一个可能的解决方案。

明白了深度优先搜索的基本概念和核心思想后，接下来我们将学习如何通过编程实现这种搜索策略。

### 深度优先搜索的实现 ###

深度优先搜索的实现并不复杂，但却需要我们对递归或栈有深入的理解。下面，让我们通过一个Java代码示例来了解如何实现深度优先搜索。

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    public class OneMoreClass {
        
    
        // 用于标记节点是否被访问过　
        private Map<Integer, Boolean> visited = new HashMap<>();
    
        // 邻接表表示的图　
        private Map<Integer, List<Integer>> graph = new HashMap<>();
    
        /**
         * 添加边
         *
         * @param u 起点
         * @param v 终点
         */
        public void addEdge(int u, int v) {
        
            // 初始化邻接表　
            if (!graph.containsKey(u)) {
        
                graph.put(u, new ArrayList<>());
                visited.put(u, false);
            }
            if (!graph.containsKey(v)) {
        
                graph.put(v, new ArrayList<>());
                visited.put(v, false);
            }
            // 在u的邻接表中添加v　
            graph.get(u).add(v);
        }
    
        /**
         * 深度优先搜索
         *
         * @param v 当前访问的节点
         */
        public void dfs(int v) {
        
            // 标记当前节点已访问　
            visited.put(v, true);
            System.out.print(v + " ");
    
            // 访问v的所有未被访问过的邻居节点　
            for (int neighbor : graph.get(v)) {
        
                if (!visited.get(neighbor)) {
        
                    dfs(neighbor);
                }
            }
        }
    
        public static void main(String[] args) {
        
            OneMoreClass dfs = new OneMoreClass();
            dfs.addEdge(0, 1);
            dfs.addEdge(0, 2);
            dfs.addEdge(1, 2);
            dfs.addEdge(2, 0);
            dfs.addEdge(2, 3);
            dfs.addEdge(3, 3);
    
            System.out.println("深度优先搜索（从节点2开始）：");
            dfs.dfs(2);
        }
    }

在这个例子中，我们首先定义了一个图，然后通过深度优先搜索遍历了这个图。我们使用邻接表来表示图，并使用一个HashMap来记录每个节点是否被访问过。在深度优先搜索中，我们首先访问一个节点，然后递归地访问它的所有未被访问过的邻居节点。运行结果如下：

深度优先搜索（从节点2开始）：
    2 0 1 3

这段代码虽然简短，但却包含了深度优先搜索的核心思想。通过递归，我们可以轻松地实现深度优先搜索，遍历所有的节点。

然而，深度优先搜索并非没有问题。在实际使用中，我们可能会遇到一些问题，例如递归深度过大导致的栈溢出问题，或者是非递归实现时栈的使用不当等。接下来，让我们来了解一下广度优先搜索。

### 什么是广度优先搜索？ ###

在深入浸润了深度优先搜索的世界之后，我们来到了另一个重要的概念——广度优先搜索。如果说深度优先搜索是一种勇敢的冒险者，深入洞穴的每一个角落，那么广度优先搜索则像是一位细心的园丁，逐层照顾每一朵花儿，不让任何一处被忽视。

广度优先搜索（Breadth-First Search，BFS）是一种在树（Tree）或图（Graph）这样的数据结构中进行搜索的算法。它的特点是一层一层地进行搜索，每一层的节点都会被访问到，然后再进入下一层。这种方式就好比我们在寻找某个城市的地铁站，先从起点站开始，然后逐站寻找，直到找到目标站为止。

接下来，我们将深入探讨如何实现广度优先搜索，以及在实际应用中如何使用它来解决问题。

### 广度优先搜索的实现 ###

在深入理解了广度优先搜索的基本概念之后，让我们一起来探讨如何用Java语言将其实现。

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.Queue;
    
    public class OneMoreClass {
        
    
        // 用于标记节点是否被访问过　
        private Map<Integer, Boolean> visited = new HashMap<>();
    
        // 邻接表表示的图　
        private Map<Integer, List<Integer>> graph = new HashMap<>();
    
        /**
         * 添加边
         *
         * @param u 起点
         * @param v 终点
         */
        public void addEdge(int u, int v) {
        
            // 初始化邻接表　
            if (!graph.containsKey(u)) {
        
                graph.put(u, new ArrayList<>());
                visited.put(u, false);
            }
            if (!graph.containsKey(v)) {
        
                graph.put(v, new ArrayList<>());
                visited.put(v, false);
            }
            // 在u的邻接表中添加v　
            graph.get(u).add(v);
        }
    
        /**
         * 广度优先搜索
         *
         * @param v 当前访问的节点
         */
        public void bfs(int v) {
        
            // 创建一个队列，用于存储待访问的节点　
            Queue<Integer> queue = new LinkedList<>();
            queue.add(v);
            visited.put(v, true);
    
            while (!queue.isEmpty()) {
        
                int node = queue.poll();
                System.out.print(node + " ");
    
                // 访问node的所有未被访问过的邻居节点　
                for (int neighbor : graph.get(node)) {
        
                    if (!visited.get(neighbor)) {
        
                        queue.add(neighbor);
                        visited.put(neighbor, true);
                    }
                }
            }
        }
    
        public static void main(String[] args) {
        
            OneMoreClass bfs = new OneMoreClass();
            bfs.addEdge(0, 1);
            bfs.addEdge(0, 2);
            bfs.addEdge(1, 2);
            bfs.addEdge(2, 0);
            bfs.addEdge(2, 3);
            bfs.addEdge(3, 3);
    
            System.out.println("广度优先搜索（从节点2开始）：");
            bfs.bfs(2);
        }
    }

我们使用了一个队列来存储待访问的节点，而不是直接递归访问。这是因为广度优先搜索是按照距离顺序访问节点的，即先访问距离当前节点最近的节点，然后再访问距离当前节点稍远一些的节点，以此类推。运行结果如下：

广度优先搜索（从节点2开始）：
    2 0 3 1

这种实现方式看似简单，但其中蕴含的深度却不容忽视。在实际应用中，我们可能会遇到各种各样的问题，比如如何处理图中的环，如何优化搜索效率等等。

### 深度优先搜索与广度优先搜索的比较 ###

在我们深入了解深度优先搜索和广度优先搜索的特性后，现在我们来比较一下这两种搜索策略的优缺点，以及它们在不同场景下的应用。

深度优先搜索，如同其名，它的特点是尽可能深地搜索树的分支。这种策略在搜索大树时非常有效，因为它可以快速找到解决方案，或者在没有解决方案的情况下，快速排除某些路径。然而，这种策略也有其局限性，例如，它可能会在搜索过程中陷入无限循环。为了避免这种情况，我们通常需要在实现深度优先搜索时，加入一些特殊的检查机制。

广度优先搜索则是一种层次遍历的策略，它会先搜索离根节点最近的节点，然后再搜索下一层的节点。这种策略在搜索最短路径问题时非常有效，因为它总是先搜索离根节点最近的路径，所以一旦找到解决方案，那么这个解决方案就是最短的。然而，广度优先搜索需要存储所有的节点，因此在空间复杂度上，通常会比深度优先搜索要大。

让我们通过一个实际的例子来理解这两种搜索策略。假设我们想要找到从A地点到B地点的路线。如果我们使用深度优先搜索，那么我们可能会先找到一条从A到B的路线，但这条路线可能不是最短的。如果我们使用广度优先搜索，我们会先找到所有从A出发可以到达的地点，然后再从这些地点出发，找到可以到达B的地点。这样，我们找到的第一条路线，就是最短的路线。

在实际的应用中，我们应该根据问题的特性，选择最适合的搜索策略。例如，如果我们需要找到所有可能的解决方案，那么深度优先搜索可能会更有效。而如果我们需要找到最短的解决方案，那么广度优先搜索可能会更合适。

### 总结 ###

我们深入探讨了深度优先搜索和广度优先搜索，这两种广泛应用的搜索策略。我们通过生动的例子和简单的代码示例，理解了它们的基本概念，实现方法，以及在实际问题中的应用。

深度优先搜索和广度优先搜索，就如同我们生活中的两种不同的决策策略。深度优先搜索，就像是一位勇敢的冒险家，愿意深入探索未知的世界，即使可能会走一些冤枉路，也不愿意错过任何一个可能的机会。而广度优先搜索，就像是一位谨慎的规划者，他会仔细地考虑每一步的选择，以最高的效率，找到最优的解决方案。

深度优先搜索和广度优先搜索是我们解决问题的重要工具。但是，我们不能盲目地选择使用哪一种搜索策略，而应该根据问题的特性，选择最适合的策略。这就像我们在生活中面临选择时，不能盲目地跟随别人，而应该根据自己的情况，做出最适合自己的决定。