Breadth First Search (BFS)
Breadth-first search assigns two values to each vertex v: A distance, giving the minimum number of edges in any path from the source vertex to vertex vvv. The predecessor vertex of vvv along some shortest path from the source vertex. The source vertex's predecessor is some special value, such as null, indicating that it has no predecessor. If there is no path from the source vertex to vertex vvv, then vvv's distance is infinite and its predecessor has the same special value as the source's predecessor. For example, here's an undirected graph with eight vertices, numbered 0 to 7, with vertex numbers appearing above or below the vertices. Inside each vertex are two numbers: its distance from the source, which is vertex 3, followed by its predecessor on a shortest path from vertex 3. A dash indicates null: In BFS, we initially set the distance and predecessor of each vertex to the special value (null). We start the search at the source and assign it a distance of 0. ...