Kruskal Algorithm

The notion of Kruskal’s algorithm is raised in discrete mathematics’ graph theory. It is preferred to find the quick and the shortest path between two locations in a connected graph. This algorithm helps in converting a graph into a forest, or we can say that it helps in searching a minimum spanning forest of a graph (undirected edge-weighted). In case the given graph is connected, it first searches for a minimum spanning tree.

We’ll talk about Kruskal’s algorithm in this article in terms of its complexity, working, example, and execution.

However, before diving into the algorithm, we must first grasp the fundamental concepts of the spanning tree and minimum spanning tree.

Also, explore the Difference between Prim’s Algorithm and Kruskal’s Algorithm to get a better understanding of this topic.

Table of Contents

• Spanning Tree
• General Properties of Spanning Tree
• Minimum Spanning Tree
• General Properties of Minimum Spanning Tree
• Example of Kruskal’s Algorithm
• Working of Kruskal’s Algorithm
• Algorithm
• The Applications of Kruskal’s Algorithm
• The Complexity of Kruskal’s Algorithm
• Practice Problems
• FAQs Related to Kruskal Algorithm

Spanning Tree

It is recognised as a subset of graphs that contains all the vertices shielded with the lowest number of edges. So, with the help of the above-mentioned statement, we can conclude that a spanning tree does not hold any cycles, and it can’t also be disconnected.

You need to dive deep into the graph world to understand spanning trees in a perfect manner. You can explore more about graphs and their applications to gain a better understanding of this topic.

General Properties of Spanning Tree

• There can be more than one spanning tree in a connected graph G.
• In a spanning tree, there are no loops or cycles.
• Because a spanning tree is loosely connected, extracting one edge from the tree will cause the graph to be disconnected.
• Adding one edge to a spanning tree will result in a loop because it is the most acyclic.
• Only nn-2 spanning trees may be constructed from a complete graph.
• In a spanning tree, the total number of edges is n-1, where n is the number of nodes.
• The spanning tree can be created if the graph is complete by removing the maximum (e-n+1) edges, where ‘e’ signifies the number of edges and ‘n’ specifies the number of vertices.

Minimum Spanning Tree

A minimum spanning tree is one in which the total weight of the edges is kept as minimal as possible.

General Properties of Minimum Spanning Tree

• Each spanning tree has n1 edges if there are n vertices in the graph.
• There will be only one unique minimum spanning tree if each edge has a different weight.
• A minimum spanning tree is the least subgraph linking all vertices if the weights are positive.
• For each cycle C in the graph, if the weight of an edge e of C is bigger than the individual weights of all other edges of C, then this edge cannot belong to an MST.
• If the weight of an edge e in the cut-set of C is rigorously less than the weights of all other edges in the cut-set of C for any cut C of the graph, then this edge corresponds to all MSTs of the graph.
• If the least-cost edge e of a graph is distinctive, then this edge is included in any MST.
• If T is a tree of MST edges, we can collapse T into a single vertex while keeping the invariant that the MST of the contracted graph + T equals the MST of the graph prior to contraction.

Working of Kruskal’s Algorithm

For a connected weighted graph, Kruskal’s Algorithm is preferred to find the shortest spanning tree. The major goal of this particular algorithm is to encounter a subset of edges that may be utilised to visit every vertex of the graph. It pursues the greedy technique that discovers an optimum explanation at every step rather than concentrating on a global optimum.

Here, we pick the edges having the lower weight and will keep on counting the edges until we complete our goal. There are some steps we need to execute the Kruskal’s algorithm, and they are as follows:

• Firstly, we will focus on sorting all the edges and will sort them according to their weight (low weight to high).
• Now, we will pick the edge having the least amount of weight and associate it with the spanning tree. If the edge being added forms a cycle, it should be rejected.
• Keep on adding the edges till all the vertices have been added and a minimum spanning tree has been formed.

Example of Kruskal’s Algorithm

Let’s look at how Kruskal’s approach functions using an example. Using an example, it will be easier to comprehend Kruskal’s algorithm.

Let’s assume a weighted graph is –

In the below table, we have accumulated the weight of the edges of the graph –

Table after organising the edges in the ascending order according to their weights –

Now, we will start creating the minimum spanning tree.

Phase 1 – Join the edge PQ having the weight 1 to the MST.

Phase 2 – Join the edge ST having the weight 2 to the MST. Also, point to be noted that this is not making any cycle.

Phase 3 – Add the edge QR having the weight 3 to the MST.

Phase 4 – Select the edge RS having the weight 4 to the MST; also, you will notice that it is not composing the cycle.

Phase 5 – Now, we will select the edge PT having the weight 5. Adding this edge will form the cycle, so we will dump it.

Phase 6 – Pick the edge PR having the weight 7. Adding this edge will form the cycle, so we will dump it.

Phase 7 – Pick the edge PS having the weight 10. Adding this edge will form the cycle, so we will dump it.

So, using Kruskal’s approach, the final least spanning tree produced from the provided weighted graph is –

Total value of MST is = PQ + ST + QR + RS = 1 + 2 + 3 + 4 = 10.

In the above tree, the number of edges now equals the number of vertices minus one. As a result, the algorithm has reached its conclusion.

Algorithm

1. Phase 1: Construct a forest F with each vertex of the graph representing a distinct tree.
2. Phase 2: Make a subset E that holds all of the graph’s edges.
3. Phase 3: Steps 4 and 5 should be repeated until E is not vacant and F is not spanning.
4. Phase 4: Extract an edge from E with the least weight.
5. Phase 5: Add the edge generated in phase 4 to forest F if it joins two different trees.
6. For mixing two trees into a solitary tree
7. ELSE
8. Dump the specific edge
9. Phase 6: Finish.

The Applications of Kruskal’s Algorithm

• The technique by Kruskal can be used to build out electrical wiring across cities.
• It’s possible to operate it to set up LAN connections.

The Complexity of Kruskal’s Algorithm

• Time Complexity
  O(E logE) or O(V logV) is the time complexity of the Kruskal algorithm. Here E indicates the no. of edges, and V indicates the no. of vertices.

Practice Problems

Q1. Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and m edges has the time complexity of ________.

Q2. The complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted _______.

Q3. Construct the minimum spanning tree (MST) for the given graph using Kruskal’s Algorithm.

Q4. Consider the following graph:

Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm? (GATE-CS-2009)

(A) (b,e), (e,f), (a,c), (b,c), (f,g), (c,d)

(B) (b,e), (e,f), (a,c), (f,g), (b,c), (c,d)

(C) (b,e), (a,c), (e,f), (b,c), (f,g), (c,d)

(D) (b,e), (e,f), (b,c), (a,c), (f,g), (c,d)

Q5. How many minimum spanning trees are possible using Kruskal’s algorithm for a given graph?

OR

The number of distinct minimum spanning trees for the weighted graph below is ____. (GATE-CS-2014)

(A) 4

(B) 5

(C) 6

(D) 7

Q6. Consider a complete undirected graph with a vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}. What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T? (GATE CS 2010)

(A) 7

(B) 8

(C) 9

(D) 10

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.

Also Explore,

• Algorithm
• Sorting Algorithms
• Search Algorithms
• RSA Algorithm
• Routing Algorithms in Computer Networks
• Prim’s Algorithm
• Linear Search Algorithm
• Floyd Warshall Algorithm
• Distance Vector Routing Algorithm
• Dijkstra Algorithm
• Algorithm Analysis
• Bubble Sort Algorithm