Kruskal Algorithm

Let G(V, E) be a connected, weighted graph. Kruskal’s 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. In this algorithm,

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

The following pseudo-code is used to construct an MCST, using Kruskal’s algorithm:

KRUSKAL MCST (G, w)

/* Input: An undirected connected weighted graph G = (V, E).
/* Output: A minimum cost spanning tree T(V, E’) of G
{
1. Sort the edges of E in order of increasing weight
2. A ← φ
3. for (each vertex v ∈ V[G])
4. do MAKE_SET(v)
5. for each edge (u, v) ∈ E, taken in increasing order of weight
{
6. if (FIND_SET (u) ≠ FIND_SET (v))
7. A ← A ∪ {(u, v)}
8. MERGE(u, v)
}
9. return A
}

Kruskal’s algorithm works as follows:

• First, sort the edges of E in order of increasing weight
• We build a set A of edges that contains the edges of the MCST. Initially A is empty.
• In lines 3-4, the function MAKE_SET(v) creates a new set {v} for all vertices of G. For a graph with n vertices, it creates n components of disjoint sets, such as {1}, {2}, and so on.
• In line 5-8: An edge (u, v) ∈ E, of minimum weight is added to the set A, if and only if it joins two nodes which belongs to different components (to check this use a FIND_SET() function, which returns a same integer value, if u and v belongs to same components (In this case, adding (u, v) to A creates a cycle); otherwise, it returns a different integer value)
• If an edge is added to A, then the two components containing its end points are merged into a single component.
• The algorithm terminates when there is just a single component.

MADE EASY

MADE EASY is a well-organized institute, complete in all aspects, and provides quality guidance for both written and personality tests. MADE EASY has produced top-ranked students in ESE, GATE, and various public sector exams. The publishing team regularly writes exam-related blogs based on conversations with the faculty, helping students prepare effectively for their exams.