广度优先搜索和深度优先搜索（广度优先搜索和深度优先搜索时间复杂度）

科技前沿 • 2025-06-08 12:34 • 阅读 33

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

 <p id="2P4RF4MN"><strong>摘要：</strong></p><p id="2P4RF4MO">1，广度优先搜索介绍</p><p id="2P4RF4MP">2，广度优先搜索的解题步骤</p><p id="2P4RF4MQ">3，广度优先搜索的代码实现</p><p id="2P4RF4MS"><strong>1，广度优先搜索介绍</strong></p><p id="2P4RF4MT">广度优先搜索(Breadth-first search，BFS)，又称宽度优先搜索，简单的说，它是从一个点开始，始终访问离他最近的点，直到所有点都被访问，则算法终止。</p><p id="2P4RF4MV">BFS属于一种盲目搜寻算法，它不会考虑结果的可能位置，而是彻底搜索整个数据结构，直到找到结果为止。</p><p id="2P4RF4N1">BFS 一般用于树，矩阵和图的遍历，对于树来说就是从根节点开始，从上到下一层一层的遍历。对于矩阵来说就是从某一个点开始沿着它的上下左右四个方向遍历(如果题要求可以访问斜对角，就需要沿着该点的 8 个方向遍历)。前两个我们不做介绍，这里我们主要讲下图的BFS。</p><p id="2P4RF4N3">因为每次都是搜索离起始点最近的点，我们可以把搜索过的点添加到队列中，当队列中的点出队的时候，我们继续搜索和它相邻的点。</p><p id="2P4RF4N5">这里要注意，一个点不能重复搜索，否则会形成死循环，所以当一个点被访问完之后还需把它标记一下。</p><p id="2P4RF4N7"><strong>2，BFS的解题步骤</strong></p><p id="2P4RF4N8">1，创建一个队列，把搜索的起始点添加到队列中，接着在创建一个数组visited，记录被访问过的顶点。</p><p id="2P4RF4N9">2，队列元素出队，访问与出队元素相连的所有没被访问过的顶点，把他们都加入到队列中。</p><p id="2P4RF4NA">3，重复步骤 2 ，直到队列为空则算法停止。</p><p id="2P4RF4NC">如下图所示，假如从顶点 0 开始搜索，搜索步骤如下：</p><p class="f_center"> <img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0608%2Fej00seqskq0039d200if00kig00if00ki.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2P4RF4NF">所以我们发现BFS搜索的首先是离他最近的顶点，如下图所示，先搜索通过一条边和它相连的点，在搜索通过两条边和它相连的点……，由近及远。</p><p class="f_center"> <img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0608%2Fa441ac2dj00seqskr0029d200fy0099g00fy0099.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p>

讯享网

广度优先搜索和深度优先搜索（广度优先搜索和深度优先搜索时间复杂度）

相关推荐