Kruskal's Algorithm is an important greedy algorithm that helps you find the shortest path between 2 cities. So, before learning what Kruskal's algorithm in Java is, let's just go through the basics first.
What is a Spanning Tree?
A spanning tree is a sub-graph or a tree of the given directed and connected graph including all the vertices and minimum possible edges. And as a tree has no loops, a spanning tree also doesn't contain any cycles or loops.
A minimum Spanning tree is a kind of spanning tree in which the sum of the weights of edges is the minimum. A graph can have many spanning trees but can only have a unique minimum spanning tree.
Let's take an example from this graph:
Spanning trees made from this graph:
More spanning trees can be made from the given graph. The Minimum Spanning Tree will be:
To create a minimum spanning tree from a graph, we select all vertices and a minimum number of edges connecting those vertices, so that no cycle is created and we select only those edges whose cost of edges is minimum.
What is Kruskal's Algorithm?
Kruskal's algorithm is a realistic algorithm that provides the shorted path from one place to another in terms of edge weights or cost. This produces output exactly the same as prim's algorithm but the process or algorithm differs.
It greedily picks n-1 edges one by one from the graph that has the minimum cost such that no cycle is created. So Kruskal's Algorithm takes up a connected and undirected graph and returns its minimum spanning tree.
How does Kruskal Algorithm work?
Let's take an example of this graph:
Step 1: So as the first step we take the edge having the smallest weight and add it to our minimum spanning tree.
Step 2: Now we take the edge having the smallest weight among the edges that aren't added to the tree yet. So as the edge we are going to add (e6) doesn't make a cycle, we add it to the minimum spanning tree.
Step 3: Now the smallest weighted edge is of weight 7. But as we add that edge to the minimum spanning tree, it creates a cycle, so we skip.
Step 4: Now smallest weighted edge is e1 having weight = 9. As it doesn't create a loop, we add it to the tree.
Step 5: Next smallest weighted edge is e2. So adding it to the tree.
So as of now, we have added n-1 minimum weighted edges of the graph to the tree and as no cycle is there, it is a minimum spanning tree.
Here is the full algorithm:
- We make a pair class to store the vertices and edges and put all the pairs in an array.
- Then we sort the array so that we can access the least weighted edge.
- Now we loop on the sorted array.
- We check using DSU (disjoint sets and union) whether both edges belong to the same group or component or not.
- If not we merge them, else we continue.
- We keep doing so till we get the minimum Spanning tree with all vertices, minimum edges, and no cycles.
Kruskal Algorithm in Java
Here is the full program to implement Kruskal Algorithm in Java:
Time & Space Complexity
As the first step of Kruskal's algorithm, we are sorting the edges based on their weights. Assuming that graph has E Edges, so time complexity is 3 * (E log E) as there are 3 elements - the 2 vertices and weight.
So, it's near O(E Log E). After that, we iterate over these edges and we try to find out if they belong to the same group/component or not, it's time complexity comes out to be O(E * O(4 Alpha)). So total time complexity comes out to be (E Log E).
And as we are using an extra space of O(E) to store the sorted edges, space complexity comes out to be O(E).
Applications & Uses
Here are some practical coding use cases for Kruskal's algorithm:
- Kruskal is a popular algorithm used to find minimum-spanning trees.
- This algorithm can be used to design a cost-effective network by only connecting the vertices having edges of minimum cost.
- It can also be applied to the transportation of goods between different cities. As it is possible to find out the shortest path between warehouses that reduces the transportation time and cost.
- It is an efficient algorithm that can save money by reducing the pipes to supply water, as we can easily find out the minimum cost to supply water in a city.
- Can be used for electrical wiring too.
So Kruskal's Algorithm in Java is not only important from the interview point of view but also, as it is used in the real world to solve problems where we need to find the shortest path between 2 cities or networks.