-
-
Save n8agrin/3629426 to your computer and use it in GitHub Desktop.
// See http://en.wikipedia.org/wiki/Kruskal's_algorithm | |
// and http://programmingpraxis.com/2010/04/06/minimum-spanning-tree-kruskals-algorithm/ | |
var _ = require('underscore'); | |
var nodes = ["A", "B", "C", "D", "E", "F", "G"]; | |
var edges = [ | |
["A", "B", 7], ["A", "D", 5], | |
["B", "C", 8], ["B", "D", 9], ["B", "E", 7], | |
["C", "E", 5], | |
["D", "E", 15], ["D", "F", 6], | |
["E", "F", 8], ["E", "G", 9], | |
["F", "G", 11] | |
]; | |
function kruskal(nodes, edges) { | |
var mst = []; | |
var forest = _.map(nodes, function(node) { return [node]; }); | |
var sortedEdges = _.sortBy(edges, function(edge) { return -edge[2]; }); | |
while(forest.length > 1) { | |
var edge = sortedEdges.pop(); | |
var n1 = edge[0], | |
n2 = edge[1]; | |
var t1 = _.filter(forest, function(tree) { | |
return _.include(tree, n1); | |
}); | |
var t2 = _.filter(forest, function(tree) { | |
return _.include(tree, n2); | |
}); | |
if (t1 != t2) { | |
forest = _.without(forest, t1[0], t2[0]); | |
forest.push(_.union(t1[0], t2[0])); | |
mst.push(edge); | |
} | |
} | |
return mst; | |
} | |
console.log(kruskal(nodes, edges)); |
There's a bug in this code: array are compared as t1 != t2 on line 36.
This can work work buggy sometimes (worked not as expected for me in node.js).
Another function for comparison should be used. I slightly modified this code: http://stackoverflow.com/a/14853974/1923879
very helpful!
If you add the extra condition, sortedEdges.length > 0 for the while loop, this will work for disconnected graphs too. Else, sortedEdges will run out before you are left with the single Forest that you looking for.
This is not working
nodes [ '2', '3', '4', '10', '108', '22' ]
edges [ [ '2', '3', 1 ],
[ '2', '4', 1 ],
[ '2', '10', 1 ],
[ '3', '2', 1 ],
[ '10', '108', 1 ],
[ '10', '22', 1 ],
[ '108', '22', 1 ] ]
mst [ [ '108', '22', 1 ],
[ '10', '22', 1 ],
[ '10', '108', 1 ],
[ '3', '2', 1 ],
[ '2', '10', 1 ],
[ '2', '4', 1 ] ]
There is a cycle !!!!
fix
line 36
if (t1 != t2) {
change to
if (!_.isEqual(t1, t2)) {
Ye, either that, or:
if (JSON.stringify(t1) != JSON.stringify(t2)) {
note: require.js and underscore.js are dependencies