0

I saw this from an answer to another question

IVlad says that the stack will contain the cycle. But while searching through a graph, wouldn't the nodes that make up the cycle have been popped off in the process?

Maybe he meant in a visited nodes stack? But even then, the visited stack does not cleanly contain the cycle. What I mean is that although the cycle is there, it could have other visited nodes sandwiched between the cycle no?

Community
  • 1
  • 1
1mike12
  • 2,946
  • 3
  • 27
  • 36

1 Answers1

0

When you are using DFS to find cycle in a graph, usually you use recursive method to implement your DFS. Recursive methods use stack to store their data, and when you find a cycle in your recursive method, you have all the path to receive current node. mean of IVlad is running program stack and not the stack you are using for implementing your DFS method.

Also you can store the nodes (Path) in another stack.

Ali Sepehri.Kh
  • 2,468
  • 2
  • 18
  • 27