Iterative Dfs VS Recursive Dfs and Different Elements Order

Iterative DFS vs Recursive DFS and different elements order

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]

Different output from dfs iterative and dfs recursive

Your iterative and recursive dfs functions produce different outputs because they operate differently when a node is connected to multiple nodes.

To take your example, 0 is connected to 1 and 2.

The recursive function will call dfsrecursive on 1 as it's the first node in adjacency list and thus 1 will appear before 2.

In the iterative version, both 1 and 2 will be pushed on the stack in order. Since 2 was pushed last, it will be popped before 1. Hence, 2 will be printed before 1.

Obviously, this change in order also affects other nodes as the two algorithms diverge.

I don't really see any problem with this, but if it bothers you, you can try reversing the order in which you push adjacent nodes to the stack. That should fix this problem.

Maintaining context of current node in a iterative DFS vs a recursive DFS

1) The simplest solution - would std::stack<Node> work? You should make it work like a program stack works - push the starting Node there, then pop a node, check if it's special, if not - push its children, repeat.

2) You don't check if you have already visited a node - maybe you can speed it up a bit. (Edited: I can't read)

Update: yes, this was an interesting beast. How about this code? I didn't test it though, but the main idea should work: split visitation into two steps - before and after recursion.

struct StackNodeEntry
{
    Node cur;
    optional<Node> parent;

    enum class Pos
    {
        before_recursion, after_recursion
    } pos;
};

bool findSpecial(Node root)
{
    stack<StackNodeEntry> stack;

    stack.push({ root, {}, StackNodeEntry::Pos::before_recursion });

    while (!stack.empty())
    {
        auto& e = stack.top();

        switch (e.pos)
        {
        case StackNodeEntry::Pos::before_recursion:
            if (isSpecial(e.cur))
            {
                if (e.parent)
                    markCurrentNodeSpecial(*e.parent);
                stack.pop();
                break;
            }

            for (auto n : getChildren(e.cur))
                stack.push({ n, e.cur, StackNodeEntry::Pos::before_recursion });
            e.pos = StackNodeEntry::Pos::after_recursion;
            break;

        case StackNodeEntry::Pos::after_recursion:

            if (isSpecial(e.cur))
            {
                if (e.parent)
                    markCurrentNodeSpecial(*e.parent);
            }
            stack.pop(); // don't use e below this line
            break;
        }
    }

    return isSpecial(root);
}

What are some true Iterative Depth First Search implementation suggestions?

Question 1: If you check+mark before the push, it uses less space but changes the order in which nodes are visited. You will visit everything, though.

Question 2: You are correct that an iterative DFS will usually put all the children of a node onto the stack at the same time. This increases the space used for some graphs, but it doesn't change the worst case space usage, and it's the easiest way so there's usually no reason to change that.

Occasionally you know that it will save a lot of space if you don't do this, and then you can write an iterative DFS that works more like the recursive one. Instead of pushing the next nodes to visit on the stack, you push a parent and a position in its list of children, or equivalent, which is pretty much what the recursive version has to remember when it recurses. In pseudo-code, it looks like this:

func DFS(start):
    let visited = EMPTY_SET
    let stack = EMPTY_STACK

    visited.add(start)
    visit(start)
    stack.push( (start,0) )

    while(!stack.isEmpty()):
        let (parent, pos) = stack.pop()
        if (pos < parent.numChildren()):

            let child = parent.child[pos]
            stack.push(parent,pos+1)

            if (!visited.contains(child)):
                visited.add(child)
                visit(child)
                stack.push( (child,0) )

You can see that it's a little more complicated, and the records you push on the stack are tuples, which is annoying in some cases. Often we'll use two stacks in parallel instead of creating tuples to push, or we'll push/pop two records at a time, depending on how nodes and child list positions have to be represented.

Depth-first search with goal iterative

You have to keep track of the parent of each visited node using a dictionary. Then once you reach your goal node, backtrack to source using dictionary.

graph = {"A": ["D", "F", "B"],
         "B": ["C"],
         "C": [],
         "D": ["E"],
         "E": ["G"],
         "F": [],
         "G": []}

def dfs_non_recursive(graph, source, goal):
    if source is None or source not in graph:
        return "Invalid input"

    path = []  # path to goal
    parent = {} # stores parent of each node

    stack = [source]

    while len(stack) != 0:

        s = stack.pop()

        if s == goal:
            path.append(goal)
            while(s in parent.keys()):
                path.append(parent[s])
                s = parent[s]
            return path[::-1]  # reverse of path

        if s not in graph:
            # leaf node
            continue

        for neighbor in graph[s]:
            stack.append(neighbor)
            parent[neighbor] = s

    return path

DFS_path = dfs_non_recursive(graph, "A", "G")
print(DFS_path)

---

Related Topics