Created
October 23, 2014 06:49
-
-
Save eldilibra/4745be9bcb5e64f44797 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function Node (id, depth) { | |
this.id = id; | |
this.depth = depth; | |
this.children = []; | |
this.equals = function equals (otherNode) { | |
return this.id === otherNode.id; | |
}; | |
} | |
function shortestPath (root, dest) { | |
var current = root; | |
var visited = [root]; | |
var valid = []; | |
var counter = 0; | |
while (!current.equals(dest)) { | |
current.children.forEach(function (c) { | |
if (visited.indexOf(c) > -1) { | |
console.log('step #' + ++counter); | |
console.log('skipping', c.id, 'since it has been visited'); | |
return; | |
} | |
console.log('step #' + ++counter); | |
console.log(c.id); | |
visited.push(c); | |
valid.push(c); | |
}); | |
current = valid.shift(); | |
} | |
} | |
var you = new Node("You", 0); | |
var a = new Node("a", 1); | |
var b = new Node("b", 1); | |
var c = new Node("c", 1); | |
var d = new Node("d", 2); | |
var e = new Node("e", 2); | |
var f = new Node("f", 3); | |
d.children.push(f); | |
c.children.push(d); | |
b.children.push(e); | |
b.children.push(c); | |
a.children.push(e); | |
a.children.push(b); | |
you.children.push(a); | |
you.children.push(b); | |
you.children.push(c); | |
shortestPath(you, f); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Copy and paste this to a directory on your machine, then run
node main.js
. You'll see the traversal play out step by step.