2025年广度优先搜索和深度优先搜索（广度优先搜索和深度优先搜索的基本思想）

科技前沿 • 2025-05-23 23:24 • 阅读 45

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

 <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>1 概述</h4>

讯享网

算法是作用于具体的数据结构之上的，深度优先搜索算法和广度优先搜索算法都是基于图这种数据结构的。主要原因是因为图的这种数据结构表达能力很强，大部分涉及搜索的场景都可以抽象成图。
图上的搜索算法，最直接的理解就是，在图中找出从一个顶点出发，到另一个顶点的路径。具体方法有很多，比如今天要讲的两种最简单、最“暴力”的深度优先、广度优先搜索，还有 A、IDA 等启发式搜索算法。

2 广度优先搜索（Breath First Search）

广度优先搜索（Breath First Search）简称BFS，它是一种地毯式层层推进的搜索策略，即优先查找距离顶底近的，然后是次近的，依次往外搜索。如下图所示BFS搜索策略，搜索结果 1->2-3->4->5->6->7。

图2-1
讯享网

算法描述：
1.从图中顶点V出发，首先访问V
2.依次访问V的，各个未被访问的邻接节点
3.依次从上述邻接节点出发，依次访问他们的各个未被访问的邻接节点。
4.如果此时图中任然有未被访问的顶点，则选择图中的一个未被访问的顶点作为起始顶点。重复广度优先搜索的过程，直到图中的所有节点均被访问过。

伪代码描述：

讯享网

3 深度优先搜索（Depth First Search）

深度优先搜索（Depth First Search）简称DFS，其过程简要来说就是对每一个可能的分支路径深入到不能深入为止，而且每个节点只能访问一次。图2-1所示DFS搜索策略，搜索结果 1->2->5->7->3->6->4。

算法描述：
1.从图中某个顶点V出发，访问顶点V
2.依次从V未被访问的邻接点出发，对图进行深度优先遍历；直至图中和V有路径相通的顶点都被访问
3.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

伪代码描述

java 代码实现

讯享网

4 LeetCode实战

思路：使用bfs，将已经访问节点置位0

讯享网

参考文献：
[1]https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
[2] https://en.wikipedia.org/wiki/Breadth-first_search
[3]https://en.wikipedia.org/wiki/Depth-first_search

2025年广度优先搜索和深度优先搜索（广度优先搜索和深度优先搜索的基本思想）

2 广度优先搜索（Breath First Search）

3 深度优先搜索（Depth First Search）

4 LeetCode实战

相关推荐