算法——图——bsf 广度优先搜索算法 (Breadth First Search)

图遍历算法——bsf 广度优先搜索算法 (Breadth First Search) 算法

  • 概述
  • 算法过程
    • 步骤一:初始化原点到队列
    • 步骤二:将队列的头顶点放入到已完成集合
    • 步骤三:将订单的关联顶点放入到队列中
    • 步骤四:将u顶点设置为完成节点。
    • 步骤五:重复步骤二至四。
  • 时间复杂度&空间复杂度
    • 时间复杂度
    • 空间复杂度

概述

        广度优先搜索(BFS)是一种重要的图遍历算法,用于在横向运动中搜索图的所有顶点。它从一个给定的顶点开始,在进入下一个级别之前访问它的所有邻居。BFS的时间复杂度取决于图中顶点和边的数量。

文章中使用的动画网站地址:
限 pc: 广度优先算法 :http://www.donghuasuanfa.com/platform/portal?pc=bfs

算法一览表:https://blog.csdn.net/ww753951/article/details/106862328

动画算法一览表:http://www.donghuasuanfa.com/portal

算法过程

        算法分为五个步骤。
        步骤一:将源点放入到队列中。
        步骤二:将队列的头顶点u放入到已完成列表。
        步骤三:将u的所有未处理过的关联顶点放入到队列中,并标记为已处理。

        步骤四:将u顶点设置为完成顶点。
        步骤五:重复步骤二至四。


以下图为例,图的原点为7,则算法遍历图节点的顺序为7,13,25,16,18,39。

请添加图片描述

步骤一:初始化原点到队列

步骤演示过程如下图1-1所示。节点7为源点。算法首先将节点7移动到队列Q中。

请添加图片描述

图1-1

步骤二:将队列的头顶点放入到已完成集合

将队列的头元素u放入到已遍历完成列表。当前队列的头部顶点为7,所以将7顶点移动到已遍历集合。步骤演示过程如下图2-1所示。
请添加图片描述

图2-1

步骤三:将订单的关联顶点放入到队列中

将u的所有未处理过的关联顶点放入到队列中,并标记为已处理,节点颜色变为红色。
当前u的所有未处理的元素分别为13,25,16。所以将7的关联顶点分别放入队列。
步骤演示过程如下图3-1所示。

请添加图片描述

图3-1

步骤四:将u顶点设置为完成节点。

当前顶点为u=7。 将u=7顶点设置为已完成,并标记为绿色。步骤演示过程如下图3-1所示。
请添加图片描述

图4-1

步骤五:重复步骤二至四。

步骤二:将队列的头部顶点13放入到已遍历结合。
步骤三:将13节点的关联元素放入到到队列, 因为13的关联顶点分别为7和25,且7已处理、25已放入队列,所以13顶点的此步骤无需处理。
步骤四:将13节点设置为完成节点。
整体步骤如图5-1所示。

请添加图片描述

图5-1





        剩下的节点处理和上述步骤一致,不再赘述。

时间复杂度&空间复杂度

时间复杂度

        在BFS中,每个顶点和边只访问一次。因此,BFS的时间复杂度可以表示为O(V+E),其中V是图中顶点的数量,E是图中边的数量。

        让我们分解一下时间复杂性分析:
        1.访问所有顶点:BFS需要访问图中的所有顶点。这需要O(V)时间。
        2.检查所有边:BFS还需要检查所有边,以确定是否有任何未访问的顶点连接到当前顶点。对于每个顶点,我们需要检查其所有相邻顶点。在最坏的情况下,每个顶点与其他每个顶点都有一条边,即一个完整的图。这需要O(E)时间。

因此,BFS的总体时间复杂度为O(V+E)。

空间复杂度

        BFS的空间复杂度由队列数据结构决定,队列数据结构用于跟踪访问的顶点和要探索的顶点。在最坏的情况下,当访问所有顶点时,队列可以将所有顶点存储在图的一个级别上。因此,BFS的空间复杂度也是O(V)。

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

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

