1. 首页首页
  2. 科技前沿科技前沿

2025年广度优先搜索（广度优先搜索树）

科技前沿 • • 阅读 65

广度优先搜索（广度优先搜索树）svg xmlns http www w3 org 2000 svg style display none svg

大家好，我是讯享网，很高兴认识大家。



 <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <h4>广度优先搜索&#xff08;BFS&#xff09;与深度优先搜索&#xff08;DFS&#xff09;详解</h4>

讯享网

广度优先搜索（BFS）和深度优先搜索（DFS）是图算法中两个基本的遍历方法。通过实例分析它们的工作原理和代码实现，可以更深入地理解它们的应用场景及优缺点。

1. 广度优先搜索（BFS）

原理：
广度优先搜索从起始节点开始，逐层遍历图中的所有节点，优先访问距离起始节点最近的节点。其核心思想是以一种层级结构进行遍历。

示例：
假设有一个无向图如下所示：

讯享网

从节点 开始进行广度优先搜索的顺序是：。

实现步骤：

  1. 初始化一个队列，将起始节点 加入队列。
  2. 标记节点 为已访问。
  3. 当队列不为空时，执行以下操作：
    • 从队列中取出一个节点，访问该节点的所有未被访问过的邻居节点，并将这些邻居节点加入队列，同时标记为已访问。
  4. 重复步骤3，直到队列为空。

代码实现（Java）：

 

示例代码详细解释：
 

     
 
  1. 初始化队列和集合： 
  
       
   
    • ：使用LinkedList来实现队列。
      •  
   
    • ：使用HashSet来存储已访问的节点，避免重复访问。
      •  
  
     
    2.  
 
  2. 将起始节点加入队列并标记为已访问： 
  
       
   
    • ：将起始节点加入队列。
      •  
   
    • ：将起始节点加入已访问集合。
      •  
  
     
    3.  
 
  3. 当队列不为空时，持续遍历： 
  
       
   
    • ：当队列不为空时，继续遍历。
      •  
   
    • ：从队列中取出一个节点。
      •  
   
    • ：处理当前节点，这里简单打印节点值。
      •  
  
     
    4.  
 
  4. 遍历当前节点的所有邻居节点： 
  
       
   
    • ：遍历当前节点的所有邻居节点。
      •  
   
    • ：如果邻居节点未被访问过。
      •  
   
    • ：将邻居节点加入队列。
      •  
   
    • ：将邻居节点标记为已访问。
      •  
  
     
    5.  

 

应用：
 

     
 
  • 最短路径求解：在无权图中，BFS可以找到从起点到终点的最短路径。
    •  
 
  • 层级遍历：可以用于二叉树的层序遍历。
    •  

 

优缺点：
 

     
 
  • 优点：能找到无权图中的最短路径，适用于层级遍历。
    •  
 
  • 缺点：在宽度较大的图中，BFS的空间复杂度较高，因为需要存储每一层的所有节点。
    •  

 

2. 深度优先搜索（DFS）
 

原理：
 深度优先搜索从起始节点开始，沿着一条路径不断深入，直到不能继续为止，然后回溯到上一节点，继续探索其他路径。其核心思想是优先深入每一条路径。
 

示例：
 假设有一个无向图如下所示：
 

讯享网
 

从节点 开始进行深度优先搜索的顺序可能是：。具体顺序可能因为邻接节点的访问顺序不同而有所不同。
 


讯享网
 

实现步骤：
 

     
 
  1. 初始化一个栈，将起始节点 加入栈。
    2.  
 
  2. 标记节点 为已访问。
    3.  
 
  3. 当栈不为空时，执行以下操作： 
  
       
   
    • 从栈中取出一个节点，访问该节点的所有未被访问过的邻居节点，并将这些邻居节点加入栈，同时标记为已访问。
      •  
  
     
    4.  
 
  4. 重复步骤3，直到栈为空。
    5.  

 

代码实现（Java）：
 

 

示例代码详细解释：
 

     
 
  1. 初始化栈和集合： 
  
       
   
    • ：使用Stack来实现栈。
      •  
   
    • ：使用HashSet来存储已访问的节点，避免重复访问。
      •  
  
     
    2.  
 
  2. 将起始节点加入栈并标记为已访问： 
  
       
   
    • ：将起始节点加入栈。
      •  
   
    • ：将起始节点加入已访问集合。
      •  
  
     
    3.  
 
  3. 当栈不为空时，持续遍历： 
  
       
   
    • ：当栈不为空时，继续遍历。
      •  
   
    • ：从栈中取出一个节点。
      •  
   
    • ：处理当前节点，这里简单打印节点值。
      •  
  
     
    4.  
 
  4. 遍历当前节点的所有邻居节点： 
  
       
   
    • ：遍历当前节点的所有邻居节点。
      •  
   
    • ：如果邻居节点未被访问过。
      •  
   
    • ：将邻居节点加入栈。
      •  
   
    • ：将邻居节点标记为已访问。
      •  
  
     
    5.  

 

应用：
 

     
 
  • 路径搜索：在图中查找特定路径或解决迷宫问题。
    •  
 
  • 拓扑排序：用于DAG（有向无环图）的拓扑排序。
    •  
 
  • 连通性检查：判断图的连通性，查找连通分量。
    •  

 

优缺点：
 

     
 
  • 优点：空间复杂度较低，在图的深度较大
    •  

 

而宽度较小时，性能较好。
 

     
 
  • 缺点：可能会陷入深层路径，从而导致找到的路径不是最优解（尤其在有权图中）。
    •  

 

比较与选择
 

     
 
  • 广度优先搜索（BFS）适用于需要找到最短路径的问题，以及需要层级遍历的情况。
    •  
 
  • 深度优先搜索（DFS）适用于需要探索所有路径的问题，以及在图的深度较大而宽度较小时的情况。
    •  

 

在实际应用中，选择BFS还是DFS取决于具体问题的要求和图的结构特性。如果需要找到最短路径或者处理宽度较大的图，优先选择BFS；如果需要遍历整个图或者处理深度较大的图，优先选择DFS。
 

示例对比
 

以一个更复杂的图为例，进一步对比BFS和DFS的行为。假设我们有如下无向图：
 

讯享网
 

从节点 开始，BFS 和 DFS 的遍历顺序如下：
 

     
 
  • BFS：
    •  
 
  • DFS：
    •  

 

BFS详解：
 

     
 
  1. 初始化队列：
    2.  
 
  2. 访问 ，队列变为：
    3.  
 
  3. 访问 ，队列变为：
    4.  
 
  4. 访问 ，队列变为：
    5.  
 
  5. 访问 ，队列变为：
    6.  
 
  6. 依次访问 ，直到队列为空。
    7.  

 

DFS详解：
 

     
 
  1. 初始化栈：
    2.  
 
  2. 访问 ，栈变为：
    3.  
 
  3. 访问 ，栈变为：
    4.  
 
  4. 访问 ，栈变为：
    5.  
 
  5. 访问 ，栈变为：
    6.  
 
  6. 访问 ，栈变为：
    7.  
 
  7. 访问 ，栈变为：
    8.  
 
  8. 依次访问 ，直到栈为空。
    9.  

 

这两个算法在遍历顺序上的不同反映了它们各自的特性和适用场景。
 


                    


                    


                    

                        

                            

                                小讯
                            

                            

                                

                                    
                                        
                                    
                                

                            

                        

                    

                


                

                    
                    
                    

                        
                        

                             上一篇
                            2025-06-10 23:39
                        

                    

                    
                    


                    
                    
                    

                        
                        

                            下一篇 
                            2025-06-11 20:45
                        

                    

                    
                    
                


                

                    
相关推荐

                    
                

                

                    

                        版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/173448.html