Scribd
Upload
27 views

Graph Theory Assignment 2

The document discusses implementations of Kruskal's and Prim's minimum spanning tree algorithms in C. It includes the code for both algorithms, applying them to sample graph data. It provides the output of running the code, showing the edges and total weight of the minimum spanning trees constructed.

Uploaded by

3017 Antara Mudi Cse Ai
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
27 views

Graph Theory Assignment 2

The document discusses implementations of Kruskal's and Prim's minimum spanning tree algorithms in C. It includes the code for both algorithms, applying them to sample graph data. It provides the output of running the code, showing the edges and total weight of the minimum spanning trees constructed.

Uploaded by

3017 Antara Mudi Cse Ai
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

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:

You might also like