Graph DSF and BFS Example

Demonstrates how to implement a Breadth First and Depth First Search on a Graph

by Nyle Anderson

HTML

<input type="button" onclick="createGraph();" value="Create Graph" />
<br/>

<br/> Select two nodes:
<br />From
<select id="from"></select>
<select id="to"></select>

<input type="button" onclick="doDFS();" value="Depth First Search" />
<input type="button" onclick="doBFS();" value="Breadth First Search" />

<br/>
<p id="nodes"></p>
<br/>
<p id="edges"></p>
<br/>
<br/>
<p id="results"></p>
<img src="http://cop3530.pbworks.com/f/1436983373/Graph1.jpg" />

JavaScript

// This is a basic implementation of a Graph
// It has nodes and edges 
// I am using a stack (array in Javascript) to hold info

var Node = function(_name) {
  this.name = _name;
  this.discovered = false;
  this.edges = [];
  return this;
}

var Edge = function(_from, _to, _cost) {
  this.from = _from;
  this.to = _to;
  this.cost = _cost;
  return this;
}

var Graph = function() {

  // This is a specific implementation of a graph
  // that uses nodes edges and paths. There are many
  // more ways to implement a graph and you should 
  // research them

  this.nodes = [];
  this.edges = [];
  this.paths = [];

  this.addNode = function(_name) {
    var node = new Node(_name);
    this.nodes.push(node);
    return node;
  };

  this.addEdge = function(_from, _to, _cost) {
// Create Edge _from, _to are nodes
    var edge1 = new Edge(_from, _to, _cost);
    var edge2 = new Edge(_to, _from, _cost);
// Add edge to Graphs collection of edges (used only for print)   
    this.edges.push(edge1);

// More important add to Nodes collection of edges
    _from.edges.push(edge1);
    _to.edges.push(edge2);

    return edge1;
  };

  this.printNodes = function() {
    var s = "All Nodes in Graph <br/>";
    for (var i = 0; i < this.nodes.length; i++) {
      s = s + "Node: " + i + "   Name: " + this.nodes[i].name + "</br>";
    }
    return s;
  }

  this.printEdges = function() {
    var s = "All Edges in Graph <br/>";
    for (var i = 0; i < this.edges.length; i++) {
      s += "Edge: " + i + "   From: " + this.edges[i].from.name + "   To: " + this.edges[i].to.name + "   Cost: " + this.edges[i].cost + "</br>";
    }
    return s;
  }
   
  // Must implement
  this.calculatePaths = function(_from, _to) {
 // f and t are the node names
    this.reset();
    var nodeFrom = this.getNodeByName(_from);
    var nodeTo = this.getNodeByName(_to);
    var dfsPath = [];
    dfsPath = this.DFS(nodeFrom, dfsPath); 
    this.paths.push(dfsPath);
    return this.paths;
  }

 ...