Skip to content

Instantly share code, notes, and snippets.

@netgusto
Last active February 5, 2022 01:24
Show Gist options
  • Save netgusto/b860b2d8f68ca557b6c22090aca46398 to your computer and use it in GitHub Desktop.
Save netgusto/b860b2d8f68ca557b6c22090aca46398 to your computer and use it in GitHub Desktop.
Graph Data Structure, adjacency list implementation + Traversals (DFS, BFS)

Graph Data Structure, adjacency list implementation + Traversals (DFS, BFS)

Simplest implementation of a Graph + Traversal algorithms.

Usage

make

# or, if you want to watch for changes
make watch
module.exports = class Graph {
constructor(V, E, directed = false) {
this.vertices = V;
this.edges = {};
E.map(e => {
const a = e[0]; const b = e[1]; const w = e[2] === undefined ? 1 : e[2];
this.addEdge(a, b, w);
if (!directed) this.addEdge(b, a, w);
});
}
addEdge(va, vb, w) {
if (!(va in this.edges)) this.edges[va] = [];
this.edges[va].push({ node: vb, w });
}
getEdges(v) {
return (v in this.edges) ? this.edges[v] : [];
}
getEdge(a, b) {
return (a in this.edges) ? this.edges[a].find(e => e.node === b) : undefined;
}
}
const Graph = require('./Graph');
const { dfs, dfsIterative, bfs } = require('./traversal');
const g = new Graph(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'], [
['a', 'b', 4],
['b', 'c', 8],
['c', 'd', 7],
['d', 'e', 9],
['e', 'f', 10],
['f', 'g', 2],
['g', 'h', 1],
['h', 'a', 4],
['b', 'h', 11],
['c', 'i', 2],
['c', 'f', 4],
['d', 'f', 14],
['h', 'i', 7],
]);
const logNode = function(vertex, previous, weight) {
console.log((previous ? previous : '∅') + ' -' + (weight ? '(' + weight + ')' : '') + '-> ' + vertex);
};
console.log('Depth First Search, starting from a:');
dfs(g, 'a', logNode);
console.log('\nDepth First Search Iterative, starting from a:');
dfsIterative(g, 'a', logNode);
console.log('\nBreadth First Search, starting from a:');
bfs(g, 'a', logNode);
console.log('\nDepth First Search, starting from i:');
dfs(g, 'i', logNode);
console.log('\nBreadth First Search, starting from i:');
bfs(g, 'i', logNode);
.DEFAULT_GOAL := run
SRC=$(wildcard *.js)
changed: $(SRC)
echo "Changed !"
exit 0
run: $(SRC)
@node index.js
watch:
while true; do make -t -s -q changed || (echo "\n---"; make -s run); sleep 0.5; done
module.exports = {
dfs,
dfsIterative,
bfs
};
function dfs(graph, currentVertex, cbk, weight = undefined, visited = {}, previousVertex) {
visited[currentVertex] = true;
cbk(currentVertex, previousVertex, weight);
graph.getEdges(currentVertex).map(e => {
if (!visited[e.node]) {
dfs(graph, e.node, cbk, e.w, visited, currentVertex);
}
});
}
function dfsIterative(graph, currentVertex, cbk) {
const stack = [{ v: currentVertex, prev: undefined, weight: undefined}];
const visited = {};
while(stack.length) {
const { v, prev, weight } = stack.pop();
if (visited[v]) continue;
visited[v] = true;
cbk(v, prev, weight);
graph.getEdges(v).reverse().map(e => { // reverse: traversal in same order as recursive dfs (stack inverses order)
stack.push({ v: e.node, prev: v, weight: e.w });
});
}
}
function bfs(graph, currentVertex, cbk) {
const queue = [{ v: currentVertex, prev: undefined, weight: undefined}];
const visited = {};
while(queue.length) {
const { v, prev, weight } = queue.pop();
if(visited[v]) continue;
visited[v] = true;
cbk(v, prev, weight);
graph.getEdges(v).map(e => {
if(!visited[e.node])
queue.unshift({ v: e.node, prev: v, weight: e.w });
});
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment