The breadth-first search algorithm

Breadth-first search assigns two values to each vertex vv:

  • distance, giving the minimum number of edges in any path from the source vertex to vertex vv.

  • The predecessor vertex of vv 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 vv, then vv'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 00 to 77, with vertex numbers appearing above or below the vertices. Inside each vertex are two numbers: its distance from the source, which is vertex 33, followed by its predecessor on a shortest path from vertex 33. A dash indicates null:

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy