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.
BFSiterator
? What doesneighbours
return? etc $\endgroup$ – padawan Nov 10 '16 at 12:14BFSiterator(v)
implements anIterator<Vertex>
which returns vertices of the graph in BFS order, traversed fromv
.neighbours(v)
returns aCollection<Vertex>
of direct neighbours of the given vertexv
. $\endgroup$ – Laurens Nov 10 '16 at 12:17