Skip to content

Instantly share code, notes, and snippets.

@liamgriffiths
Last active July 28, 2019 20:39
Show Gist options
  • Save liamgriffiths/7406990 to your computer and use it in GitHub Desktop.
Save liamgriffiths/7406990 to your computer and use it in GitHub Desktop.
graph. stack, and queue structures
function Graph(nodes) {
this.nodes = nodes || {};
}
Graph.prototype.print = function(storage, start, stop) {
start = start || 1;
storage.put(new Node(start));
while (! storage.isEmpty()) {
var seen = {};
var from = storage.get();
var to = this.nodes[from.value];
if (to) {
for (var i = 0; i < to.length; i++) {
if (to[i] == stop) {
return this.getPath(new Node(to[i], from));
} else if (! seen[to[i]]) {
storage.put(new Node(to[i], from));
seen[to[i]] = true;
} else {
}
}
}
}
};
Graph.prototype.getPath = function(finalNode) {
var node = finalNode;
var path = [];
while (node.parent) {
path.push(node.value);
node = node.parent;
}
return path.reverse();
};
function Node(value, parent, weight) {
this.value = value;
this.parent = parent || true;
this.weight = weight || 1;
}
var graph1 = {
1: [2, 4],
2: [1, 3, 5],
3: [2],
4: [7, 1],
5: [2, 6, 8],
6: [5, 9, 10],
7: [4],
8: [5],
9: [6, 12],
10: [6, 11],
11: [10]
};
var graph2 = {
1: [2, 4],
2: [1, 3, 5],
3: [2, 11],
4: [1, 5, 7],
5: [2, 4, 6, 8],
6: [5, 9, 10],
7: [4, 13],
8: [5, 14],
9: [6, 12],
10: [6, 11],
11: [3 ,10],
12: [9],
13: [7, 14],
14: [8, 13]
};
var graph = new Graph(graph2);
console.log('queue 1 -> 14');
out = graph.print(new Queue(), 1, 14); // breadth-first search
console.log(out);
console.log('stack 1 -> 14');
out = graph.print(new Stack(), 1, 14); // depth-first search
console.log(out);
function Queue() {
this.elements = [];
}
Queue.prototype = {
get: function() {
return this.elements.shift();
},
put: function(element) {
return this.elements.push(element);
},
size: function() {
return this.elements.length;
},
isEmpty: function() {
return this.size() === 0;
}
};
module.exports = Queue;
function Stack() {
this.elements = [];
}
Stack.prototype = {
get: function() {
return this.elements.pop();
},
put: function(element) {
return this.elements.push(element);
},
size: function() {
return this.elements.length;
},
isEmpty: function() {
return this.size() === 0;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment