DAA- Kruskal's Algorithm | i2tutorials

Home / Design and Analysis of Algorithms(DAA)-Tutorial / DAA- Kruskal’s Algorithm

Kruskal’s Algorithm:

Kruskal’s algorithm is one such algorithm where we construct a Minimum Spanning Tree for a given connected weighted graph. However, Kriskal’s is also a Greedy Algorithm. One point to note here is that if the graph is not linked, then it finds a Minimum Spanning Tree.

Steps for finding MST using Kruskal’s Algorithm:

The edge of G has to be arranged in the order of increasing weight.
We must start only with the vertices of G and then proceed sequentially to add each edge so that it does not result in a cycle until we use (n – 1) edges.
EXIT.

MST- KRUSKAL (G, w)

A ← ∅
for every vertex v, v ∈ V [G]
do MAKE – SET (v)
Edges of E have to be sorted into non-decreasing order by weight w
for every edge (u, v) ∈ E, have to be taken in non-decreasing order by weight
do if FIND-SET (μ) is not equal to if FIND-SET (v)
Now, we can see that A ← A ∪ {(u, v)}
UNION (u, v)
return A

Analysis:

In the above algorithm, E is the number of edges in the graph and the number of vertices is represented by v. Kruskal’s Algorithm can be shown to be run in O (E log E) time, or O (E log V) time, all with. These running times are equivalent because of the following reasons:

E can take the value at most V2 and log V2= 2 x log V is O (log V).
If the isolated vertices are ignored, each of their components of the minimum spanning tree would be, V ≤ 2 E, so log V is O (log E).

Thus the total time would result as follows,

O (E logE) = O (E logV).

Example:

Consider the following graph and find the Minimum Spanning Tree using Kruskal’s algorithm.

Solution:

We first initialize set A to an empty set and then create |v| trees. Here, one tree contains vertex with the MAKE-SET procedure. Then, we sort the edges in E into order by non-decreasing weight.

There are a total of 9 vertices and 12 edges. So MST formed would be(9-1) = 8 edges

Now, we check for each edge (u, v) whether the endpoints u and v would belong to the same tree. If they belong to the same tree then the edge (u, v) cannot be supplementary. If they do not, then the two vertices belong to different trees, and therefore the edge (u, v) is added to A, and the vertices in the two trees would be merged by a union procedure.

Step1: So, we are first supposed to take (h, g) edge

Step 2: then we with the (g, f) edge.

Step 3: Now, we consider (a, b) and (i, g) edges, and the forest becomes

Step 4: Now, we go with the edge (h, i). We can find that both h and I vertices are in the same set. Thus it is creating a cycle here. So we discard this edge.

Then we consider the edges (c, d), (b, c), (a, h), (d, e), (e, f) and the forest becomes as follows.

Step 5: In edge(e, f) both the endpoints e and f seem to exist in the same tree. Hence, we discarded this edge. Then we find that (b, h) edge also creates a cycle.

Step 6: After that, we go with the edge (d, f) and the final spanning tree is shown as follows.

Step 7: This step will be the required Minimum Spanning Tree as this is the one that contains all the 9 vertices and (9 – 1) = 8 edges

e → f, b → h, d → f [here cycle will be formed]

Prim’s Algorithm

This algorithm is another example of a greedy algorithm. Prim’s algorithm has to start with an empty spanning tree. The idea of this algorithm is mainly to maintain two sets of vertices. Which are:

The ones that contain vertices that are already included in MST.
The ones that contain vertices that are not yet included.

At each and every step, we consider all the edges and pick the minimum weighted edge out of all the edges. After picking the minimum edge, we move the other endpoint of the edge to a set that contains MST.

Following are the steps for finding MST using Prim’s Algorithm:

First, create an MST set that keeps track of vertices that are already included in MST.
Assign key values to all the vertices present in the input graph. Initialize all the key values as INFINITE (∞). Then, assign the key values like 0 for the first vertex so that it can be picked first.
While MST set doesn’t include all vertices.
1. Pick vertex u which is not in the MST set and has a minimum key value. Include ‘u’ to MST set.
2. We are supposed to update the key value of all adjacent vertices of u. To update, iterate through all adjacent vertices. For every adjacent vertex v, if the weight of edge u.v is less than the previous key value of v, then we update the key value as the weight of u.v.