面试刷题：广度优先搜索BFS
By 青衣极客 Blue Geek In 2020-05-06
前面已经有一篇文章讨论了深度优先搜索DFS，从逻辑结构上而言，还有一种与之相对的遍历方式，广度优先搜索(Breath First Search, BFS)。DFS是指优先向孩子节点前进，那么广度优先搜索BFS就是优先向兄弟节点前进。 我们知道递归结构天然地就是往更深层调用前进的，因此很适合用于实现DFS，而广度优先搜索可能就稍显复杂一点，因为它需要备份兄弟节点的孩子节点，以便后续访问。这里打算讨论一下广度优先搜索的一般逻辑形式和实现方式，最后会给出一个稍微复杂一点的运用BFS的例子。
1. 二叉树的层次遍历 Q102
Leetcode Q102 是这样一个问题：给定一个二叉树，返回其节点值的级别顺序遍历。即，从左到右，逐级递进）。我们首先来看一个输入输出的示例：
从示例中可以看出，所谓层次遍历，就是首先对同一深度的节点按照从左到右排序，然后再按照深度从小到大排列。从人类思维而言，这似乎并没有什么难点，但是对于计算机实现而言，我们必须明确每一步细节。
2. Q102的BFS解决思路
从题意可以看出，这种遍历要求优先访问同深度的节点，符合广度优先搜索BFS的特点，事实上也是为BFS量身定制的。BFS要求优先访问兄弟节点，那么孩子节点就需要备份起来。 并且，为了后续取出孩子节点时的顺序符合要求，我们必须保证使用一种“先进先出”的数据结构来进行备份，即“队列”。
也就是说，在实现BFS时，使用队列来备份孩子节点是必不可少的。 如果使用的数据结构不是队列，那么就需要在操作时按照队列的“先进先出FIFO”的规则来进行读写，或者保证具体情况要求的序。接下来，还是看一下二叉树层次遍历这个问题的BFS实现的解决思路：
图中首先将根节点压入队列，由于深度为0的这一层只有根节点一个，因此直接将根节点弹出，然后遍历根节点，并将其左右孩子节点依次压入队列。
接下来就开始遍历深度为1的节点。依次从队列中弹出节点，并访问其内容，然后将孩子节点压入队列。一直到整个队列为空，则遍历完成。
3. Q102的BFS解决方案
以上BFS解决二叉树层次遍历问题的C++解决方案如下：
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ret;
if (!root) {return ret;}
vector<int> mid;
// create a queue to store children nodes
queue<TreeNode*> buff;
buff.push(root);
while (buff.size() > 0) {
mid.clear();
// traversal nodes with the same level
for (int i = buff.size(); i > 0; --i) {
auto * node = buff.front(); buff.pop();
mid.push_back(node->val);
// add child nodes to the buff
if (node->left) {buff.push(node->left);}
if (node->right) {buff.push(node->right);}
}
ret.push_back(mid);
}
return ret;
}
};
以上解决方案中有一个小技巧，即利用队列大小作为当前层元素个数。 需要这样做是因为有必要区分队列中的哪些元素属于当前层，哪些元素是孩子节点。这一点在具体实现时方式各异，但总是需要进行这样的区分的。
这里使用循环来实现，当然也可以使用递归来实现，具体的实现方式需要在具体的问题下作出选择，这里使用循环更简单一些。
看过上面解决方案和解决思路这么简单，大家可能以为万事大吉了。但实际使用并非如此。因为树型结构没有环，也就是说遍历过程中不会遇到重复节点。而对于图的BFS遍历就更加复杂一点。
4. 获取朋友观看的视频 Q1311
了解BFS的基本思想并不是太困难，真正困难的是在实际中的运用。这里以【Leetcode Q1311 获取朋友观看的视频】为例来简要讨论一下BFS解题的过程。
题目：有n个人，每个人都有一个介于0到n-1之间的唯一ID。给定数组 watchedVideos 和 friends， 其中 watchedVideos[i] 和 friends[i]分别包含id = i的人的观看视频列表和朋友列表。 级别1的视频是您的朋友观看的所有视频，级别2的视频是您的朋友的观看的所有视频，依此类推。 通常，视频级别k都是由最短路径恰好等于k的人观看的视频。 根据您的ID和视频级别， 返回按其频率排序（递增）的视频列表。对于相同频率的视频，请按从小到大的字母顺序排列。
约束条件：
(a) n == watchedVideos.length == friends.length
(b) 2 <= n <= 100
(c) 1 <= watchedVideos[i].length <= 100
(d) 1 <= watchedVideos[i][j].length <= 8
(e) 0 <= friends[i].length < n
(f) 0 <= friends[i][j] < n
(g) 0 <= id < n
(h) 1 <= level < n
(i) 如果friends[i] 包含 j, 则 friends[j] 包含 i
从题目的要求和约束条件可以看出，从数据结构上来讲，这是一个无向图的问题，即朋友关系是对称的，A是B的朋友，则B也是A的朋友。
关于这个问题，首先来看两个示例：
从示例图看出，一级朋友关系很好说，二级朋友关系，即朋友的朋友，就有些麻烦。输入的数据已经保证了这是一张无向图，因此不需要进行相关的检查。
5. Q1311的BFS解决思路
根据Q1311的题意，在找到第k级朋友这一步应该使用广度优先搜索BFS，至于其他的只是排序的问题，不是本文讨论的重点，有疑惑的朋友待会儿直接看解决方案即可。
我们来看一下BFS的思路示意图：
首先，将指定的起始人物压入队列，然后弹出该起始人物，并将其一级朋友压入队列。然后依次弹出一级朋友，并将一级朋友的朋友压入队列，如此类推迭代。这里我们需要找到人物 0 的二级朋友，发现只有人物 3，因为其他的朋友都是一级朋友。
这个简单的示意图中，还包括了一个很重要的处理 —— 去重。即人物3的朋友人物1和人物2之所以没有被压入队列，是因为他们已经是人物0的一级朋友。
这是图结构相对于树结构在使用BFS遍历时需要解决的一个特殊的问题，而这个问题也往往会成为一个难点。
6. Q1311的BFS解决方案
使用BFS找到第k级朋友之后，就可以获得这些人物喜欢的电影，然后按照喜欢的人数进行投票排序即可。 关于投票排序这一点，我们首先需要一个辅助的仿函数，这个函数的目的是在对电影进行排序时，区分谁前谁后。
class Comp {
private:
unordered_map<string, int> * _dict;
public:
Comp(unordered_map<string, int> * dict) {
_dict = dict;
}
bool operator()(const string & a, const string & b) {
if ((*_dict)[a] == (*_dict)[b]) {
return a < b;
}
return (*_dict)[a] < (*_dict)[b];
}
};
以上代码中，传入的dict就是存储了投票信息的map结构数据。
解决方案的主体部分如下：
class Solution {
public:
vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
// bfs, get all level-th friends
unordered_set<int> lf, notlf, oldf(friends[id].begin(), friends[id].end()), newf;
notlf.insert(id);
while (level) {
newf.clear();
if (1 != level) {
for (auto & i : oldf) {
if (i == id) {
continue;
}
notlf.insert(i);
for (auto & k : friends[i]) {
newf.insert(k);
}
}
oldf = newf;
} else {
for (auto & i : oldf) {
if (!notlf.count(i)) {
lf.insert(i);
}
}
}
--level;
}
// count frequency of movies
unordered_map<string, int> dict;
for (auto & v : lf) {
for (auto & m : watchedVideos[v]) {
++dict[m];
}
}
vector<string> ret;
ret.reserve(dict.size());
for (auto & kv : dict) {
// std::cout << kv.first << "," << kv.second << std::endl;
ret.push_back(kv.first);
}
// sort
Comp comp(&dict);
sort(ret.begin(), ret.end(), comp);
return ret;
}
};
以上实现中，首先将起始人物的一级朋友放入set中。大家都知道set的元素在数学上应该是无序的，与前面要求的“先进先出FIFO”是矛盾的，那么为什么还要用set呢？
因为在这个问题中属于同一级别的朋友的访问顺序是没有要求的，但是对于新加入的朋友的查重的需求比较强烈，使用set主要是为了避免对重复的朋友进行访问。
从逻辑结构上说，BFS与DFS并列为两大典型的遍历方式，也是在处理树或者图相关问题时的常用解题思想。DFS在实现上更加直观一些，而BFS则需要考虑使用“队列”来备份孩子节点。这里的“队列”在具体问题的实现中可以存在一些差异，但基本的思路是一致的。
COMMENT
博客评论区功能由Github Issue提供，提交Issue时请以本文标题为话题。
"BG100-面试刷题：广度优先搜索BFS"