Minimum Spanning Tree Algorithm

What is Spanning Tree?

A Spanning tree is a subset of an undirected Graph that has connected all the vertices by minimum number of edges. If all the vertices are connected in a graph, then there will be at least one spanning tree present in the graph. In a graph, there can be more than one spanning trees.

Properties:

· A spanning tree does not create a cycle

· Any vertex can be reached by any other vertex

Example:

In the following example of graph you can see the highlighted edges forms spanning tree

What is Minimum Spanning Tree?

A Minimum Spanning Tree (MST) is a subset of edges of a connected weighted undirected graph that connects all the vertices together with the minimum possible total edge weight. To explain an MST there are two algorithms namely Prim’s algorithm and Kruskal’s algorithm. As we studied, one graph may have more than one spanning tree. If there are ’n’ number of vertices, the spanning tree should have n — 1 number of edges. In this context, if each edge of the graph is associated with a weight and there exists more than one spanning tree, we need to find the minimum spanning tree of the graph.

Moreover, if there exist any duplicate weighted edges, the graph may have multiple minimum spanning trees.

If we take the Consider the below Graph in the spanning tree, the cost of the spanning tree is (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38. With the help of the Prim’s algorithm and Kruskal’s algorithm we can find the minimum spanning tree.

Let us now discuss the types of spanning tree algorithms. There are two algorithms mostly used in Minimum spanning tree.

· Prim’s Algorithm

· Kruskal’s Algorithm

Prims’s Algorithm:

Prim’s algorithm is a greedy approach to find the minimum spanning tree. The random vertex can choose to start the approach to form a Minimum Spanning Tree in this algorithm.

Steps for finding MST using Prim’s algorithm:

1. Create MST set that keeps track of vertices already included in MST.

2. Assign key values to all vertices in the input graph. Initialize all key values as INFINITE (∞). Assign key values like 0 for the first vertex so that it is picked first.

3. While MST set doesn’t include all vertices.

· Pick vertex u which is not is MST set and has minimum key value. Include ‘u’to MST set.

· Update the key value of all adjacent vertices of u. To update, iterate through all adjacent vertices. For every adjacent vertex v, if the weight of edge u.v less than the previous key value of v, update key value as a weight of u.v.

Algorithm:

MST-PRIM (G, w, r)

1. for each u ∈ V [G]

2. do key [u] ← ∞

3. π [u] ← NIL

4. key [r] ← 0

5. Q ← V [G]

6. While Q ? ∅

7. do u ← EXTRACT — MIN (Q)

8. for each v ∈ Adj [u]

9. do if v ∈ Q and w (u, v) < key [v]

10. then π [v] ← u

11. key [v] ← w (u, v)

Example: To find minimum spanning tree using Prim’s algorithm

Kruskal’s Algorithm:

An algorithm to construct a Minimum Spanning Tree for a connected weighted graph. It is a Greedy Algorithm. The Greedy Choice is to put the smallest weight edge that does not because a cycle in the MST constructed so far.

Steps for finding MST using Kruskal’s algorithm:

1. Arrange the edge of G in order of increasing weight.

2. Starting only with the vertices of G and proceeding sequentially add each edge which does not result in a cycle, until (n — 1) edges are used.

3. EXIT.

Algorithm:

MST- KRUSKAL (G, w)1. A ← ∅2. for each vertex v ∈ V [G]3. do MAKE - SET (v)4. sort the edges of E into non decreasing order by weight w5. for each edge (u, v) ∈ E, taken in non decreasing order by weight6. do if FIND-SET (μ) ≠ if FIND-SET (v)7. then A  ←  A ∪ {(u, v)}8. UNION (u, v)9. return A

Example: To find minimum spanning tree using Kruskal’s algorithm

This Information is contributed by :

· Amogh Chothe

· Sachin Kulawade

· Mandar Kulkarni

· Shreyas Lengade

· Mayur Mane