lab2

 #include <stdio.h> 

#include <limits.h> 

#define V_MAX 100 // Maximum number of vertices 

// Function to find the vertex with the minimum key value, from the set of 

vertices not yet included in the MST 

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 print the constructed MST stored in parent[] 

void printMST(int parent[], int n, int graph[V_MAX][V_MAX], int V) { 

printf("Edge   Weight\n"); 

for (int i = 1; i < V; i++) 

printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]); 

} 

// Function to construct and print MST for a graph represented using 

adjacency matrix representation 

void primMST(int graph[][V_MAX], int V) { 

int parent[V_MAX]; // Array to store constructed MST 

int key[V_MAX]; // Key values used to pick minimum weight edge in cut 

int mstSet[V_MAX]; // To represent set of vertices not yet included in 

MST 

// Initialize all keys as INFINITE, mstSet[] as 0 

for (int i = 0; i < V; i++) 

key[i] = INT_MAX, mstSet[i] = 0; 

// Always include first 1st vertex in MST. Make key 0 so that this vertex 

is picked as the first vertex 

key[0] = 0; 

parent[0] = -1; // First node is always the root of MST 

// The MST will have V vertices 

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); 

12 

Department of CSE (CY), RNSIT         

IV Semester          BCSL404 – ADA LABORATORY 

 

Department of CSE (CY), RNSIT         13 

 

 

 

        // Add the picked vertex to the MST set 

        mstSet[u] = 1; 

 

        // Update key value and parent index of the adjacent vertices of the 

picked vertex 

        // Consider only those vertices which are not yet included in the MST 

        for (int v = 0; v < V; 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 

    printMST(parent, V, graph, V); 

} 

 

int main() { 

    int V, E; 

    printf("Enter the number of vertices and edges: "); 

    scanf("%d %d", &V, &E); 

 

    // Create the graph as an adjacency matrix 

    int graph[V_MAX][V_MAX]; 

    for (int i = 0; i < V; i++) { 

        for (int j = 0; j < V; j++) { 

            graph[i][j] = 0; // Initialize the graph with 0s 

        } 

    } 

 

    // Prompt the user to enter the source vertex, destination vertex, and 

weight for each edge 

    printf("Enter the source vertex, destination vertex, and weight for each 

edge:\n"); 

    for (int i = 0; i < E; i++) { 

        int source, dest, weight; 

        scanf("%d %d %d", &source, &dest, &weight); 

        graph[source][dest] = weight; 

        graph[dest][source] = weight; // Since the graph is undirected 

    } 

 

    // Print the MST using Prim's algorithm 

    primMST(graph, V); 

 

    return 0; 

}