Is this post about DFS algorithm right?

Question

what's wrong? I think stack no.4 has to be changed [G P E].

Is there any way i can skip vertex G when i visit vertex P?

I think there is no way. Is it wrong?

Answer 1

This is a variant of the standard DFS algorithm. In the standard algorithm, you would not put the unvisited neighbors of the current node all on the stack, but only the node itself, to then visit one neighbor. After having performed a DFS on that neighbor, you would backtrack and only then look at the other children. If there is still an unvisited one among them, only then it gets pushed on the stack.

But this alternative -- where all unvisited neighbors are put on the stack before deepening the traveral -- will work fine as well.

When you put a node on the stack, you should also mark it as stacked, a mark that will never be removed again during the graph traversal, even if the node is popped from the stack later. That way you can ensure that a node will never be put on the stack more than once during the whole traversal.

When arriving at node P, all the neighbors of P (i.e. G and H) have already been stacked before (H has been pulled from it, and G is still on it). As there are no other neighbors of P, this DFS algorithm pulls the next node from the stack (i.e. E) to continue the traversal.

Here is a JavaScript implementation:

class Node {
    constructor(name) {
        this.name = name;
        this.neighbors = [];
    }
    link(node) { // link nodes in both directions
        this.neighbors.push(node);
        node.neighbors.push(this);
    }
    toString() { // The string representation of the node is its name
        return this.name;
    }
    dfs() { // Main algorithm
        const stack = [this], // Start with this node on the stack
            stacked = new Set(stack); // ...and mark it as stacked

        while (stack.length > 0) { // While the stack is not empty...
            console.log('stack: ' + stack);
            const node = stack.pop(); // Pull next node from the top of the stack
            for (const neighbor of node.neighbors) {
                // Only push neighbors on the stack
                // that were never stacked before:
                if (!stacked.has(neighbor)) {
                    stack.push(neighbor); // Push on the stack,
                    stacked.add(neighbor); // ... and mark as stacked
                }
            }
        }
    }
}

// Define nodes:
const a = new Node('A'),
      e = new Node('E'),
      g = new Node('G'),
      h = new Node('H'),
      j = new Node('J'),
      m = new Node('M'),
      p = new Node('P'),
      x = new Node('X'),
      y = new Node('Y');

// Define the links between the nodes
a.link(x);
x.link(g);
x.link(h);
g.link(h);
g.link(p);
h.link(e);
h.link(p);
e.link(m);
e.link(y);
y.link(m);
m.link(j);

// Visit the nodes of the graph, starting at A
a.dfs();

.as-console-wrapper { max-height: 100% !important; top: 0; }

Note that if a graph is a tree, then a DFS traversal down the tree can never encounter a node that was already visited before, so in that case no such marking is necessary. But your graph is an undirected cyclic graph, so this extra marking is needed.