Write down BFS algorithm.

Subject | Algorithm Design |
---|---|

NU Year | Set: 3.(d) Marks: 5 Year: 2009 |

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 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.

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 the 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. 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 KKK from the source before visiting any vertex at distance k, plus, 1.
Login to post your comment.