Name: Ria Talsania

UID: 2023300242

Experiment No. 5.1

Date of Submission 04/03/25

AIM: Experiment on Graphs: To understand Graphs and implement Prim’s and Kruskal’s
Algorithm to find Minimum Spanning Trees.

Program 1

Objectives: 1. To learn Kruskal’s Algorithm

2. To find MST’s using Kruskal’s Algorithm
3. To find the best, worst and average cases of each algorithm and
find time and space complexity for each

Theory:
Kruskal’s Algorithm:

Kruskal’s algorithm sorts all edges by weight and greedily picks the smallest edge
that does not form a cycle, using the Union-Find data structure to manage
connected components.

Step 1: Sort the Edges

 All edges are sorted in ascending order of weight.

 Always pick the smallest edge first, which helps in building the Minimum
Spanning Tree (MST) optimally.

Step 2: Iterate Through the Sorted Edges

 Start picking edges one by one from the sorted list.

 For each edge (u, v, weight), we check if adding it creates a cycle.

Step 3: Cycle Detection using Union-Find

 We use the Union-Find data structure to efficiently check whether two nodes
belong to the same set (connected component).

 If u and v belong to different sets, we merge them (union) and add the edge to
the MST.

 If they are already in the same set, we skip the edge to avoid a cycle.
Step 4: Repeat Until We Get (V-1) Edges

 The MST must have exactly (V-1) edges, where V is the number of vertices.

 Once we reach this count, the MST is complete, and we stop adding edges.

Kruskal’s Time and Space Complexity:

Program 2

Problem: Kruskal’s

#include <stdio.h>
Program:
#include <stdlib.h>

#define MAX 100

int parent[MAX], rank[MAX];

int findP(int v) {
if (parent[v] != v)
parent[v] = findP(parent[v]);
return parent[v];
}

void unionSets(int v1, int v2) {

int r1 = findP(v1);
int r2 = findP(v2);

if (r1 != r2) {
if (rank[r1] > rank[r2])
parent[r2] = r1;
else if (rank[r1] < rank[r2])
parent[r1] = r2;
else {
parent[r2] = r1;
rank[r1]++;
}
}
}

int partition_array(int edges[MAX][3], int low, int high) {

int pivot = edges[high][2];
int i = low - 1;

for (int j = low; j < high; j++) {

if (edges[j][2] <= pivot) {
i++;
for (int k = 0; k < 3; k++) {
int temp = edges[i][k];
edges[i][k] = edges[j][k];
edges[j][k] = temp;
}
}
}
for (int k = 0; k < 3; k++) {
int temp = edges[i + 1][k];
edges[i + 1][k] = edges[high][k];
edges[high][k] = temp;
}
return i + 1;
}

void recursive_quick_sort(int edges[MAX][3], int low, int high) {

if (low < high) {
int pivot = partition_array(edges, low, high);
recursive_quick_sort(edges, low, pivot - 1);
recursive_quick_sort(edges, pivot + 1, high);
}
}

void kruskals(int edges[MAX][3], int V, int E) {

int result[MAX][3], e = 0, i = 0, totalCost = 0;

recursive_quick_sort(edges, 0, E - 1);

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

parent[v] = v;
rank[v] = 0;
}
while (e < V - 1 && i < E) {
int *edge = edges[i++];
int x = findP(edge[0]);
int y = findP(edge[1]);

if (x != y) {
result[e][0] = edge[0];
result[e][1] = edge[1];
result[e][2] = edge[2];
totalCost += edge[2];
e++;
unionSets(x, y);
}
}

printf("Minimum Spanning Tree:\n");

for (i = 0; i < e; i++) {
printf("%d -- %d == %d\n", result[i][0], result[i][1], result[i]
[2]);
}
printf("Total cost of Minimum Spanning Tree: %d\n", totalCost);
}

int main() {
int V, E, edges[MAX][3];
printf("Enter number of vertices and edges: ");
scanf("%d %d", &V, &E);

printf("Enter edges (source destination weight):\n");

for (int i = 0; i < E; i++) {
scanf("%d %d %d", &edges[i][0], &edges[i][1], &edges[i][2]);
}

kruskals(edges, V, E);

return 0;
}
Example 1

Output:

Dry Run:
Observations:

Kruskal’s Algorithm:

QuickSort Best case: When partitions are balanced (E Log E).

Union-Find Compression used: Makes sure that when we look for a node’s leader,

we directly connect it to the topmost parent.

This way, future searches become much faster, reducing the time taken from slow,

(O(V)), almost instant (O(1)) for large graphs.

Conclusion:

Kruskal’s algorithms efficiently construct a Minimum Spanning Tree (MST)

while making locally optimal choices at each step.

From Kruskal’s algorithm, I observed that sorting edges by weight and merging
components using the Union-Find technique allows us to construct the MST efficiently,

making it ideal for sparse graphs.