队列与BFS的简单介绍
队列
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列具有先进先出的特点。
如图
当在队列中进行读取操作(front)时,会读取队首元素,也就是元素1,使用pop时删除的也是队首元素,经过front与pop操作,队列会变成
而进行插入操作,则会在队尾执行,假设执行push操作,添加元素5,会出现
使用队列时需头文件queue
#include<queue>
定义变量
queue<int>q //括号内为队列的变量类型
队列的一些操作函数的简单使用
q.front()//取队列中第一个元素
q.pop()//删除队列中第一个元素
q.empty()//判断队列是否为空,为空时返回1;
q.push()//将某元素插入队列
BFS即广度优先搜索,是最简便的图的搜索算法之一,这种方法不考虑需要查找的具体结果,就是从某一点出发遍历整个图,直到找到结果。所谓广度优先搜索,就是从某一点出发,优先搜索与其相邻的点,搜索完成之后,继续搜索已经搜索过的相邻点的相邻点。举个栗子
观察下面二叉树(就是每个点的下方只有两条分叉的图)
当从树的顶点a开始搜索时,设a是第一层的元素。优先搜索其相邻点,就是b和c,也就是第二层元素。搜索完a的相邻节点(第二层元素搜索结束),继续搜索其相邻点的相邻节点(第三层元素,已搜索过不需搜索),就是搜索b的相邻节点d与e,完成后搜索c的相邻节点。这个过程我是利用队列来完成的,利用队列先进先出的特点,不使用队列也可以。(个人觉得使用队列解决BFS问题超级方便)
广度优先搜索,不太合理的讲,就是一层一层的搜索(不搜索完就不进入下一层的搜索),搜索完一层,紧接着搜索下一层,与其对应的是深度优先搜索(DFS),像是一条路走到黑的倔驴。
以上均为个人观点,仅是对队列的一些简单使用及BFS的理解,如有错误请指出,勿喷,不胜感激
---------------------------------------------------------------------------一只走在ACM路上的弱渣