freeCodeCamp Challenge Guide: Depth-First Search

Depth-First Search

This is a stub. Help the community by making a suggestion of a hint and/or solution. We may use your suggestions to update the missing sections.


Problem Explanation

This summarizes what need to be done without just restating the challenge description and/or instructions. This is an optional section

Relevant Links


Hints

Hint 1

Hint goes here

Hint 2

Hint goes here


Solutions

Solution 1 (Click to Show/Hide)
function isFound(r, i) {
  for(let k = 0; k < r.length; ++k) {
    if(r[k] == i) {
      return true;
    }
  }
  return false;
}

function dfs(graph, root) {
  let r = [];
  let stack = [];
  stack.push(graph[root]);
  r.push(root);
  while(stack.length > 0) {
    for(let i = 0 ; i < graph[root].length; ++i) {
      if(!isFound(r, i) && stack[stack.length - 1][i] == 1) {
        stack.push(graph[i]);
        r.push(i);
        i=0;
      }
    }
    stack.pop()
  }
  return r;
}

var exDFSGraph = [
  [0, 1, 0, 0],
  [1, 0, 1, 0],
  [0, 1, 0, 1],
  [0, 0, 1, 0]
];
console.log(dfs(exDFSGraph, 3));

Code Explanation

  • Code explanation goes here

Relevant Links