1
$\begingroup$

I'm writing a graph traversal function to be used in a garbage collector.

To avoid stack overflow, I used a finite state machine. Roughly, it descends into child nodes recursively to mark objects, and return to root (to descent down again) whenever a branch is exshausted.

However, I realized that if there's loop in the graph, it cannot handle it, as it cannot distinguish a node marked for traversal in its children/descendents from a node that it had visited before.

Q: Does traversal on a graph with loop require a stack machine? If so, I'll rewrite my traversal function.

$\endgroup$

1 Answer 1

0
$\begingroup$

as it cannot distinguish a node marked for traversal in its children/descendents from a node that it had visited before.

This can be fixed by traversing a list of nodes it's visiting, starting from root - this list doesn't have to be stored, restarting from root and iterating forward is sufficient; when a node found matching the one it's about to descend into, the function retracts.

Hence, it doesn't require a stack. But again, such implementation is very complex to implement and comprehend, and quite inefficient.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.