Scribd
Upload
355 views4 pages

7.6 - Sollin's Algorithm

Sollin's algorithm, also known as Boruvka's algorithm, is a greedy algorithm used to find the minimum spanning tree (MST) of a connected, weighted, undirected graph. The algorithm works by: 1. Initially treating each vertex as its own component. 2. Repeatedly finding the cheapest edge connecting each component to another component and adding it to the MST until only one component remains, containing all vertices. 3. Returning the resulting MST which connects all vertices with minimum total edge weight.

Uploaded by

ravishku2403
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
355 views4 pages

7.6 - Sollin's Algorithm

Sollin's algorithm, also known as Boruvka's algorithm, is a greedy algorithm used to find the minimum spanning tree (MST) of a connected, weighted, undirected graph. The algorithm works by: 1. Initially treating each vertex as its own component. 2. Repeatedly finding the cheapest edge connecting each component to another component and adding it to the MST until only one component remains, containing all vertices. 3. Returning the resulting MST which connects all vertices with minimum total edge weight.

Uploaded by

ravishku2403
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Sollin’s Algorithm

Sollin’s algorithm is also called Boruvka’s algorithm. It is used to find MST. It was given by
Boruvkas in 1926. At that time it was the first algorithm to find the MST.
Boruvka’s Algorithm is a greedy algorithm and is similar to Kruskal’s algorithm and Prim’s
algorithm.

Steps of Sollin’s Algorithm

1) Input is a connected, weighted and un-directed graph.


2) Initialize all vertices as individual components (or sets).
3) Initialize MST as empty.
4) While there are more than one components, do following
for each component.
a) Find the closest weight edge that connects this
component to any other component.
b) Add this closest edge to MST if not already added.
5) Return MST.

Let us understand the algorithm with below example.

Initially MST is empty. Every vertex is singe component as highlighted in blue color in
below diagram.

For every component, find the cheapest edge that connects it to some other
component.

Component Cheapest Edge that connects


it to some other component
{0} 0-1
{1} 0-1
{2} 2-8
{3} 2-3
{4} 3-4
{5} 5-6
{6} 6-7
{7} 6-7
{8} 2-8
The cheapest edges are highlighted with green color. Now MST becomes {0-1, 2-8, 2-
3, 3-4, 5-6, 6-7}.

After above step, components are {{0,1}, {2,3,4,8}, {5,6,7}}. The components are
encircled with blue color.

We again repeat the step, i.e., for every component, find the cheapest edge that
connects it to some other component.

Component Cheapest Edge that connects


it to some other component
{0,1} 1-2 (or 0-7)
{2,3,4,8} 2-5
{5,6,7} 2-5
The cheapest edges are highlighted with green color. Now MST becomes {0-1, 2-8, 2-
3, 3-4, 5-6, 6-7, 1-2, 2-5}

At this stage, there is only one component {0, 1, 2, 3, 4, 5, 6, 7, 8} which has all edges.
Since there is only one component left, we stop and return MST.

RELEVANT READING MATERIAL AND REFERENCES:

Source Notes:

1. https://www.geeksforgeeks.org/boruvkas-algorithm-greedy-algo-9/

Lecture Video:

1. https://youtu.be/MFsyfvtQskw
Online Notes:

1. http://vssut.ac.in/lecture_notes/lecture1428551222.pdf

Text Book Reading:

1. Cormen, Leiserson, Rivest, Stein, “Introduction to Algorithms”, Prentice Hall of India, 3rd
edition 2012. problem, Graph coloring.

In addition: PPT can be also be given.

You might also like