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

well-orgnized 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 F U {ei} for ei= the min-weight

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

•Lemma-1: 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.

•Lemma-2: 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