Kruskal’s Algorithm

Pathfinding algorithms are heavily used in the transmission of data over the internet/ network. The data which you are reading right now comes from a far-off server located somewhere on the Earth and for that, the data has created a path from the server to your device ( IP address ).

This so-called path is a sequence of servers through which the data must go through to finally end up on your device.

We (the algorithm) try to keep the path length as short as possible to reduce transmission delay.

The algorithms used vary widely.

Let’s learn about one such algorithm called Kruskal’s Algorithm.

The Kruskal algorithm is an algorithm used to find the shortest path through a graph. The solution we get is in the form of a minimum spanning tree, so first of all let’s learn what a Minimum Spanning Tree is :

Spanning Tree

A spanning tree is a subset of Graph G that has all of its vertices covered with the shortest viable range of edges. Spanning Trees can be thought of as an acyclic graph with all vertices covered.

Minimum Spanning Tree

A minimum spanning tree (MST) or minimum weight spanning tree (MWST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all of the vertices together with no cycles and the minimum viable overall edge weight.

Kruskal’s Algorithm

This algorithm belongs to the Greedy Algorithm class, which seeks the local optimum cost in the hopes of finding the global optimum cost.

Steps:

1: Sort all of the edges with their respective costs in ascending order, from lowest to highest.

2: As shown in the original diagram, mark all of the vertices in the spanning tree.

3: Find the lowest-cost edge and add it to the spanning tree. For instance, if an edge connecting vertices 2 and 3 has the lowest cost, i.e. 1, we add it to the spanning tree.

4: Continue this process, making sure that if connecting a specific edge results in the creation of a cycle, reject that edge and move on to the next one.

5:We continue to add edges to the spanning trees until all of the vertices are connected.

Time Complexity:

The most time-consuming operation in Kruskal’s algorithm is sorting because the total complexity of the Disjoint-Set operations is: O(E log V)[V being the number of vertices and E = edges.], which is the algorithm’s overall Time Complexity.

Applications of Kruskal’s Algorithm

1. If you want to connect several cities using highways or rail networks, you can use these algorithms to find the minimum length of roads/rail tracks connecting all these cities.

2. Network Design — Suppose you have a business with several offices. You have to lease phone cables to connect all these offices. So you can make use of these algorithms to find out what is the minimum cost to connect all your offices with minimum use of phone cables.

3. Can be used to find the traveling salesman problem. This is a very famous problem using MST.

4. You want to apply a set of houses with — Electric Power, Telephone Lines, Sewage Lines.

5. Designing Local Area Networks.