#### Prim MST

u
s
L
p
T
S
a
and 4 more contributors
```import { KeyPriorityQueue } from '../Data-Structures/Heap/KeyPriorityQueue'
// Weighted Undirected Graph class
constructor () {
this.connections = {}
}

// Function to add a node to the graph (connection represented by set)
this.connections[node] = {}
}

// Function to add an edge (adds the node too if they are not present in the graph)
if (!(node1 in this.connections)) { this.addNode(node1) }
if (!(node2 in this.connections)) { this.addNode(node2) }
this.connections[node1][node2] = weight
this.connections[node2][node1] = weight
}

PrimMST (start) {
// Prim's Algorithm to generate a Minimum Spanning Tree (MST) of a graph
// Details: https://en.wikipedia.org/wiki/Prim%27s_algorithm
const distance = {}
const parent = {}
const priorityQueue = new KeyPriorityQueue()
// Initialization
for (const node in this.connections) {
distance[node] = (node === start.toString() ? 0 : Infinity)
parent[node] = null
priorityQueue.push(node, distance[node])
}
// Updating 'distance' object
while (!priorityQueue.isEmpty()) {
const node = priorityQueue.pop()
Object.keys(this.connections[node]).forEach(neighbour => {
if (priorityQueue.contains(neighbour) && distance[node] + this.connections[node][neighbour] < distance[neighbour]) {
distance[neighbour] = distance[node] + this.connections[node][neighbour]
parent[neighbour] = node
priorityQueue.update(neighbour, distance[neighbour])
}
})
}

// MST Generation from the 'parent' object