Kruskal Algorithm | Minimum Spanning Tree | DAA
Minimum Spanning Tree
Given an undirected graph G = (V,E), a subgraph T =(V,E’) of
G is a spanning tree if and only if T is a tree. The MST is a spanning tree of
a connected weighted graph such that the total sum of the weights of all edges
eÎE’ is minimum amongst all the sum of edges that would give a spanning tree.
Kruskal’s Algorithm:
The problem of finding MST can be solved by using Kruskal’s
algorithm. The idea behind this algorithm is that you put the set of edges form
the given graph G = (V,E) in nondecreasing order of their weights. The
selection of each edge in sequence then guarantees that the total cost that
would from will be the minimum. Note that we have G as a graph, V as a set of n
vertices and E as set of edges of graph G.
Algorithm:
KruskalMST(G)
{
T = {V} // forest of n nodes
S = set of edges sorted in nondecreasing order of weight
while(|T| < n-1 and E !=Æ)
{
Select (u,v) from S in order DAA
Remove (u,v) from E
if((u,v) doesnot create a cycle in T))
T = T È {(u,v)}
}
}
Analysis:
In the above algorithm the n tree forest at the beginning
takes (V) time, the creation of set S takes O(ElogE) time and while loop
execute O(n) times and the steps inside the loop take almost linear time (see
disjoint set operations; find and union). So the total time taken is O(ElogE)
or asymptotically equivalently O(ElogV)!.
Comments
Post a Comment
Subscribe Us and Thanks for visiting blog.