Skip to content

Instantly share code, notes, and snippets.

@gtb104
Forked from kevinfjbecker/bfs.html
Created November 30, 2015 17:24
Show Gist options
  • Save gtb104/0e6433a380e1c4363ce0 to your computer and use it in GitHub Desktop.
Save gtb104/0e6433a380e1c4363ce0 to your computer and use it in GitHub Desktop.
Breadth-first Graph Traversal in JavaScript
var G = {
vertices: [{
edges: [1, 4]
}, {
edges: [0, 2, 3, 4]
}, {
edges: [1, 3]
}, {
edges: [1, 2, 4]
}, {
edges: [0, 1, 3]
}]
};
(function (G, s) {
var i, Q = [],
u, v;
for (i = 0; i < G.vertices.length; i += 1) {
G.vertices[i].color = 'white';
G.vertices[i].distance = Number.POSITIVE_INFINITY;
G.vertices[i].parent = null;
}
G.vertices[s].color = 'grey';
G.vertices[s].distance = 0;
G.vertices[s].parent = null;
Q.push(s);
while (Q.length > 0) {
u = Q.splice(0, 1)[0];
for (i = 0; i < G.vertices[u].edges.length; i += 1) {
v = G.vertices[u].edges[i];
if (G.vertices[v].color === 'white') {
G.vertices[v].color = 'grey';
G.vertices[v].distance = G.vertices[u].distance + 1;
G.vertices[v].parent = u;
Q.push(v);
}
}
G.vertices[u].color = 'black';
}
})(G, 0);
if (document.getElementById('hello')) {
document.getElementById('hello').innerHTML = JSON.stringify(G);
}
<!DOCTYPE html>
<html>
<head>
<meta charset=utf-8 />
<title>A Graph</title>
<!--[if IE]>
<script src="http://html5shiv.googlecode.com/svn/trunk/html5.js"></script>
<![endif]-->
<style>
article, aside, figure, footer, header, hgroup,
menu, nav, section { display: block; }
</style>
</head>
<body>
<p id="hello">Hello World</p>
<script src="graph.js"></script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment