I understand how BFS can give the shortest path in a graph but I am not able to code the entire thing. The part where I am stuck is when I pop a node from the queue and see that its the target node, how do I trace back the complete path of nodes that led to the target? In simple BFS we only have a queue but I think in this case we need some other data structure as well to keep track of path? What would be the efficient way to do that? Thank you!

  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Mar 14 '17 at 21:08
  • 1
    $\begingroup$ I'd like to think that every algorithms textbook or otherwise decent resource would cover this. Where have you looked? $\endgroup$ – Raphael Mar 14 '17 at 21:08
  • 1
    $\begingroup$ Welcome! I suggest you do more research before asking in the future. Looking in standard resources (e.g., textbooks) is a good idea. This topics is covered well in standard algorithms textbooks; in the textbooks I've seen, the chapter on shortest paths algorithms describes how to extend any algorithm for computing distances (the length of the shortest path) to recover the path itself. See also the parent links in Wikipedia: en.wikipedia.org/wiki/Breadth-first_search#Pseudocode. There's little point in us repeating material that's already explained well in standard resources. $\endgroup$ – D.W. Mar 14 '17 at 21:50
  • $\begingroup$ You're right. It's right there in the wikipedia link. Should have done thorough research. $\endgroup$ – Hemant Kumar Mar 14 '17 at 22:19