Scribd
Upload
4 views2 pages

DAA Lab Program-5.

The document provides a C program that implements Prim's algorithm to find the Minimum Cost Spanning Tree of a connected undirected graph. It includes functions to find the minimum key, print the MST, and construct the MST using a given graph. The program initializes the graph, executes the algorithm, and outputs the edges and their weights in the MST.

Uploaded by

bhargavi.desh2411
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
4 views2 pages

DAA Lab Program-5.

The document provides a C program that implements Prim's algorithm to find the Minimum Cost Spanning Tree of a connected undirected graph. It includes functions to find the minimum key, print the MST, and construct the MST using a given graph. The program initializes the graph, executes the algorithm, and outputs the edges and their weights in the MST.

Uploaded by

bhargavi.desh2411
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

5.

Find Minimum Cost Spanning Tree of a given connected


undirected graph using Prim's algorithm. Write the program in C

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

#define V 5 // Number of vertices in the graph

int minKey(int key[], bool mstSet[])


{
int min = INT_MAX, min_index;

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


if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;

return min_index;
}

int 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]; // Array to store constructed MST
int key[V]; // Key values used to pick minimum weight edge in cut
bool mstSet[V]; // To represent set of vertices not yet included in MST

// Initialize all keys as INFINITE


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

// Always include first vertex in MST.


key[0] = 0;
parent[0] = -1; // First node is always root of MST
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);

// Add the picked vertex to the MST Set


mstSet[u] = true;

// Update key and parent index of the adjacent vertices of the picked
vertex.
for (int v = 0; v < V; v++)

// graph[u][v] is non-zero only for adjacent vertices of m


// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}

// print the constructed MST


printMST(parent, graph);
}

// Driver code
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 } };

// Print the solution


primMST(graph);

return 0;
}

You might also like