Graph DFS

Traverse a graph depth-first from a start node using an explicit stack, exploring each branch fully before backtracking.

Time O(V + E) Space O(V) Graph dfs

How it works

Traverse a graph depth-first from a start node using an explicit stack, exploring each branch fully before backtracking.

Implementation

function graphDfsOp(state, start) {
  const adjHead = state.adjHead;
  const adjTo = state.adjTo;
  const adjNext = state.adjNext;
  const nodeCount = state.nodeCount;
  const visited = [];
  let v = 0;
  while (v < nodeCount) {
    visited[v] = 0;
    v = v + 1;
  }
  const stack = [];
  stack[0] = start;
  while (stack.length > 0) {
    const node = stack[stack.length - 1];
    stack.length = stack.length - 1;
    if (visited[node] === 0) {
      visited[node] = 1;
      visitNode(node);
      traverseNode(node);
      let e = adjHead[node];
      while (e !== -1) {
        const nb = adjTo[e];
        compareKeys(node, nb);
        if (visited[nb] === 0) {
          stack[stack.length] = nb;
          linkNodes(node, nb);
        }
        e = adjNext[e];
      }
    }
  }
  finish();
}