I want to find the shortest path (least number of edges) between two nodes in an unweighted graph.
How do I implement this by using a
BFSiterator(v) which returns vertices in BFS order, starting from node v? The graph interface only allows the function
neighbours(v) (to get the neighbour vertices of v) to be used. This was a homework exercise long ago, but I couldn't find an answer.
I am kind of stuck since I am not sure how to detect when a new level in the graph is reached, since the BFS iterator only return vertices. Simply collecting all vertices from the start to end node in BFS order does not work, since this would contain sibling vertices as well which are not on the shortest path.
Thanks in advance.