Kruskal's Algorithm: Examples of Kruskal Algorithm

By Priyanshu Vaish|Updated : August 3rd, 2022

Kruskal Algorithm generates the minimum spanning tree, initiating from the smallest weighted edge. Kruskal algorithm is developed for discovering the minimum spanning tree of a graph. The Kruskal algorithms are popular and follow different steps to solve the same kind of problem. This algorithm does not consider the larger problem as a whole, but the optimal solution for each smaller instance will provide an immediate output.

Before moving into the details of the Kruskal algorithm, let's define a minimum spanning tree of a graph. A spanning tree is a subgraph of a connected, undirected graph that is structured like a tree and contains all of its vertices. As a result, a minimum spanning tree corresponds to a spanning tree with the lowest weight, where the weight of a spanning tree is the total of the weights of its edges present in it. Let us now see Kruskal Algorithm along with its working, pseudocode, time complexity of Kruskal Algorithm and a lot more in detail.

Table of Content

What is Kruskal Algorithm?

Kruskal Algorithm is used to discover the smallest spanning tree of a connected graph and the spanning forest of an undirected edge-weighted graph. Basically, it accepts a graph as input and discovers the subgroup of the edges of that graph. The Kruskal algorithm follows the Greedy approach to compute the minimum spanning tree.

Kruskal's Algorithm computes the minimum spanning tree by considering the edges in increasing order of weight. The intermediate result of the Kruskal algorithm may be a connected or disconnected graph. The Kruskal algorithm can be implemented using Union find data structure. Using the Kruskal algorithm, we can find MST in network architecture gives you the smallest length of wire required to link all the nodes (servers).

Suppose G(V, E) is a connected, weighted graph in which V is the number of vertex and E is the number of edges in the graph G. Kruskal algorithm is used to find a minimum-cost spanning tree (MCST) of a given graph G. It uses a greedy approach to find MCST because at each step it adds an edge of least possible weight to the set A.

Working of Kruskal Algorithm

Kruskal algorithm starts with the minimum single node in the graph and then explores the other minimum node at every step. Kruskal algorithm finds the subset of edges that includes the vertex of the graph such that the sum of the edges' weights can be minimized. The working of the Kruskal algorithm is as follows:

  • First, examine the edges of G in the order of increasing weight.
  • Then select an edge (u, v) є E of minimum weight and check whether its endpoints belong to the same or different connected components.
  • If u and v belong to different connected components, we add them to set A. Otherwise, it is rejected because it can create a cycle.
  • The algorithm terminates when only one connected component remains (that is, all the vertices of G have been reached).

Kruskal Algorithm Pseudocode

