CODEWITHSUNDEEP
javascriptalgorithmdata-structures
devdropper87
devdropper87

Reputation: 4187

depth first traversal of a graph - javascript

I am trying to learn graphs well and implemented the following depth-first search in javascript. The DFS function is working ok, but the checkRoutes function is the source of my troubles. The checkRoutes function accepts two inputs and returns true if there is a possible path between two nodes/vertices, and false if not. it does this by starting at a node, checking the adjacency list, and then checking the adjacency lists of every item in the adjacency list via recursion.

My solution works for only one case - when you check two vertices once, but due to the way I'm storing the possibleVertices array globally, "possibleVertices" doesn't get cleared out each time. how could I push and store to the "possibleToVisit" array inside "checkRoute" instead of globally in this class? Would it be better to have this array stored on the constructor?

var possibleToVisit = [];

function dfs(v) {
  this.marked[v] = true;
  if (this.adj[v] !== undefined) {
    console.log("visited vertex " + v);
  }

  for (var i = 0; i < this.adj[v].length; i++) {
    var w = this.adj[v][i];
    if (!this.marked[w]) {
      possibleToVisit.push(w)
      this.dfs(w);
    }
  }
  console.log(possibleToVisit);
}

function checkRoute(v, v2) {
  this.dfs(v);
  if (possibleToVisit.indexOf(v2) === -1) {
    return false;
  }
  return true;
}
g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
// g.showGraph();
// g.dfs(0);
console.log(g.checkRoute(0, 4));//true
console.log(g.checkRoute(0, 5));//false

https://jsfiddle.net/youngfreezy/t1ora6ab/3/#update

Upvotes: 0

Views: 2863

Answers (3)

chen0040
chen0040

Reputation: 61

You can use a marked[] array (which is filled up during the dfs() call) to determine whether a particular vertex can be reached from a known vertex s.

Please take a look at the depth first search implementation in the following library:

https://github.com/chen0040/js-graph-algorithms

It provides an object oriented approach to the graph creation as well as the depth first search algorithm.

The sample code for its depth first search algorithm is given here:

var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.Graph(6);
g.addEdge(0, 5);
g.addEdge(2, 4);
g.addEdge(2, 3);
g.addEdge(1, 2);
g.addEdge(0, 1);
g.addEdge(3, 4);
g.addEdge(3, 5);
g.addEdge(0, 2);
var starting_vertex = 0;
var dfs = new jsgraphs.DepthFirstSearch(g, starting_vertex);


for(var v=1; v < g.V; ++v) {
 if(dfs.hasPathTo(v)) {
    console.log(s + " is connected to " + v);
    console.log("path: " + dfs.pathTo(v));
 } else {
     console.log('No path from ' + s + ' to ' + v);
 }
}

Upvotes: 0

Yeldar Kurmangaliyev
Yeldar Kurmangaliyev

Reputation: 34189

You can write a DFS "starter" function, which will reset all variables, and return something if necessary:

function Graph(v) {
    this.startDfs = startDfs;
    this.possibleToVisit = [];
}

// ...

function startDfs(v) {
    this.possibleToVisit = []; // here, you can reset any values

    this.dfs(v);

    return true; // here, you can return a custom object containing 'possibleToVisit'
}

And call it only using startDfs:

function checkRoute(v, v2) {
    this.startDfs(v);
    if (this.possibleToVisit.indexOf(v2) === -1) {
        return false;
    }
    return true;
}

Here is the updated JSFiddle.

Upvotes: 1

deamentiaemundi
deamentiaemundi

Reputation: 5525

Arrays in Javascript get passed as reference, so something like

function fill(a,l){
  for(var i = 0;i<l;i++)
    a.push(i + 10);
}

function check(idx, max){
  var arr = [];
  fill(arr,max);
  console.log(arr[idx]); // 14
}
check(4,10)

would work and everytime check gets called arr is fresh and clean.

Upvotes: 0

Related Questions