Prove that, BFS (Breadth First Search) visits all vertices reachable from V.
|NU Year||Set: 4.(b) Marks: 4 Year: 2008|
Breadth-first search assigns two values to each vertex:
- A distance, giving the minimum number of edges in any path from the source vertex to vertex v.
- The predecessor vertex of v 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 v, then v'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
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. Then we visit all the neighbors of the source and give each neighbor a distance of 1 and set its predecessor to be the source. Then we visit all the neighbors of the vertices whose distance is 1 and that have not been visited before, and we give each of these vertices a distance of 2 and set its predecessor to be vertex from which we visited it. We keep going until all vertices reachable from the source vertex have been visited, always visiting all vertices at distance k from the source before visiting any vertex at distance k, plus, 1.
Given the example above, here are the steps plus a visualization to play through each step:
- Start by visiting vertex 3, the source, setting its distance to 0.
- Then visit vertices 2 and 6, setting their distance to 1 and their predecessor to vertex 3.
- Start visiting from vertices at distance 1 from the source, beginning with vertex 2. From vertex 2, visit vertices 4 and 5, setting their distance to 2 and their predecessor to vertex 2. Don't visit vertex 3, because it has already been visited.
- From vertex 6, don't visit vertex 5, because it was just visited from vertex 2, and don't visit vertex 3, either.
- Now start visiting from vertices at distance 2 from the source. Start by visiting from vertex 4. Vertex 2 has already been visited. Visit vertex 1, setting its distance to 3 and its predecessor to vertex 4.
- From vertex 5, don't visit any of its neighbors, because they have all been visited.
- Now start visiting from vertices at distance 3 from the source. The only such vertex is vertex 1. Its neighbors, vertices 4 and 5, have already been visited. But vertex 0 has not. Visit vertex 0, setting its distance to 4 and its predecessor to vertex 1.
- Now start visiting from vertices at distance 4 from the source. That's just vertex 0, and its neighbor, vertex 1, has already been visited. We're done!
Login to post your comment.