If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.
Kruskal’s Algorithm solves the problem of finding a Minimum Spanning Tree(MST) of any given connected and undirected graph.
What is a Minimum Spanning Tree?
It is basically a subgraph of the given graph that connects all the vertices with minimum number of edges having minimum possible weight with no cycle. As this graph contains no cycle, that’s why it is called a Tree.
There can be more than one possible MST depending on the given graph.
For connecting all the vertices in the given graph we need to have atleast vertices-1 edges.
Why?
Consider a graph with only two nodes, we can connect these two nodes with one edge. At this point we have, 2 vertices & one edge. Now if we want to include one more vertex in the graph with minimum possible vertices, we need to have an edge going from the current graph to this new vertex to be added. That is, for every incoming node, we need to add an edge.
Therefore both vertices and edges will increase by one and number of vertices will always be edges+1, this implies, number of edges = vertices-1
Algorithm
Kruskal’s is a greedy approach which emphasizes on the fact that we must include only those (vertices-1) edges only in our MST which have minimum weight amongst all the edges, keeping in mind that we do not include such edge that creates a cycle in MST being constructed.
- We keep a list of all the edges sorted in an increasing order according to their weights.
- Take an edge from the list, check if it creates a cycle in the
MSTbeing constructed,- if it does not create any cycle, then we include the edge in our MST being constructed.
- if it creates a cycle, then we skip the current edge and move on to the next edge in the sorted list.
- We need to repeat the same process again until we have
(Vertices-1)edges in the final Minimum Spanning Tree.
For all this, We use Disjoint Set Union data structure which helps us in constructing the MST and checking if there exists any cycle in the MST if we include the current edge.
Here’s how we use Disjoint set union to do this :
- Initially, every vertex is a
disjoint setin itself and for adding an edge in between two vertices we need to merge the sets containing these two vertices. - Every set has their own parent which represents the whole disjoint set and merging of two sets basically means, making the parents of the
two sets same. - Set having lesser number of vertices will merge with the set having higher number of elements and merging is simply done by making the
parent of bigger set equal to the parent of smaller set.
Now for checking cycle, we see if the current two vertices of the current edge lie in the same set or not.
- If they
do notlie in thesame set, then it is okay to include this edge in the MST as the two vertices of this current edge are in separate sets and there is exist no path from first vertex to other directly or indirectly, that is why they are intwo DISJOINT sets, and adding an edge directly from V1 to V2 will not create any cycle. - If they lie in the
same set, this means that they are either directly or indirectly connected to each other with minimum number of edges possible(with minimum weights) and adding one more edge will again connect them creating a cycle in theMinimum Spanning Treebeing constructed.
While implementing this algorithm, Along with maintaining a list of sorted edges, we need to maintain two arrays also, that is, parent array and size array, which keeps the tracks of disjoint sets.
Parent array tells the parent/representative of the set of any ith vertex.
Size array, for any vertex, keeps the track of number of vertices in the disjoint set of any ith vertex.
Initially, parent of any vertex is that vertex only with the size of its set equal to 1 as this vertex is the only element in its disjoint set.
that is,
Parent[i] = i
size[i] = 1
Consider this graph,
To find the Minimum Spanning tree of this given bidirectional graph, we first need to sort all the edges in a non-decreasing order.
edge (D, E) with weight = 1
edge (F, E) with weight = 2
edge (A, F) with weight = 3
edge (F, B) with weight = 4
edge (B, E) with weight = 5
edge (A, B) with weight = 6
edge (A, E) with weight = 7
edge (C, E) with weight = 8
edge (D, C) with weight = 8
edge (B, C) with weight = 9
Parent = {0, 1, 2, 3, 4, 5}
Size = {1, 1, 1, 1, 1, 1}
vertex A at 0th index
vertex B at 1st index
vertex C at 2nd index
vertex D at 3rd index
vertex E at 4th index
vertex F at 5th index
In the given graph, each colour represents their own disjoint set, and as we know initially all the nodes are a disjoint set in their own, hence all vertices are uniquely coloured.
Edge-1:
We are currently at edge (D, E) with weight = 1 being the smallest amongst all.
First check if inclusion of this edge creates any cycle or not.
D & E are in different set therefore, no cycle will be formed if we include this edge, therefore we can include this edge.
Parent = {0, 1, 2, 4, 4, 5}Size = {1, 1, 1, 1, 2, 1}
parent [D] = E
Size [E] = Size [E] + Size [D]
Edge-2:
We are currently at edge (F, E) with weight = 2
First check if inclusion of this edge creates any cycle or not.
F & E are in different set therefore, no cycle will be formed if we include this edge, therefore we can include this edge and perform union operation on the two disjoint sets having F and E.
Parent = {0, 1, 2, 4, 4, 4}Size = {1, 1, 1, 1, 3, 1}
parent [F] = E
Size [E] = Size [E] + Size [F]
Edge-3:
We are currently at edge (A, F) with weight = 3
First check if inclusion of this edge creates any cycle or not.
F & A are in different set therefore, no cycle will be formed if we include this edge, therefore we can include this edge and perform union operation on the two disjoint sets having A and F.
Now, for combining disjoint sets of A and F, we need to make parent of A equal to F, but here we see, F is not the parent of its own set, this implies that parent of A will not be F, instead parent of A will be the parent of F.
Parent = {4, 1, 2, 4, 4, 4}Size = {1, 1, 1, 1, 4, 1}
parent [A] = parent [F] = E
Size [E] = Size [E] + Size [A]
Edge-4:
We are currently at edge (F, B) with weight = 4
First check if inclusion of this edge creates any cycle or not.
F & B are in different set therefore, no cycle will be formed if we include this edge, therefore we can include this edge and perform union operation on the two disjoint sets having A and F.
Now, for combining disjoint sets of B and F, we will make parent of F as parent of B and not F directly.
Parent = {4, 4, 2, 4, 4, 4}Size = {1, 1, 1, 1, 5, 1}
parent [B] = parent [F] = E
Size [E] = Size [E] + Size [B]
Edge-5:
We are currently at edge (B, E) with weight = 5.
But, inclusion of this edge creates a cycle as B and E are in same set because parent [B] = Parent [E] = E, and adding a direct edge between B and E will form a cycle in the MST being constructed.
Therefore, we skip this edge.
For edge (A, B), this edge will also create a cycle, with the reason being the same, A and B are in the same disjoint set, with the parent of their set equal to E and adding a direct edge between A and B will form a cycle in the MST being constructed.
Therefore, we skip this edge also.
For edge (A, E), this edge will also create a cycle, with the reason being the same, A and E are in the same disjoint set, with the parent of their set equal to E and adding a direct edge between A and E will form a cycle in the MST being constructed.
Therefore, we skip this edge also.
Now, for edge (C, E) with weight = 8,
First check if inclusion of this edge creates any cycle or not.
C & E are in different set therefore, no cycle will be formed if we include this edge, therefore we can include this edge and perform union operation on the two disjoint sets having C and E.
Now, for combining disjoint sets of C and E, we will make E as parent of B.
Parent = {4, 4, 4, 4, 4, 4}Size = {1, 1, 1, 1, 6, 1}
parent [C] = E
Size [E] = Size [E] + Size [C]
Now, we have included a total of 5 edges in minimum spanning tree which is equal the minimum number of edges required to connect all the vertices and parent of all the vertices will be a common vertex now.
Therefore we terminate our algorithm here.
Finally, this is Minimum Spanning Tree obtained after applying Kruskal’s Algorithm.
Time Complexity :
Sorting of edges = E log E
now, for (V – 1) times, we performed, union operation and checked for cycle, this may seem like an O(1) operation , but this consisted of finding the parents of both the vertices on any edge whose time complexity is O(Log V).
And as we know potential number of edges in any graph can be upto V^2.
Therefore Overall time Complexity for Kruskal’s Algorithm is O(E log E)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 |
package Graphs; import java.util.Arrays; import java.util.Scanner; public class kruskals { public static class edge implements Comparable<edge> { int u; int v; int weight; public edge(int u, int v, int weight) { this.u = u; this.v = v; this.weight = weight; } public String toString() { return this.u + " " + this.v + " " + this.weight; } // sorting of the edges will be done on the basis of weights. @Override public int compareTo(edge o) { return this.weight - o.weight; } } public static void main(String[] args) { Scanner scn = new Scanner(System.in); int nodes = scn.nextInt(); int[][] graph = new int[nodes + 1][nodes + 1]; int numEdges = scn.nextInt(); edge[] edges = new edge[numEdges]; for (int edge = 0; edge < numEdges; edge++) { int u = scn.nextInt(), v = scn.nextInt(), w = scn.nextInt(); /* * as the graph will be bidirectional then 'v' will be * neighbour of 'u' and vice-versa */ graph[u][v] = graph[v][u] = w; /* add the edge in the edges array which will be * sorted later */ edges[edge] = new edge(u, v, w); } kruskalsAlgo(nodes, numEdges, edges, graph); } public static void kruskalsAlgo(int numVertices, int numEdges, edge[] edges, int[][] graph) { /* for storing minimum spanning tree formed */ int[][] mst = new int[graph.length][graph.length]; /* sort the edges on the basis of their weights * in an increasing order */ Arrays.sort(edges); /* we use parents & size array for creating disjoint sets */ int[] parents = new int[numVertices + 1]; int[] size = new int[numVertices + 1]; for (int vertex = 1; vertex < graph.length; vertex++) { /* * initially all the vertices are a set in * themselves, hence, they are the parent of their * own set, and the size of their set is also one */ parents[vertex] = vertex; size[vertex] = 1; } int edgeCounter = 0; int edgedTaken = 1; /* for connecting all the vertices we need to have * atleast vertices-1 edges */ while (edgedTaken <= numVertices - 1) { edge e = edges[edgeCounter]; edgeCounter++; /* * we will include only those edges which does * not create any cycle in the constructed minimum * spanning tree */ if (isCyclic(e.u, e.v, parents)) continue; /* * for combining the edge into the MST, we first * need to find the parents of both the vertices, * and then the put combine the smaller set with * larger set */ union(findParent(e.u, parents), findParent(e.v, parents), parents, size); mst[e.u][e.v] = e.weight; edgedTaken++; } /* tree display */ for (int u = 1; u < mst.length; u++) { for (int v = 0; v < mst.length; v++) { if (mst[u][v] != 0) { System.out.println(u + " " + v + " " + mst[u][v]); } } } } public static boolean isCyclic(int u, int v, int[] parents) { /* * if the parents of both the vertices of the * edge are same, this means they are connected * to a common vertex, and hence if we put this * edge in the MST then it will create a cycle. */ return findParent(u, parents) == findParent(v, parents); } public static void union(int u, int v, int[] parents, int[] size) { /*find the parent of both the vertices in the current * edge, and merge the larger disjoint set with smaller * disjoint set*/ u = findParent(u, parents); v = findParent(v, parents); if (size[u] > size[v]) { parents[v] = u; size[u] += size[v]; } else { parents[u] = v; size[v] += size[u]; } } public static int findParent(int u, int[] parents) { /*if the parent of any vertex is the vertex itself, * then this is the parent of the the vertex of the * current edge being processed*/ if (parents[u] == u) { return u; } else { /*path compression*/ parents[u] = findParent(parents[u], parents); return parents[u]; } } } |
That’s all about Kruskal’s algorithm for finding minimum spanning tree.
