DS LAB 3/21/2025

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

#define V 5  

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

void printMST(int parent[], int graph[V][V]) {
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++) {
        printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
    }
}

void primMST(int graph[V][V]) {
    int parent[V];  
    int key[V];    
    bool mstSet[V];

    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX, mstSet[i] = false;
    }

    key[0] = 0;     // Start from the first vertex
    parent[0] = -1; // First node is always root of MST

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u, key[v] = graph[u][v];
            }
        }
    }

    printMST(parent, graph);
}

int main() {
    int graph[V][V] = {
        {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}
    };

    primMST(graph);

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

C-Programming of Class 12

1. Write a program to input any three numbers and find out which one is the largest number using user defined function.       #include<stdio.h> int larg_num(int num1, int num2, int num3){     if(num1 >= num2 && num1 >= num3){         return num1;     }else if(num2 >=num1 && num2>=num3){         return num2;     }     else{         return num3;     } } int main(){ int num1, num2, num3; scanf("%d%d%d", &num1,&num2,&num3); int largest = larg_num(num1,num2,num3); printf("the largest number is %d",largest);     return 0; } 2. Write a program to display the day using the switch statement depending upon the number entered. i.e. input 1 for Sunday, 7 for Saturday using user defined  function. #include <stdio.h> char *days(int num) {     switch (num)     {     case 1:   ...
Read more

C-Program of Class 11

 1. Define string. Explain any four-string handling function used in C. A String in C programming is a sequence of characters terminated with a null character ‘\0’. The C String is stored as an array of characters. #include <stdio.h> #include <string.h> int main() {     char str1[20] = "Hello";     char str2[20] = "World";     char str3[20];     strcpy(str3, str1);     printf("Copied string: %s\n", str3);     strcat(str2, str1);     printf("Concatenates string: %s\n", str1);     printf("Length of str1: %lu\n", strlen(str1));     if (strcmp(str1, str2) == 0)         printf("str1 and str2 are equal\n");     else if (strcmp(str1, str2) < 0)         printf("str1 is less than str2\n");     else         printf("str1 is greater than str2\n");     return 0; } strcat(): Concatenates (joins) two stri...
Read more