相关文章

【正点原子STM32连载】 第五十章 FATFS实验 摘自【正点原子】APM32F407最小系统板使用指南

1)实验平台:正点原子stm32f103战舰开发板V4 2)平台购买地址:https://detail.tmall.com/item.htm?id609294757420 3)全套实验源码手册视频下载地址: http://www.openedv.com/thread-340252-1-1.html## 第五…

【JAVA学习笔记】69 - 多用户通信系统

项目代码 https://github.com/yinhai1114/Java_Learning_Code/tree/main/QQClient https://github.com/yinhai1114/Java_Learning_Code/tree/main/QQServer 〇、环境设置以及前言 该项目内会弱化UI界面的设计,因为JAVA本质不是用来开发界面的。 项目开发流程 对于…

汽车标定技术(九)--标定常量与#pragma的趣事

目录 1. 不添加#pragma语句 2. 添加#pragma语句 3. 标定量只给flash空间,不给ram指定空间 4. 总结 在之前不会使用overlay机制的时候,我们想要做汽车标定,标定常量编译出来的地址一般都应该是ram的地址,而且在链接文件中都会指…

深度学习AI识别人脸年龄

以下链接来自 落痕的寒假 GitHub - luohenyueji/OpenCV-Practical-Exercise: OpenCV practical exercise GitHub - luohenyueji/OpenCV-Practical-Exercise: OpenCV practical exercise import cv2 as cv import time import argparsedef getFaceBox(net, frame, conf_thresh…

基于C#+WPF编写的调用讯飞星火大模型工具

工具源码:https://github.com/lishuangquan1987/XFYun.SparkChat 工具效果截图: 支持流式输出: 其中ApiKey/ApiSecret/AppId需要自己到讯飞星火大模型官网去注册账号申请,免费的。 申请地址:https://xinghuo.xfyun.cn/ 注册之…

代码随想录算法训练营第23期day49| 123.买卖股票的最佳时机III、188.买卖股票的最佳时机IV

目录 一、(leetcode 123)买卖股票的最佳时机III 二、(leetcode 188)买卖股票的最佳时机IV 一、(leetcode 123)买卖股票的最佳时机III 力扣题目链接 增加了两次的限制,相应的就是需要考虑的状…

【AI】自回归 (AR) 模型使预测和深度学习变得简单

自回归 (AR) 模型是统计和时间序列模型,用于根据数据点的先前值进行分析和预测。这些模型广泛应用于各个领域,包括经济、金融、信号处理和自然语言处理。 自回归模型假设给定时间变量的值与其过去的值线性相关,这使得它们可用于建模和预测时…

R语言将向量横向转换为单行数据框,随后整合数量不确定的数据框

vector1 c(1, “karthik”, “IT”) names(vector1) c(“id”, “name”, “branch”) df data.frame(as.list(vector1)) print(df) 先给向量的元素命名,然后转换为列表,最后转换为数据框。 我的需求大概是这个样子:数量不确定的仅有单行…

JL-29 雪深监测仪

技术参数 太阳能功率&#xff1a;10W 电池供电&#xff1a;3.7V/20AH 测量量程&#xff1a;0&#xff5e;5m&#xff08;探头处有15cm的盲区&#xff09; 分 辨 率&#xff1a;1mm 随机误差&#xff1a;1.5mm 非线性误差&#xff1a;<0.7mm 温度误差&#xff1a;<0…

PostgreSQL 入门教程

PostgreSQL 入门教程 1. 历史背景2. 概念3. 特点4. 用法4.1 数据库连接4.2 数据库创建4.3 表创建4.4 数据插入4.5 数据查询4.6 数据更新4.7 数据删除 5. 安装步骤6. 简单示例7. 扩展7.1 数据类型7.2 查询优化7.3 并发控制7.4 数据备份和恢复7.5 扩展性和高可用性7.6 安全性加固…

数据复现-企业数字化转型与中国实体经济发展分析

数据简介&#xff1a;在当今快速发展的数字化时代&#xff0c;数字技术已经成为企业数字化转型的核心驱动力之一。尤其对于中国这样一个拥有庞大实体经济的国家而言&#xff0c;结合数字技术的应用&#xff0c;可以为企业带来前所未有的巨大机遇和挑战。在中国&#xff0c;实体…

大促期间治理品牌窜货的诀窍

渠道问题中&#xff0c;最常见的是窜货&#xff0c;窜货还会伴随低价&#xff0c;会影响其他经销商的利益&#xff0c;同时窜货还可能带来假货&#xff0c;所以治理窜货是品牌的责任&#xff0c;对于出货量巨大的双十一大促&#xff0c;品牌更应重视对窜货问题的治理。 力维网络…

MySQL binlog 日志解析后的exec_time导致表示什么时间?

1. exec_time 到底表示什么时间&#xff1f; MySQL binlog日志解析后&#xff0c;我们能看到会有 exec_time &#xff0c;从字面意思理解这个记录的是执行时间&#xff0c;那这个记录的到底是单条sql的执行时间&#xff1f;还是事务的执行时间&#xff1f;下面通过测试来解读一…

Scikit-LLM:一款大模型与 scikit-learn 完美结合的工具!

Scikit-LLM 是文本分析领域的一项重大变革&#xff0c;它将像 ChatGPT 这样强大的语言模型与 scikit-learn 相结合&#xff0c;提供了一套无与伦比的工具包&#xff0c;用于理解和分析文本。 有了 scikit-LLM&#xff0c;你可以发现各种类型的文本数据中的隐藏模式、情感和上下…

c++分割路径的字符串,得到 目录 文件名 扩展名

简单的做一个c小代码片的记录 c分割了图片的 路径字符串&#xff0c;得到 目录 文件名 扩展名 #include <iostream> using namespace std;int main() {std::string path "E:\\set1_seg\\32.jpg";//index:"\\"在字符串中的位置int index path.find…

深度学习基于python+TensorFlow+Django的花朵识别系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 花朵识别系统&#xff0c;基于Python实现&#xff0c;深度学习卷积神经网络&#xff0c;通过TensorFlow搭建卷积神经…

【图像处理:OpenCV-Python基础操作】

【图像处理&#xff1a;OpenCV-Python基础操作】 1 读取图像2 显示图像3 保存图像4 图像二值化、灰度图、彩色图&#xff0c;像素替换5 通道处理&#xff08;通道拆分、合并&#xff09;6 调整尺寸大小7 提取感兴趣区域、掩膜8 乘法、逻辑运算9 HSV色彩空间&#xff0c;获取特定…

教育共赴 行以致远 |忻州市高级技工学校领导一行莅临唯众考察交流

​ 2023年11月9日下午&#xff0c;忻州市高级技工学校副校长曲云凤、计算机应用与维修专业负责人王彪、计算机应用与维修专业五名骨干教师李巧英、卢艳、官雪梅、李帅、段娜一行七人到访武汉唯众智创科技有限公司&#xff0c;就物联网专业人才培养方案、课程体系建设等进行了考…

Codeforces Round 908 (Div. 2)题解

目录 A. Secret Sport 题目分析: B. Two Out of Three 题目分析: C. Anonymous Informant 题目分析: A. Secret Sport 题目分析: A,B一共打n场比赛&#xff0c;输入一个字符串由A和‘B’组成代表A赢或者B赢&#xff08;无平局&#xff09;&#xff0c;因为题目说明这个人…

如何在CentOS上安装SQL Server数据库并通过内网穿透工具实现远程访问

文章目录 前言1. 安装sql server2. 局域网测试连接3. 安装cpolar内网穿透4. 将sqlserver映射到公网5. 公网远程连接6.固定连接公网地址7.使用固定公网地址连接 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;…