首页 > 其他分享 >数据结构之广度优先搜索

数据结构之广度优先搜索

时间:2024-08-29 14:51:16浏览次数:9  
标签:优先 标记 队列 BFS 访问 visited 广度 数据结构 节点

一、基本思想

BFS的基本思想是使用队列(Queue)数据结构来实现。队列是一种先进先出(FIFO)的数据结构,这符合BFS逐层访问节点的需求。在BFS中,首先将起始节点加入队列,并标记为已访问。然后,从队列中取出一个节点,访问其所有未被访问的相邻节点,并将这些相邻节点加入队列。重复这个过程,直到队列为空,即所有可达的节点都被访问过。

二、算法步骤

1、初始化:创建一个队列,并将起始节点加入队列,同时标记为已访问。
2、循环访问:当队列不为空时,执行以下步骤:
(1)从队列中取出一个节点(队首节点)。
(2)访问该节点(例如,打印节点值、处理节点数据等)。
(3)遍历该节点的所有未被访问的相邻节点。
(4)对于每个相邻节点,如果它未被访问过,则将其加入队列,并标记为已访问。
3、结束条件:当队列为空时,算法结束。此时,所有可达的节点都已被访问过。

三、应用场景

BFS广泛应用于图论中的各种问题,包括但不限于:

1、最短路径问题:在无权图中,BFS可以找到从一个节点到另一个节点的最短路径(以边的数量计)。
2、连通性问题:判断图中的所有节点是否都连通,或者某个节点是否可以到达图中的其他节点。
3、拓扑排序:对有向无环图(DAG)进行排序,使得对于任意一条有向边u->v,节点u都在节点v之前。
4、层次遍历:在树形结构中,BFS可以用于层次遍历,即按层级访问树的节点。

四、优点与缺点

1、优点:
BFS能够找到从起始节点到目标节点的最短路径(在无权图中)。
适用于解决连通性、拓扑排序等问题。

2、缺点:
当图非常大或非常稀疏时,BFS可能需要访问大量的节点才能找到目标节点或确定无路径可达。
在某些情况下,如寻找所有路径或评估路径的多样性时,BFS可能不如深度优先搜索(DFS)有效。

五、代码示例

以下是一个简单的BFS代码示例,用于在无权图中进行搜索:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 假设图使用邻接表表示
vector<vector<int>> graph;
vector<bool> visited;

void bfs(int start) {
    queue<int> q;
    visited.assign(graph.size(), false); // 初始化访问标记
    visited[start] = true; // 标记起始节点为已访问
    q.push(start); // 将起始节点加入队列

    while (!q.empty()) {
        int node = q.front(); // 取出队首节点
        q.pop(); // 弹出队首节点
        cout << node << " "; // 访问节点(这里只是打印节点值)

        // 遍历当前节点的所有相邻节点
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) { // 如果相邻节点未被访问过
                visited[neighbor] = true; // 标记为已访问
                q.push(neighbor); // 加入队列以便后续访问
            }
        }
    }
}

int main() {
    // 示例:构建一个图并调用BFS
    // ...(图的构建代码省略)
    bfs(0); // 假设从节点0开始搜索
    return 0;
}

标签:优先,标记,队列,BFS,访问,visited,广度,数据结构,节点
From: https://blog.csdn.net/qq_39311377/article/details/141369366

相关文章

  • 数据结构之最小生成树
    一、算法概述构建最小生成树的常用算法有两种:Prim算法和Kruskal算法。1.Prim算法Prim算法从某一个顶点开始,逐步增加边和顶点,直到形成最小生成树。算法的基本思想是:1、初始化:选择一个顶点作为起始点,将其加入已选集合,其他顶点属于未选集合。2、循环:在未选集合中选择一条......
  • 数据结构-顺序表-详解
    数据结构-顺序表-详解1.是什么2.静态顺序表2.1实现2.2缺点3.动态顺序表3.1总览3.2动态顺序表的创建3.3初始化3.4销毁3.5打印3.6插入尾插头插3.7删除尾删头删1.是什么顺序表是一种基本的数据结构,它使用一组连续的内存空间来存储数据元素,这些元素在逻辑上也是连续......
  • 数据结构(C)---双端队列(Deque)
    在使用本博客提供的学习笔记及相关内容时,请注意以下免责声明:信息准确性:本博客的内容是基于作者的个人理解和经验,尽力确保信息的准确性和时效性,但不保证所有信息都完全正确或最新。非专业建议:博客中的内容仅供参考,不能替代专业人士的意见和建议。在做出任何重要决定之前,请咨询相......
  • 数据结构与算法(循环链表,双向链表)
    循环链表最后一个元素指向首元素带尾指针的循环链表合并双向链表双向链表:在单链表的每个结点里再增加一个指向其直接前驱的指针域prior,这样链表中就形成了有两个方向不同的链,故称为双向链表双向链表插入操作思路代码删除操作思路代码三种链表比较顺序表......
  • [学习笔记] Splay & Treap 平衡树 - 数据结构
    [学习笔记]Splay&Treap平衡树-数据结构Splay树又名伸展树,一种平衡二叉查找树,通过\(\text{Splay}\)操作不断把节点旋到根节点来维护整颗树的平衡。说人话,很玄学的玩意,复杂度是单log级别的。为啥是单log,科学的解释请移步OI-WIKI。不科学的解释就是,通过不断\(\tex......
  • 25版王道数据结构课后习题详细分析 第五章 树与二叉树 5.4 树、森林
    一、单项选择题————————————————————————————————————————解析:正确答案:D————————————————————————————————————————解析:森林与二叉树具有对应关系,因此,我们存储森林时应先将森林转换......
  • 【Test 002】 高阶数据结构 二叉搜索树 必会知识点!
    文章目录1.二叉搜索树的概念2.二叉搜索树K模型的代码实现2.1Find()查找的实现2.2Insert()插入的实现2.3InOrder()中序遍历的实现2.4Erase()删除的实现3.二叉搜索树的KV模型4.二叉搜索树的性能分析1.二叉搜索树的概念......
  • 数据结构——单向链表
    链表1.空间可以不连续(理论上长度是无限的)2.访问元素不方便3.链表需要更大的空间存放数据和节点地址4.链表的插入和删除效率很高O(1)单向链表无头单向链表,节点插入在头的话,每次头结点都会变,所以有了有头链表,头结点的pNext总是指向链表的第一个节点1.创建空链表//创建空......
  • 【数据结构与算法第二章(理论知识)】绪论:数据结构的定义、算法的基本概念和算法效率分析
     目录【数据结构与算法第二章(理论知识)】绪论1.1数据结构的定义1.2算法的基本概念1.3算法效率分析1.3.1时间复杂度1.3.2空间复杂度【数据结构与算法第二章(理论知识)】绪论1.1数据结构的定义    数据结构没有一个统一的官方定义,以下是一些经典书籍对数据......
  • 算法与数据结构——哈希算法
    哈希算法前面介绍了哈希表的工作原理和哈希冲突的处理方法。然而无论是开放寻址还是链式地址,它们只能保证可以在发生冲突时正常工作,而无法减少哈希冲突的发生。如果哈希冲突过于频繁,哈希表的性能则会急剧劣化。如下图所示,对于链式哈希表,理想情况下键值对均匀分布在各个桶中,达到......