GRAPH THEORY AND COMBINATORICS ASSIGNMENT(2)
NAME: ANTARA MUDI
STUDENT’S ID: 211003003017
STREAM: B.TECH CSE AI
BATCH: BCS AI 2A
SUBJECT: GRAPH THEORY AND COMBINATORICS
ASSIGNED BY: SUKUMAR CHAKRABORTY SIR
KRUSKAL’S MINIMUM SPANNING TREE
#include <stdio.h>
#include <stdlib.h>
int compare(const void* p1, const void* p2)
const int(*x)[3] = p1;
const int(*y)[3] = p2;
return (*x)[2] - (*y)[2];
void makeSet(int parent[], int rank[], int n)
for (int i = 0; i < n; i++)
parent[i] = i;
rank[i] = 0;
int findParent(int parent[], int c)
if (parent[c] == c)
{return c;}
return parent[c] = findParent(parent, parent[c]);
void unionSet(int u, int v, int parent[], int rank[], int n)
u = findParent(parent, u);
v = findParent(parent, v);
if (rank[u] < rank[v])
{parent[u] = v;}
else if (rank[u] > rank[v])
{parent[v] = u;}
else {
parent[v] = u;
rank[u]++;
void kruskal(int n, int edge[n][3])
{ //sorting the edges first using the qsort function
qsort(edge, n, sizeof(edge[0]), compare);
int parent[n];
int rank[n];
makeSet(parent, rank, n);
int totalweight = 0;
printf("Edges in the Minimum Spanning Tree:\n");
for (int i = 0; i < n; i++) {
int v1 = findParent(parent, edge[i][0]);
int v2 = findParent(parent, edge[i][1]);
int wt = edge[i][2];
if (v1 != v2) {
unionSet(v1, v2, parent, rank, n);
totalweight += wt;
printf("(%d,%d) --> \t%d\n", edge[i][0],edge[i][1], wt);
printf("Total weight:%d\n",totalweight);
}
int main()
{//(source vertex,destination vertex,weight of the edge)
int edge[11][3] = {{1,2,10},{1,4,12},{2,3,15},{2,5,18},
{3,4,20},{3,5,8},{3,6,14},{4,5,5},
{4,6,50},{5,7,11},{6,7,17}
};
kruskal(11, edge);
return 0;
OUTPUT:
PRIM’S MINIMUM SPANNING TREE
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#define V 7
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])
{int totalweight=0;
printf("EDGES IN THE MST -\n");
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++)
{ printf("%d - %d \t%d \n", parent[i], i,
graph[i][parent[i]]);
totalweight+=graph[i][parent[i]]; }
printf("\nTOTAL WEIGHT=%d",totalweight);
}
void prim(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;
parent[0] = -1;
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] == false
&& graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
printMST(parent, graph);
}
int main()
{ int graph[V][V]={{0,10,0,12,0,0,0},
{10,0,15,0,18,0,0},
{0,15,0,20,8,14,0},
{12,0,20,0,5,50,0},
{0,18,8,5,0,0,11},
{0,0,14,50,0,0,17},
{0,0,0,0,11,17,0}
};//adjacency matrix for the graph
prim(graph);
OUTPUT:
