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