prim's algo P5

 #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 V, int graph[V_MAX][V_MAX]) {

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


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

}


int main() {

    int V, E;

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

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


    if (V > V_MAX) {

        printf("Error: Number of vertices exceeds the maximum limit.\n");

        return 1;

    }


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

}


Comments

Post a Comment

Popular posts from this blog

kruskal algo P4

 #include <stdio.h> #include <stdlib.h> #define MAX_EDGES 1000 typedef struct Edge {     int src, dest, weight; } Edge; typedef struct Graph {     int V, E;     Edge edges[MAX_EDGES]; } Graph; typedef struct Subset {     int parent, rank; } Subset; Graph* createGraph(int V, int E) {     Graph* graph = (Graph*) malloc(sizeof(Graph));     graph->V = V;     graph->E = E;     return graph; } int find(Subset subsets[], int i) {     if (subsets[i].parent != i) {         subsets[i].parent = find(subsets, subsets[i].parent);     }     return subsets[i].parent; } void Union(Subset subsets[], int x, int y) {     int xroot = find(subsets, x);     int yroot = find(subsets, y);     if (subsets[xroot].rank < subsets[yroot].rank) {         subsets[xroot].parent = yroot;     } else if (subs...
Read more

topological sort P6

 #include <stdio.h> #include <stdlib.h> #define MAX_VERTICES 100 // Structure to represent a graph typedef struct {     int V;     int** adjMatrix; } Graph; // Function to create a new graph Graph* createGraph(int V) {     Graph* graph = (Graph*)malloc(sizeof(Graph));     graph->V = V;     graph->adjMatrix = (int**)calloc(V, sizeof(int*));     for (int i = 0; i < V; i++) {         graph->adjMatrix[i] = (int*)calloc(V, sizeof(int));     }     return graph; } // Function to add an edge to the graph void addEdge(Graph* graph, int src, int dest) {     graph->adjMatrix[src][dest] = 1; } // Function to perform topological sorting void topologicalSort(Graph* graph) {     int V = graph->V;     int inDegree[MAX_VERTICES] = {0};     int queue[MAX_VERTICES], front = 0, rear = -1;     // Calculate in-degree (number o...
Read more