【面试高频算法解析】算法练习6 广度优先搜索

前言

本专栏旨在通过分类学习算法,使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目,帮助您深度理解每种算法,避免出现刷了很多算法题,还是一知半解的状态


专栏导航

  1. 二分查找
  2. 回溯(Backtracking)
  3. 双指针
  4. 滑动窗口
  5. 深度优先搜索
  6. 广度优先搜索
  7. 贪心算法
  8. 单调队列
  9. 堆(Heap)

算法解析

广度优先搜索(Breadth-First Search,简称 BFS)是一种遍历或搜索树结构或图结构的算法。它从一个节点开始,逐层(层次)遍历节点的邻居,然后是邻居的邻居,以此类推,直到找到所需的解或遍历完所有可达的节点。

BFS 的核心思想是先访问离起始点最近的节点,也就是说,它先宽后深地访问节点,这就是“广度优先”的含义。这种算法一般使用队列数据结构来实现。

以下是 BFS 的基本步骤:

  1. 初始化队列:首先将起始节点放入队列中。

  2. 遍历队列中的节点:只要队列不为空,就从队列的前端取出一个节点,并检查它是否是目标节点。

    • 如果找到目标,根据问题的需要,可以返回结果或继续搜索。
    • 如果不是目标,将该节点的所有未访问的邻居节点加入队列的后端。
  3. 标记已访问节点:为了避免重复访问节点,需要记录已经访问过的节点。可以在节点数据结构中添加一个访问标记,或者使用一个单独的数据结构(如哈希表)来存储已访问节点。

  4. 重复步骤2:继续执行步骤2,直到队列为空或找到目标。

BFS 通常用于解决以下类型的问题:

  • 最短路径问题:在无权图中找到两个节点之间的最短路径。
  • 连通性问题:检查图中的两个节点是否连通,或者图是否完全连通。
  • 层次遍历:层次遍历树结构或图结构(如二叉树的层次遍历)。

以下是一个在无向图中进行 BFS 的 Python 示例:

from collections import dequedef bfs(graph, start, target):visited = set()  # 创建一个集合用于存储已访问的节点queue = deque([start])  # 创建一个队列,并将起始节点加入队列while queue:node = queue.popleft()  # 从队列中取出一个节点if node == target:return True  # 如果该节点是目标,则返回Truevisited.add(node)  # 将该节点标记为已访问for neighbor in graph[node]:if neighbor not in visited:queue.append(neighbor)  # 将所有未访问的邻居加入队列return False  # 队列为空,未找到目标,返回False# 示例图
graph = {'A': ['B', 'C'],'B': ['A', 'D', 'E'],'C': ['A', 'F'],'D': ['B'],'E': ['B', 'F'],'F': ['C', 'E'],
}# 调用 BFS
print(bfs(graph, 'A', 'F'))  # 输出:True

在这个例子中,我们定义了一个图的邻接表表示,并实现了 BFS 算法来找到从节点 ‘A’ 到节点 ‘F’ 的路径是否存在。这个 BFS 实现会返回一个布尔值,标识是否找到了目标节点。


实战练习

省份数量

有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1:
请添加图片描述

输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出:2

示例 2:
请添加图片描述

输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出:3

提示:

  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j] 为 1 或 0
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]

官方题解


二叉树的层序遍历II

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

示例 1:
请添加图片描述

输入:root = [3,9,20,null,null,15,7]
输出:[[15,7],[9,20],[3]]

示例 2:
输入:root = [1]
输出:[[1]]

示例 3:
输入:root = []
输出:[]

提示:

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

官方题解

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/231806.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Python机器学习】k近邻——模型复杂度与泛化能力的关系

以某数据进行研究&#xff0c;先将数据集分为训练集和测试集&#xff0c;然后用不同的邻居数对训练集合测试集的新能进行评估&#xff1a; from sklearn.datasets import load_breast_cancer from sklearn.model_selection import train_test_split from sklearn.neighbors imp…

日程安排小程序实战教程

日常中我们经常有一些事情需要提醒自己&#xff0c;使用日历的形式比较符合实际的使用习惯。本篇我们就利用微搭低代码工具带着大家开发一款日程安排的小程序。 1 创建数据源 登录微搭低代码控制台&#xff0c;打开数据模型&#xff0c;点击创建 输入数据源的名称日程安排 …

记录第一次在GitHub上面提交Issue

第一次在GitHub上面提交Issue&#xff0c;记录一下。 对着源码调了好久才发现&#xff0c;问题并不在程序而在模型&#xff08;虽然只是一个很小的问题&#xff0c;但是能够解决问题&#xff0c;并且做出了自己的一点小小贡献&#xff0c;还是很开心。嘻嘻&#xff0c;发博客记…

BART论文解读:BERT和GPT结合起来会发生什么?

BART:Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension 主要工作 提出了BART (Bidirectional and Auto-Regressive Transformers)&#xff0c; 是一种用于自然语言生成、翻译和理解的序列到序列的预训练方法。它…

stable diffusion 基础教程-提示词之光的用法

基图 prompt: masterpiece,best quality,1girl,solo,looking at viewer,brown hair,hair between eyes,bangs,very long hair,red eyes,blush,bare shoulders,(white sundress),full body,Negative prompt: EasyNegative,badhandv4,nsfw,lowres,bad anatomy,bad hands,text…

【DevOps-07-2】Sonarqube基本使用

一、简要说明 Sonar Qube的使用方式很多&#xff0c;Maven可以整合&#xff0c;也可以采用sonar-scanner的方式&#xff0c;再查看Sonar Qube的检测效果 Sonarqube集成在Maven实现代码检测使用sonar-scanner客户端的方式 二、Sonarqube管理后台安装中文插件 1、登录Sonarqube管…

数据结构和算法-插入排序(算法效率 折半优化 顺序表与链表插入排序 代码实现)

文章目录 插入排序算法实现算法效率分析优化-折半插入排序代码实现对链表进行插入排序小结 插入排序 首先49当作第一个已经排好序得元素&#xff0c;将第二个元素与前面得元素对比&#xff0c;发现小于49&#xff0c;于是49移动位置 此时将65与之前元素对比&#xff0c;发现其…

C语言编译器(C语言编程软件)完全攻略(第二部分:与编译器相关的几个知识点)

介绍常用C语言编译器的安装、配置和使用。 二、与编译器相关的几个知识点 上节我们介绍了编译器和 IDE 的概念&#xff0c;大家肯定希望赶紧实践一下&#xff0c;用 IDE 真正地运行一段C语言代码来看看效果&#xff0c;这样能够更快地获得成就感。 但是&#xff0c;使用 IDE …

Linux第20步_在虚拟机上安装“Visual Studio Code”

1、双击windows系统桌面上的“FileZilla Client.exe”&#xff0c;打开FTP客户端&#xff0c;点击03软件下的Visual Studio Code&#xff0c;发现code_1.50.1-1602600906_amd64。 2、点击“文件”&#xff0c;然后点击“站点管理器”&#xff0c;见下图操作&#xff1a; 3、点…

vr体验馆用什么软件计时计费,如遇到停电软件程序如何恢复时间

vr体验馆用什么软件计时计费&#xff0c;如遇到停电软件程序如何恢复时间 一、软件程序问答 如下图&#xff0c;软件以 佳易王vr体验馆计时计费软件V17.9为例说明 1、软件如何计时间&#xff1f; 点击相应编号的开始计时按钮即可 2、遇到停电再打开软件时间可以恢复吗&…

在 Oracle 数据库表中加载多个数据文件

在本文中&#xff0c;我将展示 SQL 加载器 Unix 脚本实用程序的强大功能&#xff0c;其中 SQL 加载器可以使用自动 shell 脚本加载多个数据文件。这在处理大量数据以及需要将数据从一个系统移动到另一个系统时非常有用。 它适合涉及大量历史数据的迁移项目。那么就不可能为每…

