| 23 | } |
| 24 | |
| 25 | PrimMST(start) { |
| 26 | // Prim's Algorithm to generate a Minimum Spanning Tree (MST) of a graph |
| 27 | // Details: https://en.wikipedia.org/wiki/Prim%27s_algorithm |
| 28 | const distance = {} |
| 29 | const parent = {} |
| 30 | const priorityQueue = new KeyPriorityQueue() |
| 31 | // Initialization |
| 32 | for (const node in this.connections) { |
| 33 | distance[node] = node === start.toString() ? 0 : Infinity |
| 34 | parent[node] = null |
| 35 | priorityQueue.push(node, distance[node]) |
| 36 | } |
| 37 | // Updating 'distance' object |
| 38 | while (!priorityQueue.isEmpty()) { |
| 39 | const node = priorityQueue.pop() |
| 40 | Object.keys(this.connections[node]).forEach((neighbour) => { |
| 41 | if ( |
| 42 | priorityQueue.contains(neighbour) && |
| 43 | distance[node] + this.connections[node][neighbour] < |
| 44 | distance[neighbour] |
| 45 | ) { |
| 46 | distance[neighbour] = |
| 47 | distance[node] + this.connections[node][neighbour] |
| 48 | parent[neighbour] = node |
| 49 | priorityQueue.update(neighbour, distance[neighbour]) |
| 50 | } |
| 51 | }) |
| 52 | } |
| 53 | |
| 54 | // MST Generation from the 'parent' object |
| 55 | const graph = new GraphWeightedUndirectedAdjacencyList() |
| 56 | Object.keys(parent).forEach((node) => { |
| 57 | if (node && parent[node]) { |
| 58 | graph.addEdge(node, parent[node], this.connections[node][parent[node]]) |
| 59 | } |
| 60 | }) |
| 61 | return graph |
| 62 | } |
| 63 | } |
| 64 | |
| 65 | export { GraphWeightedUndirectedAdjacencyList } |