How can I find the actual path found by BFS?

by

To do so, you need to store a map:V->V (from vertices to vertices), which will map from each node v, the vertex u that “discovered” v.

You will populate this map during the iterations of BFS.

Later – you can reconstruct the path by simply going from the target node (in the map) up until you get back to the source, which will be your path (reversed, of course).

Note that this map can be implemented as an array if you enumerate the vertices.

More Related Contents:

  1. Insertion sort stops working after million input
  2. How to find out how many bits are set (equal 1) in the product of two integers [closed]
  3. C++ – Find numbers between first and last negative numbers in Array
  4. Program stopped working, when tried to run
  5. Absolute Distinct Numbers
  6. C++ throwing exception in recursive algorithm
  7. How to use Quick Sort to sort an array of strings
  8. How to get the maximum number after erasing n digits from the number [closed]
  9. Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition
  10. Rotating a point about another point (2D)
  11. Create Random Number Sequence with No Repeats
  12. Fast ceiling of an integer division in C / C++
  13. Algorithm for finding the smallest power of two that’s greater or equal to a given value [duplicate]
  14. Search for a struct item in a vector by member data
  15. Need for predictable random generator
  16. Splitting a string by a character
  17. How can I sort a std::map first by value, then by key?
  18. what is the difference between set and unordered_set in C++?
  19. Similar String algorithm
  20. Calculating the Amount of Combinations
  21. Better shading on BW display while rendering filled surfaces
  22. `std::list::sort()` – why the sudden switch to top-down strategy?
  23. Algorithm to add or subtract days from a date?
  24. Creating N nested for-loops
  25. What’s time complexity of this algorithm for finding all combinations?
  26. How to find and replace all occurrences of a substring in a string?
  27. Counting number of bits: How does this line work ? n=n&(n-1); [duplicate]
  28. Good C++ solutions to the “Bring all the zeros to the back of the array” interview challenge
  29. Finding square root without using sqrt function?
  30. Order Statistic Tree in C++

Leave a Comment