自然语言处理24-T5模型的介绍与训练过程,利用简单构造数据训练微调该模型,体验整个过程

大家好,我是微学AI,今天给大家介绍一下自然语言处理24-T5模型的介绍与训练过程,利用简单构造数据训练微调该模型,体验整个过程。在大模型ChatGPT发布之前,NLP领域是BERT,T5模型为主导,T5(Text-to-Text Transfer Transformer)是一种由Google Brain团队在2019年提出的自然…

大数据概念:数据网格和DataOps

数据网格&#xff08;Data Mesh&#xff09; 一种新型的数据架构模式&#xff0c;旨在解决传统数据架构中存在的一些问题&#xff0c;例如数据孤岛、数据冗余、数据安全等。数据网格将数据作为一种服务&#xff0c;通过在分布式环境中提供数据服务&#xff0c;实现数据的共享和…

多内层神经网络具有先天的不可解释性

多层神经网络的不可解释性是指其内部的决策过程很难被人类理解和解释。这主要是因为多层神经网络具有大量的神经元和多个层次的连接&#xff0c;使得网络的决策过程变得非常复杂。 具体而言&#xff0c;多层神经网络中每一层的神经元会根据输入的特征进行加权组合和非线性变换&…

Centos服务器安装Certbot以webroot的方式定时申请SSL免费证书

最近发现原先免费一年的SSL证书都改为3个月的有效期了&#xff0c;原先一年操作一次还能接受&#xff0c;现在3个月就要手动续期整的太慢烦了&#xff0c;还是让程序自动给处理下吧&#xff0c; 安装 Certbot yum install epel-release -y yum install certbot -yEPEL是由 Fe…

系统安全及应用

文章目录 系统安全及应用一、账号安全基本措施1、系统账号清理1.1 将用户设置为无法登录1.2 锁定长期不使用的账号1.3 删除无用的账户1.4 清空一个账号密码1.5 锁定账户文件passwd、shadow 2、密码安全控制设置密码有效期 3、命令历史限制3.1 减少命令记录条数3.2 登录时自动清…

13. 强化学习编程实验1-在格子世界中寻宝(1)

文章目录 1.实验目的2.任务描述3.任务分析3.1 待求问题是多步决策问题否3.2 问题求解过程是一个马尔科夫决策过程3.3 状态空间S的确定3.4 动作空间A的确定3.5 状态转移概率P的确定3.6 立即回报R的确定3.7 折扣 γ \gamma γ的确定 4. 编程架构4.1 程序中有哪些对象和类4.2 环境…

pyfolio工具结合backtrader分析量化策略组合,附源码+问题分析

pyfolio可以分析backtrader的策略&#xff0c;并生成一系列好看的图表&#xff0c;但是由于pyfolio直接install的稳定版有缺陷&#xff0c;开发版也存在诸多问题&#xff0c;使用的依赖版本都偏低&#xff0c;试用了一下之后还是更推荐quantstats。 1、安装依赖 pip install …

数据采集有哪些方法?HTTP代理起到什么作用?

在这个数字化的时代&#xff0c;数据就如同生活中不可或缺的元素&#xff0c;我们的行为、喜好、甚至是想法都被转化成了数字化的信息。那么&#xff0c;现代社会是如何进行数据的采集的呢&#xff1f;让我们一同来看看&#xff01; 1. 网络浏览行为的追踪 在我们浏览互联网的…

【AI视野·今日NLP 自然语言处理论文速览 第六十六期】Tue, 31 Oct 2023

AI视野今日CS.NLP 自然语言处理论文速览 Tue, 31 Oct 2023 (showing first 100 of 141 entries) Totally 100 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers The Eval4NLP 2023 Shared Task on Prompting Large Language Models a…