Apr 10
Kruskal’s Algorithm
In simple language, this algorithm is know as minimum spanning tree algorithm, which takes graph as input and retrieve subset of edges of that graph.
It works as detectors which finds a minimum spanning forest of an undirected edge-weightage graph.
Basic Terms :-
Spanning Tree :- It is the subgraph of a connected graph.
Minimum Spanning Tree :- The spanning tree in which he sum of all weightage of all edge is minimum .
Working :-
We begins with edges with lowest weight and keep on adding the edges until and unless the goal is achieved.
Sort all the edges from low to high weigh (ascending order)
Pick the lowest edge and add it into spanning tree
Keep on adding edges from low to high until all vertices are covered
Application :-
Used in LAN (Local Area Network )
Can be used to set electric wires for larger areas
Time Complexity :-
O(E logE) or O(V logV)
where,
V = number of vertices
E = number of edges
Source Code
Example :-
Let’s take an example to understand this algorithm :-
As you can see edges and there weight :-
EDGE = WEIGHT
AB = 1
BC = 3
CD = 4
DE = 2
AE = 5
AC = 7
AD = 10
Let’s check the minimum weight to form spanning tree
Because AB has the least weight, add edge AB first with weight 1.
2. Add edge DE, because it has weight 2 but remember it is not creating cycle.
3. Now, Add edge BC which is 3rd least weight, and it is also not creating any cycle.
4. Now pick 4th least weight edge CD and add it into spanning tree, It is also not forming any cycle.
5. But this time when we shall be picking 5th least edge AE with weight 5, it is forming cycle so this time we will discard it.
6. Same goes with edge AC with weight 7too it is forming cycle.
7. And same with edge AD with weight 10 too , It is also creating cycle.
So, Final spanning tree will be
I hope you like this blog.
