April 2018
Beginner to intermediate
426 pages
10h 19m
English
So far, we have only demonstrated how the BFS algorithm works. We can use it for more things than just outputting the order of vertices visited. For example, how would we solve the following problem?
Given a graph G and the source vertex v, find the distance (number of edges) from v to each vertex u∈ G along the shortest path between v and u.
Given a vertex v, the BFS algorithm visits all the vertices with distance 1, then distance 2, and so on. So, we can use the BFS algorithm to solve this problem. We can modify the breadthFirstSearch function to return some information for us: