Breadth First Search

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.

BFS was invented in the late 1950s by E. F. Moore, who used it to find the shortest path out of a maze, and discovered independently by C. 

• Search for all vertices  that are directly reachable from the root (called level 1 vertices)
• After mark all these vertices, visit all vertices that are directly reachable from any level 1 vertices (called level 2 vertices), and so on.
• In general, level k vertices are directly reachable from a level k – 1 vertices

1. White vertices have not been discovered ( All vertices start out white )
2. Grey vertices are discovered but not fully explored ( They may be adjacent to white vertices)
3. Black vertices are discovered and fully explored (They are adjacent only to black and gray vertices)
4. Explore vertices by scanning adjacency list of grey vertices

Applications:
Breadth-first search can be used to solve many problems in graph theory, for example:

• Copying garbage collection, Cheney's algorithm
• Finding the shortest path between two nodes u and v (with path length measured by number of edges)
• Testing a graph for bipartiteness 
• (Reverse) Cuthill–McKee mesh numbering
• Ford–Fulkerson method for computing the maximum flow in a flow network
• Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
• Construction of the failure function of the Aho-Corasick pattern matcher.