Iterative graph traversal: non-BFS and non-DFS ordering

Question

Consider this traversal algorithm in pseudocode:

Traverse(G, v):
    S is stack
    stack.push(v)
    label v as visited
    while S is not empty:
        v = S.pop()
        for all w in G.adjacentNodes(v) do:
            if w is not labeled:
                label w
                S.push(w)

This traversal algorithm differs from BFS in its use of the stack instead of queue and from DFS in the moment when it marks a visited vertex (in iterative DFS you mark it as visited when you pop it from the stack). It also provides ordering different from both these approaches.

I have the following questions:

1. Is this traversal correct for a graph of any complexity, i.e. will it visit all vertices of the connected component in which the initial vertex v lies?
2. When should DFS be preferred to this approach? The original DFS creates duplicates in the stack, does it have advantages?

I've looked at similar questions on this site, but they don't provide satisfactory and complete answers.

Answer 1

It's a hybrid. It "visits" from left to right the siblings (a breadth-first element) but separates the handling from the visit, as the handling is done in depth-first fashion.

So for each node:

• its children are added to the stack from left to right so they will be evaluated from right to left
• its children will be handled before the nodes that are already in the stack before "visiting" the children of the current node
• a "right" child's entirety of subtree will be handled before a "left" child is even explored let alone handled (but it was visited)

To answer your question: yes, this will successfully traverse the graph and it depends on your goals when it is to be preferred. But objective reasons for preference for this algorithm could stem from a desire to get a breadth-first from right to left.

But, if "visiting" does not do any magic besides marking a node as being visited, then you could easily use a depth-first search with descending sibling order instead, because that only differs from your algorithm by its non-separation of visit from handling.

Answer 2

Yes, this traversal algorithm is correct and will visit all vertices in the connected component of the starting node v. It’s a variation of DFS that marks nodes as visited when they are pushed onto the stack, rather than when they are popped, which avoids pushing the same node multiple times. This makes it more memory-efficient than standard iterative DFS, but it doesn't produce a post-order traversal (which is important for algorithms like topological sort or strongly connected components). Use this approach when you simply need to visit all reachable nodes efficiently without duplicates in the stack. Use standard DFS if you need post-order properties or more control over the traversal order.