#### Implementing Prim’s MST algorithm with adjacency matrix

I am learning about MSTs and right now I am trying to implement Prim’s algorithm (the O(V^2) version, suitable for dense graphs) in C++. Although the code works fine for small inputs, I have come across some bigger test cases where my program doesn’t correctly compute the total weight of the MST and I really can’t figure out where the bug is. I have drawn inspiration from multiple online variants of this algorithm (geeksforgeeks etc), but with no success. This is the bread and butter of my code:

``````void prim(){
for (int i = 0; i < V; ++i)
parent[i] = -1, inMST[i] = false, key[i] = INT_MAX;

key = 0;

for (int i = 0; i < V; ++i)
{
int mn = INT_MAX, index;

for (int j = 0; j < V; ++j)
if (inMST[j] == false && key[j] <= mn)
mn = key[j], index = j;

int u = index;

inMST[u] = true;

total_weight += key[u];

for (int j = 0; j < V; ++j)
if (inMST[j] == false && W[u][j] < key[j])
key[j] = W[u][j], parent[j] = u;
}
}
``````

Here is the test case that doesn’t work and the full version of my program: https://drive.google.com/file/d/1HeUIfCbwCn2U5v9nMUmDWnD0Irt0JETZ/view?usp=sharing (expected output),