Boruvka's
algorithm for Minimum Spanning Tree
Summary:
Ø Definition of MST
Ø History
Ø Different with other algorithms
Ø Explanation of algorithm
Ø Proof
Ø Advantages
Ø Implementation
Ø Conclusion
Introduction:
A spanning tree with the least
weight to be connected with graph is called minimum spanning tree. The spanning
tree is a weighted graph. The Spanning tree which minimizes the quantity of
weighted graph.the boruvka algorithm is the third algorithm was discovered by
Oktar Boruvka in 1926.There was the oldest algorithm was discovered before
computer was existed.The algorithm was worked as the method of constructing and
wellorgnized electricity network. The Boruvka algorithm was finding minimum
tree in graph. The algorithm was working different applications .the time
complexity of this algorithm O(log v) of the iteration of outer loop and the runtime
complexity is O(elogv).e is showed by number of edges and v is showed by number
of verticals.
History:
Otakar Boruvka was the first person to
given the solution of minimum spanning tree in 1926.it was the first algorithm
to find minimum spanning tree is discovered by Boruvka. The algorithm was basic
two rule.1st is cut rule and 2nd is cycle rule.
·
Cut rule:
The cut rule help us to cut the graph
for different way and find the minimum cut of the graph and help us how to add
our MST.
·
Cycle rule:
The cycle rule states that we have a cycle
that the heaviest edge on that cycle cannot be in the MST. This helps us
determine what we can remove in construct the MST.
Lemmas for MST:
There are
different methods for minimum spanning tree and all minimum spanning trees are
the base of two simple lemmas.
Lemma
1. The minimum spanning tree contains very safe edge:
·
: Let vEV
be any vertex in G, the MST of G must contain edge (v, w) that is the Minimum
weight edge occurrence on v.
·
We prove this state using a
greedy exchange argument
Lemma
2. The minimum spanning tree contains no worthless edge.
·
Adding any worthless edge to F
would introduce a cycle.
·
Our basic minimum spanning tree
algorithm frequently adds one or more safe edges to the
Developing forest F.
·
Whenever we add new edges to F,
some unclear edges become safe, and others become Useless.
Different with other algorithm:
1.
Boruka's algorithm takes O(ElogV) time.
2.
Prim algorithm takes O(elogv) or O(E+VlogV)or
O(V+ElogV) depend on data structure.
3.
Kruskal algorithm takes O(ElogV) time.
Faster Algorithm:
1.
Linear time randomize algorithm by karger, klein
and tarjan
2.
The fastest non randomized comparison based on
complexity by Bernard chazelln, is based of the soft heap. The time is required
by O(ealfa (e,v)) time.
Pseudocode for MST:
Function MST (G, W):
T= {}
While
T does not form a spanning tree:
Find the minimum weighted edge in E that is safe for T
T= T union {(u, v)
Return T
Implementation:
Boruvka (Sollin's Pseudo code for MST
F <Ø
While F is disconnected do
For all components Ci
Do
F>F U {ei} for ei= the minweight
edge leaving Ci
End for
End while
The way of Finding
boruvka:
·
Start with minimum weight of any tree.
·
Find the next minimum weight of the tree
·
Consider only edges that leave the connected
component. Add smallest considered edge to your connected component. Continue
until a spanning tree is created.
Proof of
Correctness:
The
proof of correctness is using by the theorem of lemma's
•Lemma1: Let vEV be any vertex in G, the MST of G must contain edge (v, w) that is
the Minimum weight edge occurrence on v.
•Lemma2: The set of edges marked for reduction during a Boruvka stage induces
a forest in G
Uses and Advantages:

• Can be used
to find the solutions for MST of any electric power, Water, telephone lines,
transporting route etc to minimize the cost.
• In Network
sensor especially in Plane a set of sensor nodes and transmission data is
measured by MST in terms of Euclidian Distance and it is sink with all nodes of
sensor transmission and transmission power of all nodes are the minimum value.
Limitation:
• MST cannot
be used to solve the Travel salesman problem (TSP) because he needs to return
home to take rest, more over TSP is a cycle which is not follow the lemma of
MST.
Conclusion:
• Kruskal is
better than Boruvka and Prim in low numbered edges where Prim and Boruvka takes
fewer time than Kruskal in a big set of edges.
• Among all
three Algorithm Prim is taken less time in Binary search tree or adjacency list
or Fibonacci