kruskal

kruskal.js
==========

A simple implementation of Kruskal's algorithm to find the minimum spanning tree of a graph.

This implementation needs only the edge list, not the whole adjacency matrix, so could be more
efficient for sparser graphs.

Kruskal's Algorithm

Usage
=====

Here is an example of finding the minimum spanning tree given in the example directory:

!alt tag

See example/example.js for a full example. Here is an abridged version:

// vertices hold data that will be used in the distance metric function
var verticies = [
[0.38503426988609135,0.5090362404007465],
[0.19520984776318073,0.786977760726586],
...
]

// edges are vertex position pairs
var edges = [
[8,6], [8,12], [6,12], ...
];

function metric_dist( a, b )
{
var dx = a[0] - b[0];
var dy = a[1] - b[1];
return dxdx + dydy;
}

var Kruskal = require("../kruskal.js");
var edgeMST = Kruskal.kruskal( vertices, edges, metric_dist );

// Print minimum spanning tree
for (var ind in edgeMST)
{
var u = edgeMST[ind][0];
var v = edgeMST[ind][1];

console.log( verts[u][0] + " " + verts[u][1] );
console.log( verts[v][0] + " " + verts[v][1] );
console.log("");

}

License
=======
GPLv3