赞
踩
队列(queue)是一种采用先进先出(FIFO,first in first out)策略的抽象数据结构。比如生活中排队,总是按照先来的先服务,后来的后服务。队列在数据结构中举足轻重,其在算法中应用广泛,最常用的就是在宽度优先搜索(BFS)中,记录待扩展的节点。
队列内部存储元素的方式,一般有两种,数组(array)和链表(linked list)。两者的最主要区别是:
C++中,使用<queue>中的queue
模板类,模板需两个参数,元素类型和容器类型,元素类型必要,而容器类型可选,默认deque
,可改用list
(链表)类型。
队列的主要操作有:
push()
队尾追加元素front()
弹出队首元素size()
返回队列长度empty()
判断队列为空参考:https://blog.csdn.net/myloveqingmu/article/details/57084573
接口描述了类的行为和功能,而不需要完成类的特定实现。
C++ 接口是使用抽象类来实现的,抽象类与数据抽象互不混淆,数据抽象是一个把实现细节与相关的数据分离开的概念。
如果类中至少有一个函数被声明为纯虚函数,则这个类就是抽象类。
设计抽象类(通常称为 ABC)的目的,是为了给其他类提供一个可以继承的适当的基类。抽象类不能被用于实例化对象,它只能作为接口使用。如果试图实例化一个抽象类的对象,会导致编译错误。
因此,如果一个 ABC 的子类需要被实例化,则必须实现每个虚函数,这也意味着 C++ 支持使用 ABC 声明接口。如果没有在派生类中重载纯虚函数,就尝试实例化该类的对象,会导致编译错误。
可用于实例化对象的类被称为具体类。
注重独一无二,该体系集合可以知道某物是否已经存在于集合中,不会存储重复的元素。Set的实现类在面试中常用的是:
set:
unordered_set:
Map用于存储具有映射关系的数据。Map中存了两组数据(key
与value
),它们都可以是任何引用类型
的数据,key
不能重复,我们可以通过key
取到对应的value
。Map的实现类在面试中常用是:
map:
key
无重复,value
允许重复unordered_map:
key
无重复,value
允许重复key
和 value
为空
一个 List 是一个元素有序的、可以重复(这一点与Set和Map不同)、可以为 null 的集合,List的实现类在面试中常用是:list 和 vector
List:
Vector:
List与 Vector对比:
get
和set
,Vector绝对优于List,因为List要移动指针add
和remove
,List比较占优势,因为Vector要移动数据
队列是一种比较重要的数据结构,它支持FIFO(First in First out),即尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。
图的遍历,比如给出无向连通图(Undirected Connected Graph)中的一个点,找到这个图里的所有点。这就是一个常见的场景。
LintCode 上的 Clone Graph 就是一个典型的练习题。
更细一点的划分的话,这一类的问题还可以分为:
层级遍历,也就是说我不仅仅需要知道从一个点出发可以到达哪些点,还需要知道这些点,分别离出发点是第几层遇到的,比如 Binary Tree Level Order Traversal time: O(N), space: O(N)就是一个典型的练习题。
由点及面,前面已经提到。
拓扑排序,让我们在后一节中展开描述。
最短路径算法有很多种,BFS 是其中一种,但是他有特殊的使用场景,即必须是在简单图中求最短路径。
大部分简单图中使用 BFS 算法时,都是无向图。当然也有可能是有向图,但是在面试中极少会出现。
什么是简单图(Simple Graph)?
即,图中每条边长度都是1(或边长都相同)。
BFS 大部分的时候是在图上进行的。
图在离线数据中的表示方法为 <E, V>
,E表示 Edge,V 表示 Vertex。也就是说,图是顶点(Vertex)和边(Edge)的集合。
二叉树中进行 BFS 和图中进行 BFS 最大的区别就是二叉树中无需使用 unordered_map 来存储访问过的节点(丢进过 queue 里的节点)
因为二叉树这种数据结构,上下层关系分明,没有环(circle),所以不可能出现一个节点的儿子的儿子是自己的情况。
但是在图中,一个节点的邻居的邻居就可能是自己了。
[[1],[0,2,3],[1],[1]]
这个图表示 0 和 1 之间有连边,1 和 2 之间有连边,1 和 3 之间有连边。即每个点上存储自己有哪些邻居(有哪些连通的点)。
这种方式下,空间耗费和边数成正比,可以记做 O(m),m代表边数。m最坏情况下虽然也是 O(n^2),但是邻接表的存储方式大部分情况下会比邻接矩阵更省空间。
自定义邻接表
可以用自定义的类来实现邻接表
- class DirectedGraphNode {
- int label;
- vector<DirectedGraphNode> neighbors;
- ...
- }
其中 neighbors 表示和该点连通的点有哪些。
使用 Map 和 Set(面试时)
也可以使用 HashMap 和 HashSet 搭配的方式来存储邻接表
unordered_map<T, unordered_set<T>> = new unordered_map<int, unordered_set<int>>();
其中 T 代表节点类型。通常可能是整数(Integer)。
这种方式虽然没有上面的方式更加直观和容易理解,但是在面试中比较节约代码量。
在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序(英语:Topological sorting)。
也可以定义为:拓扑排序是对有向无环图的顶点的一种排序,它使得如果存在一条从顶点A到顶点B的路径,那么在排序中B出现在A的后面。
确切的说,一张图的拓扑序列可以有很多个,也可能没有
。拓扑排序只需要找到其中一个
序列,无需找到所有
序列。
拓扑排序的算法是典型的宽度优先搜索算法,其大致流程如下:
依赖
的点,放到宽度优先搜索的队列中拓扑排序时间复杂度:
O(n+m)。
每个顶点只入栈一次,出栈一次,所以是n次。每个点会更新与它相关的边,每条边被考虑一次。所以总共是m次。
什么时候需要分层遍历?
我们可以将当前层的所有节点存在第一个队列中,然后拓展(Extend)出的下一层节点存在另外一个队列中。来回迭代,逐层展开。这个方法更能体现BFS分层的效果
- Queue<T> queue1 = new LinkedList<>();
- Queue<T> queue2 = new LinkedList<>();
- queue1.offer(startNode);
- int currentLevel = 0;
-
- while (!queue1.isEmpty()) {
- int size = queue1.size();
- for (int i = 0; i < size; i++) {
- T head = queue1.poll();
- for (all neighbors of head) {
- queue2.offer(neighbor);
- }
- }
- Queue<T> temp = queue1;
- queue1 = queue2;
- queue2 = temp;
-
- queue2.clear();
- currentLevel++;
- }
双向宽度优先搜索 (Bidirectional BFS) 算法适用于如下的场景:
以上 3 个条件都满足的时候,可以使用双向宽度优先搜索来求出起点和终点的最短距离。
双向宽度优先搜索本质上还是BFS,只不过变成了起点向终点和终点向起点同时进行扩展,直至两个方向上出现同一个子节点,搜索结束。我们还是可以利用队列来实现:一个队列保存从起点开始搜索的状态,另一个保存从终点开始的状态,两边如果相交了,那么搜索结束。起点到终点的最短距离即为起点到相交节点的距离与终点到相交节点的距离之和。
Q.双向BFS是否真的能提高效率?
假设单向BFS需要搜索 N 层才能到达终点,每层的判断量为 X,那么总的运算量为X ^ N. 如果换成是双向BFS,前后各自需要搜索 N / 2 层,总运算量为 2 * X ^ {N / 2}。如果 N 比较大且X 不为 1,则运算量相较于单向BFS可以大大减少,差不多可以减少到原来规模的根号的量级。
如果在面试中被问到了如何优化 BFS 的问题,Bidirectional BFS 几乎就是标准答案了。
- /**
- * Definition for graph node.
- * class UndirectedGraphNode {
- * int label;
- * ArrayList<UndirectedGraphNode> neighbors;
- * UndirectedGraphNode(int x) {
- * label = x; neighbors = new ArrayList<UndirectedGraphNode>();
- * }
- * };
- */
- public int doubleBFS(UndirectedGraphNode start, UndirectedGraphNode end) {
- if (start.equals(end)) {
- return 1;
- }
- // 起点开始的BFS队列
- Queue<UndirectedGraphNode> startQueue = new LinkedList<>();
- // 终点开始的BFS队列
- Queue<UndirectedGraphNode> endQueue = new LinkedList<>();
- startQueue.add(start);
- endQueue.add(end);
- int step = 0;
- // 记录从起点开始访问到的节点
- Set<UndirectedGraphNode> startVisited = new HashSet<>();
- // 记录从终点开始访问到的节点
- Set<UndirectedGraphNode> endVisited = new HashSet<>();
- startVisited.add(start);
- endVisited.add(end);
- while (!startQueue.isEmpty() || !endQueue.isEmpty()) {
- int startSize = startQueue.size();
- int endSize = endQueue.size();
- // 按层遍历
- step ++;
- for (int i = 0; i < startSize; i ++) {
- UndirectedGraphNode cur = startQueue.poll();
- for (UndirectedGraphNode neighbor : cur.neighbors) {
- if (startVisited.contains(neighbor)) {//重复节点
- continue;
- } else if (endVisited.contains(neighbor)) {//相交
- return step;
- } else {
- startVisited.add(neighbor);
- startQueue.add(neighbor);
- }
- }
- }
- step ++;
- for (int i = 0; i < endSize; i ++) {
- UndirectedGraphNode cur = endQueue.poll();
- for (UndirectedGraphNode neighbor : cur.neighbors) {
- if (endVisited.contains(neighbor)) {
- continue;
- } else if (startVisited.contains(neighbor)) {
- return step;
- } else {
- endVisited.add(neighbor);
- endQueue.add(neighbor);
- }
- }
- }
- }
- return -1; // 不连通
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。