| 10 | * @see https://en.wikipedia.org/wiki/Prim%27s_algorithm |
| 11 | */ |
| 12 | export const prim = (graph: [number, number][][]): [Edge[], number] => { |
| 13 | if (graph.length == 0) { |
| 14 | return [[], 0] |
| 15 | } |
| 16 | const minimum_spanning_tree: Edge[] = [] |
| 17 | let total_weight = 0 |
| 18 | |
| 19 | const priorityQueue = new PriorityQueue( |
| 20 | (e: Edge) => { |
| 21 | return e.b |
| 22 | }, |
| 23 | graph.length, |
| 24 | (a: Edge, b: Edge) => { |
| 25 | return a.weight < b.weight |
| 26 | } |
| 27 | ) |
| 28 | const visited = new Set<number>() |
| 29 | |
| 30 | // Start from the 0'th node. For fully connected graphs, we can start from any node and still produce the MST. |
| 31 | visited.add(0) |
| 32 | add_children(graph, priorityQueue, 0) |
| 33 | |
| 34 | while (!priorityQueue.isEmpty()) { |
| 35 | // We have already visited vertex `edge.a`. If we have not visited `edge.b` yet, we add its outgoing edges to the PriorityQueue. |
| 36 | const edge = priorityQueue.extract() |
| 37 | if (visited.has(edge.b)) { |
| 38 | continue |
| 39 | } |
| 40 | minimum_spanning_tree.push(edge) |
| 41 | total_weight += edge.weight |
| 42 | visited.add(edge.b) |
| 43 | add_children(graph, priorityQueue, edge.b) |
| 44 | } |
| 45 | |
| 46 | return [minimum_spanning_tree, total_weight] |
| 47 | } |
| 48 | |
| 49 | const add_children = ( |
| 50 | graph: [number, number][][], |