Implementing Prim’s MST algorithm with adjacency matrix

  algorithm, c++, graph

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] = 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),
https://drive.google.com/file/d/1M5RjxE8nu1BUbh64J3QSYHjmv9FV3jrv/view?usp=sharing (input), https://drive.google.com/file/d/1-ecO1yfs9sjarb0gXT3PBEIneaiWDLNc/view?usp=sharing.

Thanks for your help!

Source: Windows Questions C++

LEAVE A COMMENT