C++ Prim's Algorithm for Minimum Spanning Tree (MST) Implementation

This is a C++ implementation of Prim's algorithm to find the Minimum Spanning Tree (MST) of a graph. The code consists of three main functions:

• minKey function: This function takes an array of key values (key[]) and a boolean array (mstSet[]) indicating which vertices are already included in the MST, along with the number of vertices (V). It returns the index of the vertex with the minimum key value that is not yet included in the MST.

• printMST function: This function takes an array of parent nodes (parent[]), the adjacency matrix of the graph (graph[][]), and the number of vertices (V). It prints the edges of the constructed MST along with their corresponding weights.

• primMST function: This function takes the adjacency matrix of the graph (graph[][]) and the number of vertices (V) as input. It implements Prim's algorithm to find the MST. It initializes a key array to store the minimum edge weights from the source vertex to other vertices, a mstSet array to keep track of vertices included in the MST, and a parent array to store the parent nodes of each vertex in the constructed MST.

The algorithm iteratively selects the vertex with the minimum key value not yet included in the MST, updates the key values for adjacent vertices, and adds the selected vertex to the MST. The printMST function then displays the resulting MST.

int minKey(int key[], bool mstSet[], int V) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (mstSet[v] == false && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}

void printMST(int parent[], int **graph, int V) {
    cout << 'Edge' << '\t' << 'Weight' << '\n';
    for (int i = 1; i < V; i++)
        cout << parent[i] << ' - ' << i << '\t' << graph[i][parent[i]] << ' \n';
}

void primMST(int **graph, int V) {
    int parent[V]; // to store constructed MST
    int key[V]; // key values used to pick minimum weight edge in cut
    bool mstSet[V]; // to represent set of vertices not yet included in MST
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }
    key[0] = 0; // always include first vertex in MST
    parent[0] = -1; // first node is root of MST
    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet, V); // pick the minimum key vertex from the set of vertices not yet included in MST
        mstSet[u] = true; // add the picked vertex to the MST Set
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
    printMST(parent, graph, V); // print the constructed MST
}

This code provides a clear and efficient implementation of Prim's algorithm, making it a valuable resource for understanding and applying this important graph algorithm.