|Algo| Breadth-First Search

Breadth-First Search, BFS.
It is a common algorithm applied on graph problems !!

Conditions:
1. N/A
2. graph problems ..

Mental cultivation:
1. Push initialized node into queue
2. pick up the first one, and remove from queue
3. find its neighbors
4. push those neighbors into queue.
5. until the queue is empty


Examples:
279 – Perfect Squares
286 – Walls and Gates
200 – Number of Islands
752 – Open the Lock

Template:
This template is modify from BFS – pattern.

/**
 * C++
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    queue<Node> queue;  // store all nodes which are waiting to be processed
    unordered_set<Node> visited;  // store all the nodes that we've visited
    step = 0;       // number of steps neeeded from root to current node

    // initialize
    add root to queue;
    add root to visited;

    // BFS
    while (queue is not empty) {
        step = step + 1;

        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = queue.front(); //the first node in queue
            queue.pop();// remove the first node from queue
            return step if cur is target;

            for (Node next : the neighbors of cur) {
                if (visited.count(next) == 0 /*next is not in visited*/) {
                    queue.push(next); //add next to queue
                    visited.insert(next); //add next to visited
                }  
            }
        }
    }

    return -1;  // there is no path from root to target
}



Ref.
BFS – pattern
https://www.youtube.com/watch?v=aQGfOXQFFeo