Implementation of Prim’s Algorithm

Understanding Prim’s Algorithm

Prim’s algorithm builds a minimum spanning tree (MST) for a connected, weighted graph. It does this by starting from an arbitrary vertex and progressively adding the smallest edge that connects a vertex in the MST to a vertex outside the MST.

Key Concepts:

1. Initialization:
   • Start with a vertex (commonly the first vertex) and include it in the MST.
   • Use arrays to keep track of the minimum edge weights, the included vertices, and the parent of each vertex for tracing the MST.
2. Selecting Minimum Edges:
   • Use a helper function to find the vertex with the smallest key (edge weight) that has not yet been included in the MST.
   • Mark this vertex as included in the MST.
3. Updating Key Values:
   • For each adjacent vertex of the newly included vertex, check if the edge weight is smaller than the current key value of that vertex.
   • If it is, update the key value and record the parent of that vertex.
4. Repeat:
   • Continue this process until all vertices have been included in the MST.

#include <stdio.h>
#include <limits.h>

#define MAX 100

// Function to find the vertex with minimum key value
int minKey(int key[], int mstSet[], int V) {
    int min = INT_MAX, min_index;

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

// Function to implement Prim's algorithm
void prim(int graph[MAX][MAX], int V) {
    int parent[MAX]; // Array to store constructed MST
    int key[MAX];    // Key values used to pick minimum weight edge
    int mstSet[MAX]; // To represent the vertices included in MST

    // Initialize all keys as INFINITE
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = 0;
    }

    // Always include the first vertex in the MST
    key[0] = 0;     // Make key 0 so that this vertex is picked first
    parent[0] = -1; // First node is always the root of MST

    for (int count = 0; count < V - 1; count++) {
        // Pick the minimum key vertex from the set of vertices not yet included in MST
        int u = minKey(key, mstSet, V);
        mstSet[u] = 1; // Add the picked vertex to the MST

        // Update key value and parent index of the adjacent vertices of the picked vertex
        for (int v = 0; v < V; v++) {
            // Update key only if graph[u][v] is smaller than key[v]
            if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    // Print the constructed MST
    printf("Edges in the Minimum Spanning Tree (Prim's Algorithm):\n");
    for (int i = 1; i < V; i++) {
        printf("%d -- %d == %d\n", parent[i], i, graph[i][parent[i]]);
    }
}

// Main function
int main() {
    int V;
    int graph[MAX][MAX];

    printf("Enter number of vertices: ");
    scanf("%d", &V);

    printf("Enter the adjacency matrix:\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    prim(graph, V);

    return 0;
}

Explanation of Each Part:

1. Finding the Minimum Key:
   • The function minKey scans the key array to find the vertex with the smallest key value that hasn’t been included in the MST yet.
   • This function helps in selecting the next vertex to include in the MST.
2. Initializing the MST:
   • The prim function initializes key, parent, and mstSet arrays:
     • key[] is initialized to a large value (INT_MAX) to represent that all vertices are initially disconnected.
     • mstSet[] keeps track of which vertices are included in the MST (initialized to 0).
     • parent[] records the parent vertex for each vertex, helping to reconstruct the MST later.
3. Main Loop:
   • The main loop runs V - 1 times, since a minimum spanning tree with V vertices will have V - 1 edges.
   • Inside the loop:
     • We call minKey to get the next vertex u with the smallest key value.
     • We mark u as included in the MST by setting mstSet[u] = 1.
     • We then update the key values for all adjacent vertices of u. If an edge to a vertex v has a smaller weight than the current key for v, we update key[v] and set parent[v] to u.
4. Output:
   • After the loop completes, we print the edges included in the MST. The parent array helps trace back the connections.

Sample Input and Output for Prim’s Algorithm

Input:

mathematicaCopy codeEnter number of vertices: 5
Enter the adjacency matrix:
0 2 0 6 0
2 0 3 8 5
0 3 0 0 7
6 8 0 0 9
0 5 7 9 0

Output:

mathematicaCopy codeEdges in the Minimum Spanning Tree (Prim's Algorithm):
0 -- 1 == 2
1 -- 2 == 3
1 -- 4 == 5
0 -- 3 == 6

Conclusion

Prim’s algorithm efficiently finds the minimum spanning tree by gradually adding the lowest weight edges while ensuring no cycles are formed. This algorithm is particularly effective for dense graphs represented using adjacency matrices. If you have any further questions or need additional examples, feel free to ask!