Depth First Search – Graphs

This article covers how to implement Depth First Search (DFS) for Graphs in Javascript. For more information on Depth First Search and the tree implementation, see the main DFS article.

Strategy
Similar to DFS for trees, the Javascript implementation for DFS for graphs is to process nodes in order. The difference is there’s no longer left/right branches, and that we need to keep track of the nodes we’ve visited. This is to prevent infinite traversal.

  1. remove from top of stack
  2. process node
  3. for each neighbor, if it hasn’t been visited
    • add to visited list
    • add to stack at top (which will be removed first)
let adj; //matrix of adjacencies

function DFS (node) {
  let stack=[node]; //LIFO: Last In, First Out
  let visited=[]; //list of nodes we've visited already

  while (stack.length>0) { //while stack isn't empty
    const current=stack.pop(); //take from top of stack

    //process current node
    console.log(current);

    //add neighbors to stack and visited list
    for (let i=0; i<adj[current].length;i++) {
      if (!visited[current]) {
        visited.push(current);
        stack.push(current);
      }
    }
  }
}