队列和广度优先搜索
2022/9/16 23:18:30
本文主要是介绍队列和广度优先搜索,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
队列
队列(Queue):简称为队,一种线性表数据结构,是一种只允许在表的一端进行插入操作,而在表的另一端进行删除操作的线性表。
把队列中允许插入的一端称为 「队尾(rear)」;把允许删除的另一端称为 「队头(front)」。当表中没有任何数据元素时,称之为 「空队」。
队列有两种基本操作:「插入操作」 和 「删除操作」。
- 队列的插入操作又称为「入队」。
- 队列的删除操作又称为「出队」。
存储方式
- 「顺序存储的队列」:利用一组地址连续的存储单元依次存放队列中从队头到队尾的元素,同时使用指针
front
指向队头元素在队列中的位置,使用指针rear
指示队尾元素在队列中的位置。 - 「链式存储的队列」:利用单链表的方式来实现队列。队列中元素按照插入顺序依次插入到链表的第一个节点之后,并使用队头指针
front
指向链表头节点位置,也就是队头元素,rear
指向链表尾部位置,也就是队尾元素。
基本操作
-
初始化空队列:创建一个空队列,定义队列的大小
size
,以及队头元素指针front
,队尾指针rear
。 -
判断队列是否为空:当队列为空时,返回
True
。当队列不为空时,返回False
。一般只用于队列中删除操作和获取队头元素操作中。 -
判断队列是否已满:当队列已满时,返回
True
,当队列未满时,返回False
。一般只用于顺序队列中插入元素操作中。 -
插入元素(入队):相当于在线性表最后元素后面插入一个新的数据元素。并改变队列顶指针
top
的指向位置。 -
删除元素(出队):相当于在线性表最后元素后面删除最后一个数据元素。并改变队列顶指针
top
的指向位置。 -
获取队列队头元素:相当于获取线性表中最后一个数据元素。与插入元素、删除元素不同的是,该操作并不改变队列顶指针
top
的指向位置。
广度优先遍历
广度优先搜索算法(Breadth First Search):简称为 BFS,又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始,沿着树的宽度遍历树或图的节点。如果所有节点均被访问,则算法中止。
广度优先遍历类似于树的层次遍历过程。呈现出一层一层向外扩张的特点。先看到的节点先访问,后看到的节点后访问。遍历到的节点顺序符合「先进先出」的特点,所以广度优先搜索可以通过「队列」来实现。
基于队列实现的广度优先搜索实现步骤
graph
为存储无向图的字典变量,start
为开始节点。- 然后定义
visited
为标记访问节点的 set 集合变量。定义q
为存放节点的队列。 - 首先将起始节点放入队列
q
中,即q.put(start)
。并将其标记为访问,即visited.add(start)
。 - 从队列中取出第一个节点
node_u
。访问节点node_u
,并对节点进行相关操作(看具体题目要求)。 - 遍历与节点
node_u
相连并构成边的节点node_v
。- 如果
node_v
没有被访问过,则将node_v
节点放入队列中,并标记访问,即q.append(node_v)
,visited.add(node_v)
。
- 如果
- 重复步骤 4 ~ 5,直到
q
为空。
参考:https://gitee.com/itcharge/LeetCode-Py
这篇关于队列和广度优先搜索的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-15Springboot应用的多环境打包学习
- 2024-10-15Springboot应用的生产发布学习
- 2024-10-15创建Springboot项目学习:新手入门教程
- 2024-10-15创建springboot项目学习:新手入门教程
- 2024-10-14Java创业学习:新手入门教程
- 2024-10-14JAVA创业学习:新手入门教程
- 2024-10-14Java创业学习:从零开始的Java编程教程
- 2024-10-14Java对接阿里云智能语音服务学习
- 2024-10-14JAVA对接阿里云智能语音服务学习教程
- 2024-10-14Java副业学习:从入门到实战的简单教程