MST-Prim(G,r)
for each u ∈ G.V
       u.key = ∞
	   u.pred = nil
	   r.key = 0
	   Q = G.V
while Q ≠ ∅
	 u = ExtractMin(Q)
	 for each v ∈ G.Adj[u]
	 if v ∈ Q and w(u,v) < v.key
	 v.pred = u
	 v.key = w(u,v)

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

// Define the maximum number of vertices in the graph
#define MAX_VERTICES 100

// Structure to represent a vertex
struct Vertex {
    int key;
    int pred;
};

// Function to extract the vertex with the minimum key from the queue
int extractMin(struct Vertex Q[], int size, bool visited[]) {
    int minIndex = -1;
    int minValue = INT_MAX;
    
    for (int i = 0; i < size; i++) {
        if (!visited[i] && Q[i].key < minValue) {
            minValue = Q[i].key;
            minIndex = i;
        }
    }
    
    return minIndex;
}

// Main Prim's algorithm function
void MST_Prim(int G[MAX_VERTICES][MAX_VERTICES], int numVertices, int r) {
    struct Vertex vertices[MAX_VERTICES];
    bool visited[MAX_VERTICES] = {false};
    
    // Initialize vertices
    for (int u = 0; u < numVertices; u++) {
        vertices[u].key = INT_MAX;
        vertices[u].pred = -1;
    }
    
    vertices[r].key = 0;
    
    for (int i = 0; i < numVertices; i++) {
        int u = extractMin(vertices, numVertices, visited);
        visited[u] = true;
        
        for (int v = 0; v < numVertices; v++) {
            if (G[u][v] && !visited[v] && G[u][v] < vertices[v].key) {
                vertices[v].pred = u;
                vertices[v].key = G[u][v];
            }
        }
    }
    
    // Print the minimum spanning tree
    printf("Edge   Weight\n");
    for (int i = 0; i < numVertices; i++) {
        if (vertices[i].pred != -1) {
            printf("%d - %d   %d\n", vertices[i].pred, i, vertices[i].key);
        }
    }
}

int main() {
    int numVertices, r;
    int G[MAX_VERTICES][MAX_VERTICES];
    
    printf("Enter the number of vertices: ");
    scanf("%d", &numVertices);
    
    printf("Enter the adjacency matrix:\n");
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            scanf("%d", &G[i][j]);
        }
    }
    
    printf("Enter the root vertex: ");
    scanf("%d", &r);
    
    MST_Prim(G, numVertices, r);
    
    return 0;
}