Iterative DFS vs Recursive DFS and different elements order

by

Both are valid DFS algorithms. A DFS does not specify which node you see first. It is not important because the order between edges is not defined [remember: edges are a set usually]. The difference is due to the way you handle each node’s children.

In the iterative approach: You first insert all the elements into the stack – and then handle the head of the stack [which is the last node inserted] – thus the first node you handle is the last child.

In the recursive approach: You handle each node when you see it. Thus the first node you handle is the first child.

To make the iterative DFS yield the same result as the recursive one – you need to add elements to the stack in reverse order [for each node, insert its last child first and its first child last]

More Related Contents:

  1. Cut set of a graph, Boost Graph Library
  2. How to find number of words in a phrase with spaces removed by checking v. dictionary
  3. c++ error : Segmentation fault (core dumped)
  4. Create an algorithm that asks the user for two positive numbers, call them “first” and “last”, and prints the sum of all the numbers between first [closed]
  5. What is the most effective way for float and double comparison?
  6. Fast bignum square computation
  7. Detecting endianness programmatically in a C++ program
  8. Algorithm to convert RGB to HSV and HSV to RGB in range 0-255 for both
  9. What is the efficient way to count set bits at a position or lower?
  10. Fast exact bigint factorial
  11. Generating combinations in c++
  12. How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag’s value]?
  13. Lock-free Progress Guarantees in a circular buffer queue
  14. Finding duplicates in O(n) time and O(1) space
  15. Fast String Hashing Algorithm with low collision rates with 32 bit integer [closed]
  16. Emulate “double” using 2 “float”s
  17. How to get a random element from a C++ container?
  18. LRU cache design
  19. c++ sort keeping track of indices [duplicate]
  20. Need for predictable random generator
  21. How to add two numbers without using ++ or + or another arithmetic operator
  22. Are there any better methods to do permutation of string?
  23. Reorder vector using a vector of indices [duplicate]
  24. Converting epoch time to “real” date/time
  25. Fastest algorithm for primality test [closed]
  26. Dijkstra Shortest Path with VertexList = ListS in boost graph
  27. What is the safe way to fill multidimensional array using std::fill?
  28. What’s time complexity of this algorithm for finding all combinations?
  29. How to find and replace all occurrences of a substring in a string?
  30. Finding square root without using sqrt function?

Leave a Comment