The Kruskal algorithm takes an undirected connected weighted graph G(V, E), where V represents the number of vertices and E represents the number of edges in the graph. The output of the Kruskal algorithm is a minimum cost spanning tree T(V, E') of the given graph G. Here, the V is the same as the given graph, but the E' is changed as we do not include all the edges of the graph G. The pseudocode of Kruskal algorithm is as given below:

KRUSKAL MCST (G, W)

{

Sort the edges of E in order of increasing weight

A←Ø

for (each vertex v є V[G])

do MAKE_SET(v)

for (each edge (u, v) є E, taken in increasing order of weight)

{

if (FIND SET (u) ≠ FIND_SET (V))

A←A ∪ {(u, v)}

MERGE(u, v)
}

return A

}

Analysis of Kruskal Algorithm

Suppose G(V, E) is a connected, weighted graph in which V is the number of vertex and E is the number of edges in graph G. The analysis of the Kruskal algorithm is as follows:

  1. Sorting of edges requires O(|E| log |E|) time.
  2. Since, in any graph, the minimum number of edges is (V-1), and the maximum number of edges (when the graph is complete) is V(V- 1)/2. Hence V- 1 ≤ E ≤ V (V-1)/2. Thus O(E log E)= O(E log (V(V-1)/2)) = O(E log V)
  3. Initializing the n-disjoint set (in lines 3-4) using MAKE_SET will require O(V) time.
  4. There are at most 2 |E| FIND SET operations (since there are E edges and each edge has 2 vertices) and (V-1) MERGE operations. Thus we require O((2E+ (V-1)log n) time.
  5. At worst, O(V) time for the remaining operations.
  6. We know that E ≥ (V-1) for a connected graph.

So the total time for Kruskal algorithm is O((2E+ (V-1) logV) = O(|E| log |V]) 

Time complexity of Kruskal Algorithm

The time complexity of the Kruskal algorithm is O(ElogE) or O(ElogV). Sorting of edges takes O(ELogE) time. After sorting, we iterate through all edges and apply the find-union algorithm. The find and union operations can take at most O(LogV) time.

So overall complexity of the Kruskal algorithm is O(ELogE + ELogV) time. The value of E can be at most O(V2), so O(LogV) is O(LogE) the same. Therefore, the overall time complexity is O(ElogE) or O(ElogV)

Kruskal Algorithm Example

Consider the following graph:

Kruskal Algorithm

What is the minimum cost spanning tree of the above graph using the Kruskal algorithm?

Solution:

The weight of the following graph's edges is shown in the table below:

Edges

AB

AC

AD

AE

BC

BD

CD

Weight

60

10

40

70

30

20

50

Sort the edges mentioned above in increasing order of weight.

Edges

AC

BD

BC

AD

CD

AB

AE

Weight

10

20

30

40

50

60

70

We will make the spanning tree step by step,

  1. Choose the minimum edge that is AC
  2. Choose the following minimum that is BD
  3. Repeat the next minimum, which is BC
  4. Next minimum, AD, but this will create a cycle, so discard it.
  5. Similarly, discard the next edges CD, AB because they form a cycle.
  6. At last, include the edge AE.

So, the final spanning tree is:

Kruskal Algorithm

Important Topics for Gate Exam
AdmixturesTruss
Bolted ConnectionDynamic Programming
Difference Between Struts and ColumnsDesign of Beams
PolymersHuffman Coding
Mechanical Properties of Engineering MaterialsMoulding Sand
Crystal DefectsPrinciple of superposition of forces
Free body diagramInternal forces
Influence line diagramDeflection of Beams
Internal and external forcesLami's theorem
Losses of PrestressMoment Distribution Method

Comments

write a comment

FAQs on Kruskal Algorithm

  • The concept of Kruskal's algorithm is introduced in discrete mathematics' graph theory. In a linked weighted graph, it's utilized to find the shortest path between two locations. This program turns a network into a forest, treating each node as a distinct tree.

  • Kruskal Algorithm is used to find the MST(minimum spanning tree) for any connected weighted graph. The main aim of the Kruskal algorithm is to find the subset of the edges through which we can traverse each and every vertex of the given graph.

  • The MCST(minimum cost spanning tree) using the Kruskal algorithm is unique. If all the edge weights in your graph are distinct, then the given graph has a unique MCST(minimum cost spanning tree), and the Prim and Kruskal algorithms are guaranteed to return the same tree.

  • We use the Kruskal algorithm to find the MCST(minimum cost spanning tree) of the undirected weighted connected graph. The Kruskal algorithm creates the MCST (minimum cost spanning tree) by locating the least weighted edge connecting two trees in the forest.

  • The advantage of the Kruskal algorithm is to find the subset of edges that generate the tree and includes each and every vertex where the sum of all weight of the edges is a minimum. Kruskal algorithm is suitable for sparse graphs (low number of edges).

  • The negative edge weight does not have any impact on the Kruskal algorithm. In the Kruskal algorithm, the least weight edge in the graph that connects two distinct components is added to the MCST(minimum cost spanning tree). So, if there is a negative weight edge, it will not affect the working of the Kruskal algorithm.

  • Prim's approach returns connected components and only works on connected graphs. Prim's approach is more efficient in dense graphs. Kruskal's approach is more efficient in sparse graphs. It constructs the shortest spanning tree beginning from the root vertex.

  • It is a greedy algorithm since you combine two sets of vertices each step based on the least amount of weight available, and you pick the edge that seems to be best at the time. Because this is a greedy phase, the algorithm is considered to be greedy.

  • The negative weight edges do not affect their accuracy. The safe edge added to A (subset of an MST) in Kruskal's technique is always the least weight edge in the graph that connects two unique components. As a result, if there are negative weight edges, they will not affect the algorithm's progress.

  • Prim's approach is substantially quicker when you have an extremely dense graph with many more edges than vertices. Kruskal algorithm performs better in sparse graphs because it employs simpler data structures.

Follow us for latest updates