Breadth-first Search (BFS)

Concept

Two main scenarios of using BFS: do traversal or find the shortest path. Typically, it happens in a tree or a graph.

In tree/graph traversal: It's level-order traversal, the nodes closer to the root node will be traversed earlier

In finding shortest path: If a node X is added to the queue in the kth round, the length of the shortest path between the root node and X is exactly k.

Implementation

1.Queue

2.Queue + set (avoiding cycle)

Template

Find the length of a shortest path from root to target.

Every time, you move down one level down, in this case, you will find the shortest length from root to target.

class Solution { public: int bfs(Node* root, Node* target) { qeueu<Node*> q; q.push(root); int step = 0; while(!q.empty()) { step++; //move down one level int n = q.size(); for(int i = 0 ; i < n ; i++) { Node* cur = q.front(); q.pop(); if(cur == target) return step; for(Node next: the neighbors of cur) { q.push(next); } } } return -1; //there is no path from root to target } };

Template II

Avoid cycle in a graph.

class Solution { public: int bfs(Node* root, Node* target) { qeueu<Node*> q; set<Node*>visited; int step = 0; //initialize q.push(root); visited.insert(root); while(!q.empty()) { step++; int n = q.size(); for(int i = 0 ; i < n ; i++) { Node* cur = q.front(); q.pop(); if(cur == target) return step; for(Node next : the neighbors of cur) { //not found if(visited.count(next) == 0) { q.push(next); visited.insert(next); } } } } //no such path from root to target return -1; } };

[Medium] No.279 Perfect Squares

Approach: BFS + greedy

Time Complexity: O(N^h/2), where h is the maximal number of recursion that could happen.

Space Complexity: check the link.

class Solution { public: int numSquares(int n) { //construct data base set<int> uset; for(int i = 1 ; i * i <= n ; i++) { uset.insert(i*i); } queue<int> q; //store remain number unordered_set<int> next_queue; //avoid duplicate numbers q.push(n); int step = 0; while(!q.empty()) { step++; int siz = q.size(); for(int j = 0 ; j < siz ; j++) { int cur = q.front(); q.pop(); for(auto it = uset.begin() ; it != uset.end() ; it++) { if(uset.count(cur) != 0) return step; if(cur > *it) { next_queue.insert(cur - *it); } } } //move set into queue for(auto itt = next_queue.begin() ; itt != next_queue.end() ; itt++) { q.push(*itt); } } return step; } };

[Medium] No.103 Binary Tree Zigzag Level Order Traversal

Approach: BFS

Time Complexity: O(N), where N is the number of nodes in the tree.

Space Complexity: O(N), where N is the number of nodes in the tree.

class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { if(root == NULL) return {}; queue<TreeNode*> q; q.push(root); vector<vector<int>> ans; while(!q.empty()) { int siz = q.size(); vector<int> temp; for(int i = 0 ; i < siz ; i++) { TreeNode* cur = q.front(); q.pop(); temp.push_back(cur->val); if(cur->left != NULL) q.push(cur->left); if(cur->right != NULL) q.push(cur->right); } ans.push_back(temp); } //reverese odd index order for(int j = 1 ; j < ans.size() ; j+=2) { reverse(ans[j].begin(), ans[j].end()); } return ans; } };