dfsBfs

dfsBfs.js

const _ = require('underscore');

class Node {
  
  constructor(id, value, adjacent) {
    this.id = id;
    this.value = value;
    this.adjacent = adjacent;
  }

}

class Graph {
  
  constructor(adjacent) {
    this.adjacent = adjacent;
  }
  
  dfs(source, dest) {    
    if (!source) {
      return false;
    }    
    if (source.id === dest.id) {
      return true;
    }
    
    for (let node of source.adjacent || []) {        
      if (this.dfs(node, dest)) {
        return true;
      }
    }

    return false;
  }
  
  bfs(source, dest) {
    const visited = [];
    const searchList = [source];
    
    while (searchList.length !== 0) {
      const node = searchList.shift();
      
      if (node.id === dest.id) {
        return true;
      }
      
      if (visited.includes(node.id)) {
        return false;
      }
      visited.push(node.id);
      
      if (node.adjacent) {
        searchList.push(...node.adjacent); 
      }
    }
    
    return false;
  }
  
}

const test = (currentResult, expectedResult) => {
  if (!_.isEqual(currentResult, expectedResult)) {
    console.log('Error!');
    console.log('Current Result:');
    console.log(currentResult);
    console.log('Expected Result:');
    console.log(expectedResult);
  } else {
    console.log('Success.');
  }
} 

/*
  a-> b
   -> c -> d
*/
let id = 1;
const d = new Node(id++, 'd');
const b = new Node(id++, 'b');
const c = new Node(id++, 'c', [d]);
const a = new Node(id++, 'a', [b, c]);

var graph = new Graph([a]);

test(graph.bfs(a, d), true);
test(graph.bfs(b, a), false);

test(graph.dfs(a, d), true);
test(graph.dfs(b, a), false);