# Constructing The Minimum Spanning Tree for a Graph using Kruskal’s Algorithm

Kruskal’s algorithm is a minimum-spanning-tree algorithm where the algorithm finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph at each step.

```//To Construct the minimum spanning tre for a graph using Kruskal's Algorithm
import java.io.*;
class edge {
int u, v, cost;
}
class kruskal {
edge E[];
int n, t[][], p[], e;
void getdata() throws IOException {
System.out.println("Enter number of vertices: ");
System.out.println("Enter number of Edges: ");

E = new edge[20];
t = new int[n][3];
p = new int[n + 1];

for (int i = 1; i <= n; i++)
p[i] = -1;
for (int i = 1; i <= e; i++) {
edge x = new edge();
System.out.print("Source " + i + ":-\t");
System.out.print("Destin " + i + ":-\t");
System.out.print("Weight " + i + ":-\t");
E[i] = x;
System.out.println();
}
}
void sort() {
edge t = new edge();
for (int i = 1; i <= e - 1; i++)
for (int j = 1; j <= e - i; j++)
if (E[j].cost > E[j + 1].cost) {
t = E[j];
E[j] = E[j + 1];
E[j + 1] = t;
}
System.out.println("The sorted array is: ");
for (int i = 1; i <= e; i++)
System.out.println("An edge is :(" + E[i].u + "," + E[i].v + ") and cost :" + E[i].cost);
}
void union(int i, int j) {
p[i] = j;
}
int find(int i) {
while (p[i] > 0)
i = p[i];
return i;
}
int greedykruskal() {
int mincost, u, v, min, j, k;
int i = 1;
int q = 1;
mincost = 0;
System.out.println("Edges selected are: ");
while (i <= n - 1) {
u = E[q].u;
v = E[q].v;
min = E[q].cost;
j = find(u);
k = find(v);
if (j != k) {
mincost = mincost + min;
t[i][1] = u;
t[i][2] = v;
System.out.println("An edge(" + u + "," + v + ") with cost:" + min);
i++;
union(j, k);
}

q++;
}
if (i <= n - 1) {
System.out.println("A spanning tree cannot be formed ");
return 0;
} else
return mincost;
}
}
class testkruskal {
public static void main(String args[]) throws IOException {
kruskal ob = new kruskal();
ob.getdata();
ob.sort();
int m = ob.greedykruskal();
System.out.println("Minimum cost is : " + m);
}
}

/*-----------------------------------OUTPUT-------------------------

Enter number of vertices: 5

Enter number of Edges: 7

Source 1:- 1

Destin 1:- 3

Weight 1:- 13

Source 2:- 1

Destin 2:- 5

Weight 2:- 2

Source 3:- 1

Destin 3:- 2

Weight 3:- 11

Source 4:- 2

Destin 4:- 3

Weight 4:- 15

Source 5:- 2

Destin 5:- 4

Weight 5:- 8

Source 6:- 2

Destin 6:- 5

Weight 6:- 12

Source 7:- 4

Destin 7:- 5

Weight 7:- 14

The sorted array is:
An edge is :(1,5) and cost :2
An edge is :(2,4) and cost :8
An edge is :(1,2) and cost :11
An edge is :(2,5) and cost :12
An edge is :(1,3) and cost :13
An edge is :(4,5) and cost :14
An edge is :(2,3) and cost :15

Edges selected are:
An edge(1,5) with cost:2
An edge(2,4) with cost:8
An edge(1,2) with cost:11
An edge(1,3) with cost:13
Minimum cost is : 34
Process Exit...

*/
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.