Created
September 5, 2012 02:33
-
-
Save n8agrin/3629426 to your computer and use it in GitHub Desktop.
Simple Kruskal's implementation
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
// 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)); |
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)) {
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
very helpful!