Possible Solution to: Depth-First Search

Contributors
1

What is your hint or solution suggestion?

Possible Solution 
function dfs(graph, root) {
// start the array with root because it is where we start
let visited = [root];

//keep track of what we visited last to avoid infinite loops
let lastVisited = null;

// main traverse function
  const traverse = (root) => {
    // go through every element of current node
    for (let i = 0;i < graph[root].length;i++){
      if (graph[root][i] === 1) {
        // add to visited if we arrive at a node
        if (!visited.includes(root)) visited.push(root);
        // avoid infinite back and forward loops
        if (lastVisited === i) continue;
        //keep track of what we visited here
        lastVisited = root;
        // recurse!
        traverse(i)
        // be sure to return if we got to last element, geez
      } else if (i === graph[root].length - 1) {
        return;
      }
    }
  }

// actually call the function, that is essential I am tellin' ya!
traverse(root)

// harvest the final product!
return visited;
}
// some examples!
var exDFSGraph = [
  [0, 1, 0, 0],
  [1, 0, 1, 0],
  [0, 1, 0, 1],
  [0, 0, 1, 0]
];
var example = [
  [0, 1, 0, 0], 
  [1, 0, 1, 0], 
  [0, 1, 0, 1], 
  [0, 0, 1, 0]];
var example_2 = [
  [0, 1, 0, 0], 
  [1, 0, 1, 0], 
  [0, 1, 0, 0], 
  [0, 0, 0, 0]];
console.log(dfs(example,1))
console.log(dfs(exDFSGraph, 3));
console.log(dfs(example_2,3))

Challenge: Depth-First Search

Link to the challenge:

2

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.