User Tools

Site Tools


λ Kruskal's minimum spanning tree

======= Algorithm ======= <syntax js> // graph is {nodes:[a,b,c...], edges:[{source:a, target:b}...]} function minimumSpanningTree(graph) { // Create a forest 'trees' (a set of trees), where each vertex // in the graph is a separate tree. var trees = new DisjointSet(); for (var i=0, c=graph.nodes.length; i<c; i++) { trees.makeSet(graph.nodes[i]); } // Create a set 'edges' containing all the edges in the graph. var edges = graph.edges.slice(); // Copy using slice. // Sort 'edges' so that the edges are in descending order, // the last edge is the shortest. edges.sort(function(a, b) {return b.distance - a.distance;}); var usedEdges = []; // While 'edges' is nonempty and 'trees' is not yet spanning. while (edges.length > 0 && trees.length > 1) { // Remove an edge with minimum weight from 'edges' var edge = edges.pop(); var treeSource = trees.setContaining(edge.source); var treeTarget = trees.setContaining(edge.target); if (treeSource !== treeTarget) { usedEdges.push(edge); // If that edge connects two different trees, then add it to // the forest, combining two trees into a single tree. trees.unionSets(treeSource, treeTarget); } // Otherwise discard that edge. } return usedEdges; } </syntax> ======= Support ======= <syntax js> function DisjointSet() { this.sets = []; } DisjointSet.prototype = { get length() { return this.sets.length; }, makeSet:function(x) { var set = {data:x}; set.parent = set; x._set = set; // Ugly pollution of data.x for now. this.sets.push(set); return set; }, setContaining:function(x) { if (!x._set) return null; return this.setContainingSet(x._set); }, setContainingSet:function(x) { if (x.parent === x) return x; else return this.setContainingSet(x.parent); }, unionSets:function(a, b) { a.parent = b; this.sets.splice(this.sets.indexOf(a), 1); } }; function run(graph) { result = minimumSpanningTree(graph); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title":"Kruskal's minimum spanning tree", "height":"500px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style type="text/css"> path { fill: #ddd; fill-opacity: .8; stroke: #fff; stroke-width: 1px; } circle { stroke-width: 1px; stroke: #444; } line { stroke: #999; } line.notused { stroke-dasharray: 5,5; } line.checking { stroke: black; stroke-width: 2px; } line.selected { stroke-width: 2px; } </style> <script src="http://d3js.org/d3.v3.min.js"></script> <script> var nodes = []; var links = []; var force; var svg; function buildGraph() { force = d3.layout.force().size([300, 300]); svg = d3.select("body").append("svg:svg") .attr("width", 300) .attr("height", 300); newGraph(); } function newGraph() { nodes = []; links = []; var numNodes = 7+Math.floor(Math.random()*5); for (var i=0; i<numNodes; i++) { var node = [10+Math.random()*280, 10+Math.random()*280]; node.colour = "hsl("+Math.floor(i/(numNodes+1)*360)+", 100%, 50%)"; nodes.push(node); } var edge = function(a, b) { var dx = a[0] - b[0], dy = a[1] - b[1]; return { source: a, target: b, distance: Math.sqrt(dx * dx + dy * dy) }; } var hasEdge = function(a, b) { for (var i=0, c=links.length;i<c;i++) { if ((links[i].source === a && links[i].target === b) || (links[i].source === b && links[i].target === a)) return true; } return false; } d3.geom.delaunay(nodes).forEach(function(d) { if (!hasEdge(d[0], d[1])) links.push(edge(d[0], d[1])); if (!hasEdge(d[1], d[2])) links.push(edge(d[1], d[2])); if (!hasEdge(d[2], d[0])) links.push(edge(d[2], d[0])); }); /*force.gravity(0) .nodes(nodes) .links(links) .linkDistance(function(d) { return d.distance; }) .start();*/ svg.selectAll("line").remove(); svg.selectAll("circle").remove(); var link = svg.selectAll("line").data(links); link.enter().append("svg:line"); link .attr("x1", function(d) { return d.source[0]; }) .attr("y1", function(d) { return d.source[1]; }) .attr("x2", function(d) { return d.target[0]; }) .attr("y2", function(d) { return d.target[1]; }); var node = svg.selectAll("g").data(nodes); node.enter() .append("circle") .attr("r", 4); node.attr("cx", function(d) { return d[0]; }) .attr("cy", function(d) { return d[1]; }); lastEdges = lastTrees = undefined; if (window.reset) reset(); } window.onload = buildGraph; function globals() { return {result:undefined}; } function args() { return {nodes:nodes, edges:links}; } var lastEdges, lastTrees; function update(n, x, isRunning, duration, prev) { // Cheat a little and save the last values we see for trees and used. var trees = x.lookupInScope("trees"); if (trees) lastTrees = trees; else trees = lastTrees; var edges = x.lookupInScope("edges"); if (edges) lastEdges = edges; else edges = lastEdges; if (!edges) edges = links; if (duration < 0) { return; // Mostly state-less visualisation. } // Update nodes. var circle = svg.selectAll("circle").data(nodes); if (trees) { circle.style("fill", function(d) { var set = trees.setContaining(d); if (set) return set.data.colour; else return "black"; }); } else { circle.style("fill", null); } // Update links. var used = x.lookupInScope("usedEdges"); var result = x.lookupInScope("result"); if (result) used = result; if (!used) used = []; var checking = x.lookupInScope("edge"); var link = svg.selectAll("line").data(links); link.classed("selected", function(d) { return used.indexOf(d) !== -1; }); if (trees) { link.style("stroke", function(d) { if (used.indexOf(d) !== -1) { var set = trees.setContaining(d.target); if (set) return set.data.colour; } return null; }); } else { link.style("stroke", null); } link.classed("checking", function(d) { return d === checking; }); link.classed("notused", function(d) { return edges.indexOf(d) === -1 && used.indexOf(d) === -1 && d !== checking; }); } </script> </head> <body> <button onclick="newGraph()" style="position:absolute;left:0px;top:0px">New Graph</button> </body> </html> </syntax>

algorithm/kruskals.txt · Last modified: 2015/02/02 08:28 (external edit)