seen.insert(start); que.push(start); while (!que.empty()) { const T &head = que.front(); que.pop(); for (const T &neighbor : head.neighbors) { if (!seen.count(neighbor)) { //check whether already visited seen.insert(neighbor); //insert the just-visited node into visited set que.push(neighbor); //push into Queue-to-explore(存储等待被拓展到下一层的节点) } } } //set/seen 与 queue 是一对好基友，无时无刻都一起出现，往 queue 里新增一个节点，就要同时丢到 set 里。
queue<T> q1, q2; q1.push(startNode); int level = 0;
while (!q1.empty()) { intsize = q1.size(); for (int i = 0; i < size; i++) { T head = q1.front(); q1.pop(); for (all neighbors of head) { q2.push(neighbor); } } q1 = q2; //直接通过将q1替换为q2，实现到下一层的转换 level++; }
使用 dummy node 来间隔不同的层级。
Dummy Node 一般本身不存储任何实际有意义的值，通常用作"占位"，或者链表的“虚拟头”。如很多的链表问题中，我们会在原来的头head的前面新增一个节点，这个节点没有任何值，但是 next 指向 head。这样就会方便对 head 进行删除或者在前面插入等操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
queue<T> q; q.push(startNode); q.push(NULL); int level = 0;
// 因为有 dummy node 的存在，不能再用 isEmpty 了来判断是否还有没有拓展的节点了 while (q.size() > 1) { T head = q.front(); q.pop(); if (head == NULL) { level++; q.push(NULL); continue; } for (all neighbors of head) { q.push(neighbor); } }
Summary
能用BFS的时候一定不要用DFS(除非面试官有特别要求)
找所有连通图（块）的问题，相当于是==找所有点，用BFS==。
找所有排列的问题，相当于是==找所有路径，用DFS==。
BFS的三中使用情况：
图的遍历(由点及面，层级遍历)
简单图最短路径
==拓扑排序必须掌握!!!== (依据indegree和outdegree的概念)
是否需要层级遍历
size = queue.size()
坐标变化数组：
deltaX, deltaY
inBound
图的遍历
Binary Tree Level Order Traversal（层级遍历）
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
classSolution { private: vector<int> delta_x = {-1, 0, 1, 0}; vector<int> delta_y = {0, -1, 0, 1}; public: intnumIslands(vector<vector<bool>> &grid){ int m = grid.size(); int n = m > 0 ? grid[0].size() : 0; if (m == 0) return0; int count = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 0) continue; bfs(grid, i, j); //由点及面 count++; } } return count; } //bfs traversal（由点及面） voidbfs(vector<vector<bool>> & grid, int r, int c){ int m = grid.size(), n = grid[0].size(); //调用此函数时m肯定是不为0的 queue<pair<int, int>> q; q.push({r, c}); grid[r][c] = 0; //note as visited by modifying into 0 while(!q.empty()) { intsize = q.size(); for (int i = 0; i < size; i++) { pair<int, int> curr = q.front(); q.pop(); //explore neighbors for (int j = 0; j < 4; j++) { pair<int, int> next(curr.first + delta_x[j], curr.second + delta_y[j]); if (next.first < 0 || next.first >= m || next.second < 0 || next.second >= n) { continue; } if (grid[next.first][next.second] == 1) { q.push(next); grid[next.first][next.second] = 0; //note as visited by modifying into 0 } } } } } };
Serialize and Deserialize Binary Tree (层级遍历)
Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called serialization and reading back from the file to reconstruct the exact same binary tree is deserialization.
serialize: This method will be invoked first, you should design your own algorithm to serialize a binary tree which denote by a root node to a string which can be easily deserialized by your own "deserialize" method later.
deserialize: This method will be invoked second, the argument data is what exactly you serialized at method "serialize", that means the data is not given by system, it's given by your own serialize method. So the format of data is designed by yourself, and deserialize it here as you serialize it in "serialize" method.
//假设单向BFS需要搜索 N 层才能到达终点，每层的判断量为 X，那么总的运算量为 X ^ N. 如果换成是双向BFS，前后各自需要搜索 N / 2 层，总运算量为 2 * X ^ {N / 2} 。如果 N 比较大且X 不为 1，则运算量相较于单向BFS可以大大减少，差不多可以减少到原来规模的根号的量级。
intdoubleBFS(Node * start, Node * end){ if (start == end) return1; queue<Node> startQ, endQ; startQ.push(start); endQ.push(end); unordered_set<Node> startVisited, endVisited; startVisited.insert(start); endVisited.insert(end); intstep = 0; while (!startQ.empty() || !endQ.empty()) { int startSize = startQ.size(); step++; for (int i = 0; i < startSize; i++) { Node * curr = startQ.front(); startQ.pop(); for (Node * neighbor : curr->neighbors) { if (startVisited.count(neighbor)) { //重复节点 continue; } if (endVisited.count(neighbor)) { //相交 returnstep; } startQ.push(neighbor); startVisited.insert(neighbor); } } int endSize = endQ.size(); step++; for (int i = 0; i < endSize; i++) { Node * curr = endQ.front(); endQ.pop(); for (Node * neighbor : curr->neighbors) { if (endVisited.count(neighbor)) { //重复节点 continue; } if (startVisited.count(neighbor)) { //相交 returnstep; } endQ.push(neighbor); endVisited.insert(neighbor); } } } return-1; //不连通 }
Word Ladder（隐式简单图）
Given two words (start and end), and a dictionary, find the shortest transformation sequence from start to end, output the length of the sequence. Transformation rule such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary. (Start and end words do not need to appear in the dictionary )
# 自己的solution：BFS traverse nodes level by level; return level + 1 when the next node matches end. # 一个难点在于：Implicit BFS - 要自己去构建graph，这里的每个node是string class Solution { public: int ladderLength(string &start, string &end, unordered_set<string> &dict) { if (start == end) return1; //corner case int count = 1; queue<string> q; q.push(start); if (dict.find(start) != dict.end()) dict.erase(start); //通过erase已经访问过的string来记录为visited while(!q.empty()) { //开始bfs int n = q.size(); for (int i = 0; i < n; i++) { string curr = q.front(); q.pop(); //explore neighbors of curr for (int i = 0; i < curr.size(); i++) { //枚举替换位置 for (int j = 0; j < 26; j++) { //枚举替换字母 string tmp = curr; if (tmp[i] == 'a' + j) continue; tmp[i] = 'a' + j; if (tmp == end) return count + 1; if (dict.find(tmp) != dict.end()) { q.push(tmp); dict.erase(tmp); //通过erase已经访问过的string来记录为visited } } } } count++; //count levels traversed during bfs } return0; } };
Knight Shortest Path（grid简单图）
Given a knight in a chessboard (a binary matrix with 0 as empty and 1 as barrier) with a source position, find the shortest path to a destination position, return the length of the route. Return -1 if destination cannot be reached.
// seqs里的seq是sequence的subsequence，比如[1, 2]，这意味着1指向2。 // 判断是否有Unique Topological Order：每次iteration的时候queue里只有一个node，其他的做法和general的类似。 classSolution { public: /** * @param org: a permutation of the integers from 1 to n * @param seqs: a list of sequences * @return: true if it can be reconstructed only one or false */ boolsequenceReconstruction(vector<int> &org, vector<vector<int>> &seqs){ int n = org.size(); int count = 0; //count the total length of all seqs unordered_map<int, unordered_set<int>> graph; vector<int> indegree(n); for (vector<int> seq : seqs) { count += seq.size(); if (seq.size() >= 1 && (seq[0] < 1 || seq[0] > n)) returnfalse; for (int i = 1; i < seq.size(); i++) { if (seq[i] < 1 || seq[i] > n) returnfalse; //避免重复计算indegree，比如这个case: [[5,2,6,3],[4,1,5,2]] 5->2有两次 if (graph[seq[i - 1]].count(seq[i]) == 0) { graph[seq[i - 1]].insert(seq[i]); //相邻node之间有前后指向关系 indegree[seq[i] - 1]++; //node n 对应到 indegree的第n-1位 } } } /*case: [1] [] */ if (count < n) returnfalse; queue<int> q; for (int i = 0; i < indegree.size(); i++) { if (indegree[i] == 0) q.push(i + 1); } int k = 0; while(q.size() == 1) { //queue should always have only one node int curr = q.front(); q.pop(); for (int next : graph[curr]) { indegree[next - 1]--; if (indegree[next - 1] == 0) q.push(next); } if (curr != org[k]) returnfalse; //而且唯一的那一个要和unique order里的对应node一样 k++; } return k == n; } };
