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

2024-01-07 17:59:25

前言

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


专栏导航

  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 deque

def bfs(graph, start, target):
    visited = set()  # 创建一个集合用于存储已访问的节点
    queue = deque([start])  # 创建一个队列,并将起始节点加入队列
    
    while queue:
        node = queue.popleft()  # 从队列中取出一个节点
        if node == target:
            return True  # 如果该节点是目标,则返回True
        visited.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

官方题解

文章来源:https://blog.csdn.net/sinat_41883985/article/details/135403248
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。