Simple Kruskal's implementation

kruskal.js

// 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));

note: require.js and underscore.js are dependencies

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)) {