WAP in C++ to find the minimum spanning tree using
Kruskal’s Algorithm and Prim’s Algorithm.
• Kruskal’s Algorithm:
Input:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
struct Edge
int src, dest, weight;
};
struct Graph
int V, E;
struct Edge* edge;
};
struct Graph* createGraph(int V, int E)
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));
return graph;
struct subset
int parent;
int rank;
};
int find(struct subset subsets[], int i)
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
void Union(struct 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 (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
int myComp(const void* a, const void* b)
struct Edge* a1 = (struct Edge*) a;
struct Edge* b1 = (struct Edge*) b;
return a1->weight > b1->weight;
void KruskalMST(struct Graph* graph)
int V = graph->V;
struct Edge result[V];
int e = 0;
int i = 0;
qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
struct subset *subsets = (struct subset*) malloc(V * sizeof(struct subset));
for (int v = 0; v < V; ++v)
subsets[v].parent = v;
subsets[v].rank = 0;
while (e < V - 1)
struct Edge next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y)
result[e++] = next_edge;
Union(subsets, x, y);
cout<<"Following are the edges in the constructed MST\n";
for (i = 0; i < e; ++i)
printf("%d -- %d == %d\n", result[i].src, result[i].dest,
result[i].weight);
return;
int main()
int V = 4;
int E = 5;
struct Graph* graph = createGraph(V, E);
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = 10;
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 6;
graph->edge[2].src = 0;
graph->edge[2].dest = 3;
graph->edge[2].weight = 5;
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 15;
graph->edge[4].src = 2;
graph->edge[4].dest = 3;
graph->edge[4].weight = 4;
KruskalMST(graph);
return 0;
}
output:
• Prim’s Algorithm:
Input:
#include <iostream>
#include <cstring>
using namespace std;
#define INF 9999
#define V 5
int G[V][V] = {
{0, 3, 0, 3, 0},
{3, 0, 0, 0, 4},
{0, 0, 0, 2, 1},
{3, 3, 2, 0, 0},
{0, 4, 1, 0, 0}};
int main () {
int num_edge;
int mst_vertex[V];
memset (mst_vertex, false, sizeof (mst_vertex));
num_edge = 0;
mst_vertex[0] = true;
int x;
int y;
cout<<"The Minimum Spanning Tree as per Prim's Algorithm:"<<endl;
cout << "Edge" << " : " << "Weight";
cout << endl;
while (num_edge < V - 1) {
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {
if (mst_vertex[i]) {
for (int j = 0; j < V; j++) {
if (!mst_vertex[j] && G[i][j]) {
if (min > G[i][j]) {
min = G[i][j];
x = i;
y = j;
cout << x << " - " << y << " : " << G[x][y];
cout << endl;
mst_vertex[y] = true;
num_edge++;
return 0;
}
output:
