0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ As a hint, I would say you should use a data structure instead of a simple iterator. $\endgroup$ – padawan Nov 10 '16 at 12:03
  • $\begingroup$ I have refined my question. It is based on a former homework exercise. $\endgroup$ – Laurens Nov 10 '16 at 12:05
  • $\begingroup$ You should "mark" the nodes in order to detect if they are visited before or not. I am not sure if this is what you ask. Maybe I can help more if you state the question in a formal way. What is the purpose of BFSiterator? What does neighbours return? etc $\endgroup$ – padawan Nov 10 '16 at 12:14
  • $\begingroup$ BFSiterator(v) implements an Iterator<Vertex> which returns vertices of the graph in BFS order, traversed from v. neighbours(v) returns a Collection<Vertex> of direct neighbours of the given vertex v. $\endgroup$ – Laurens Nov 10 '16 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.