There are many algorithm for determining the minimal spanning tree of the given weighted graph. Here we discuss Kruskal’s algorithm in data structure. To understand these algorithm first we to know minimal spanning tree. Thus a minimal spanning tree of G is a spanning tree of G with minimum possible weight among all possible spanning trees of that graph.
Kruskal’s algorithm in data structure
The algorithm involves following step:
- Step1: List all the edges of with non decreasing order of their weights.
- Step2: select an edge of minimum weight (if there are more then one edge of minimum weight, arbitrarily choose one of them). this will be the first edge of T.
- Step3: At each stage, select an edge of minimum weight from all the remaining edge of G if it does not from a cycle with the previously selected edge in T. Then add the edge to T.
- Step4: Repeat step 3 until n-1 have been selected.
Pseudo-code for kurskal’s algorithm
KruskalMst(G)
{
T={V} //set of vertices
E= set of edge sorted in non-decreasing order of thier weight
while(|T| < n-1 and E!=null)
{
select(u,v) from the E in order
remove (u,v) doesnot creat cycle in T
T= TU{(u,v)
}
}Example of kurskal’s algorithm in data structure
By using kurskal’s algorithm to find a minimal spanning tree for G in figure below:
solution:
step1:List the edges with non-decreasing order of their weights.
| Edge | (b, c) | (c, e) | (c, d) | (a, b) | (d, e) | (a, d) | (b, e) |
| weight | 1 | 1 | 2 | 3 | 3 | 4 | 4 |
Step2: The edge (b, c) has the smallest weight, so include it in T.
Step3: An edge with next smallest weight is (c, e), so it include in T
Step4: similarly next smallest weight including edge is (c, d). since it doesn’t from a cycle with the existing edges in T. similarly we follow this process until T has 5-1=4 edges which are shown in figure below and weight is 1+1+2+3=7
Related post
How you define Searching Algorithms in data structure?Ans: is the process of determining the ability of desired element in the given list of elements stored in any order or randomly. Searching operation returns the position of the required element….Read more
What is Sorting algorithm in discrete structure?
Ans: Is the process of arranging the element of a list of file in any specific order which may be ascending or descending. For example all list of words could be sorted alphabetically or by length…Read more