53 lines
1.1 KiB
JavaScript
53 lines
1.1 KiB
JavaScript
|
var _ = require("../lodash");
|
||
|
|
var Graph = require("../graph");
|
||
|
|
var PriorityQueue = require("../data/priority-queue");
|
||
|
|
|
||
|
|
module.exports = prim;
|
||
|
|
|
||
|
|
function prim(g, weightFunc) {
|
||
|
|
var result = new Graph();
|
||
|
|
var parents = {};
|
||
|
|
var pq = new PriorityQueue();
|
||
|
|
var v;
|
||
|
|
|
||
|
|
function updateNeighbors(edge) {
|
||
|
|
var w = edge.v === v ? edge.w : edge.v;
|
||
|
|
var pri = pq.priority(w);
|
||
|
|
if (pri !== undefined) {
|
||
|
|
var edgeWeight = weightFunc(edge);
|
||
|
|
if (edgeWeight < pri) {
|
||
|
|
parents[w] = v;
|
||
|
|
pq.decrease(w, edgeWeight);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
if (g.nodeCount() === 0) {
|
||
|
|
return result;
|
||
|
|
}
|
||
|
|
|
||
|
|
_.each(g.nodes(), function(v) {
|
||
|
|
pq.add(v, Number.POSITIVE_INFINITY);
|
||
|
|
result.setNode(v);
|
||
|
|
});
|
||
|
|
|
||
|
|
// Start from an arbitrary node
|
||
|
|
pq.decrease(g.nodes()[0], 0);
|
||
|
|
|
||
|
|
var init = false;
|
||
|
|
while (pq.size() > 0) {
|
||
|
|
v = pq.removeMin();
|
||
|
|
if (_.has(parents, v)) {
|
||
|
|
result.setEdge(v, parents[v]);
|
||
|
|
} else if (init) {
|
||
|
|
throw new Error("Input graph is not connected: " + g);
|
||
|
|
} else {
|
||
|
|
init = true;
|
||
|
|
}
|
||
|
|
|
||
|
|
g.nodeEdges(v).forEach(updateNeighbors);
|
||
|
|
}
|
||
|
|
|
||
|
|
return result;
|
||
|
|
}
|