Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | 16x 4x 4x 4x 12x 12x 12x 6x 6x 5x 5x 4x 1x 3x 8x 8x 3x 3x 3x 8x 8x 4x 4x 1x 3x 7x 2x | import Graph, { DefaultEdgeType } from '../Graph';
import PriorityQueue from './PriorityQueue';
const prim = <NodeIdType, NodeType, EdgeType>(
graph: Graph<NodeIdType, NodeType, EdgeType>,
weightFn: (node: DefaultEdgeType<NodeIdType, EdgeType>) => number,
) => {
const result = new Graph<NodeIdType, NodeType, EdgeType>();
const parents = new Map<NodeIdType, NodeIdType>();
const pq = new PriorityQueue<NodeIdType>();
let v: NodeIdType;
function updateNeighbors(edge: DefaultEdgeType<NodeIdType, EdgeType>) {
const w = edge.v === v ? edge.w : edge.v;
const pri = pq.priority(w);
if (pri !== undefined) {
const edgeWeight = weightFn(edge);
if (edgeWeight < pri) {
parents.set(w, v);
pq.decrease(w, edgeWeight);
}
}
}
if (graph.nodeCount() === 0) {
return result;
}
graph.nodes().forEach((node) => {
pq.add(node, Number.POSITIVE_INFINITY);
result.setNode(node);
});
// Start from an arbitrary node
pq.decrease(graph.nodes()[0], 0);
let init = false;
while (pq.size() > 0) {
v = pq.removeMin()!;
if (parents.has(v)) {
result.setEdge(v, parents.get(v)!);
} else if (init) {
throw new Error('Input graph is not connected: ' + graph.graph());
} else {
init = true;
}
graph.nodeEdges(v)?.forEach(updateNeighbors);
}
return result;
};
export default prim;
|