Minimum Cost Spanning Tree

Introduction of Minimum Cost Spanning Tree

• The minimum (Cost) Spanning Tree is also known as MST. 

Definition of MST

• A Spanning Tree (ST) is (actually derived from a graph) a tree (a connected graph without a cycle) that contains all the vertices of the graph.
• In other words, ST is an undirected, connected, and acyclic graph.
• A Spanning tree with the sum of minimum (edge) weights or costs is called MST (Minimum Cost Spanning Tree). 

Properties of MST

• A spanning tree of vertices V has V-1 edges.
•  undirected graph
• A spanning tree is associated with a weighted, connected, Non-directed or Undirected, or Bi-directional graph.
• The weights on the links or edges are called costs.
• There may be single or multiple spanning trees.
• There exists a unique path between any two vertices of a spanning tree.
• Adding any edge to a spanning tree creates a unique cycle.
• Breaking any edge on this cycle restores a spanning tree.

Use/Application/Implementation of MST

• To design of various kinds of Networks (Circuits design, Telecommunication or Telephone lines, Transportation, Water Supply, Sewage lines, Power Grids, etc.)
• In Geometric/Vision/Image Processing (Registration & Segmentation) Problems and Analysis work.
• To find out approximation values of Complex Problems.
• To choose the minimum weight of a spanning tree for broadcasting the messages to its shortest nearby location.
• In Handwriting recognition of mathematical expressions.
• Used in algorithms approximating the traveling salesman problem, multi-terminal minimum cut problem, and minimum cost weighted perfect matching.
• In Cluster Analysis.

Algorithm for MST

• There are two famous algorithms for finding out the Minimum Cost Spanning Tree: –
  • Prim’s Algorithms
  • Kruskal’s Algorithms

Prim’s Algorithms

• Prim’s Algorithm is one of the famous algorithms to find out the minimum cost spanning tree from a given graph.
• Prim’s Algorithm uses a Greedy approach to find the minimum spanning tree.
• In Prim’s Algorithm, we grow the spanning tree from a starting position.
• Prim focuses on the vertex of the growing spanning tree.
• Steps of Prim’s Algorithm:
  • Choose any vertex first (and start MST formation from the given graph).
  • Select the cheapest Neighbour vertex that is connected to it into the growing spanning tree. This can be done using Priority Queues. 
  • Now, add a selected vertex to the MST one by one from the remaining vertex having the next smallest weight until the final MST is formed.
  • Only those next vertices are added in the MST which doesn’t form a cycle during the formation of MST.
  • All the Vertices/Nodes must be traversed from the graph and present in the MST. 

Practically, in Prim’s Algorithm, we start with any arbitrary node/vertex given in the graph and mark it. In each iteration, we will mark & traverse a new smallest weight vertex that is adjacent to the one that we have already marked/traversed. Now, as a greedy algorithm, Prim’s algorithm will select the cheapest edge and mark the vertex. In the next iteration, we will select the edge with the second smallest weight and mark the vertex and so on, one by one considering no creation of a cycle. In the end, we finish a minimum spanning tree with total cost by adding all the traversed vertex with their paths. (Such as AB+ AD+DC+BC=3+6+7+10=26). 

• The time complexity of Prim’s Algorithm is O(V+E) log V because each edge is inserted in the priority queue only once and insertion in the priority queue takes logarithmic time.

Kruskal’s Algorithms

• Kruskal’s Algorithm is another one of the famous algorithms to find out the minimum cost spanning tree from a given graph.
• Kruskal’s Algorithm builds the spanning tree by adding the smallest edge value/cost one by one into a growing spanning tree.
• Kruskal’s algorithm follows and works on the principle of the greedy algorithms approach in each iteration by finding an edge that has the least weight/costs and adding it to the growing spanning tree.
• Steps of Kruskal’s Algorithms:
  • Choose the lowest edge value/costs first (and start MST formation from the given graph).
  • Now, add edges to the MST one by one from the remaining edges having the next smallest weight until the final MST is formed.
  • Only those next edges are added in the MST which doesn’t form a cycle during the formation of MST.
  • All the Vertices/Nodes must be traversed from the graph and present in the MST. 

Practically, in Kruskal’s algorithm, at each iteration we will select the edge with the lowest weight i.e., we will start with the lowest weighted edge first and after that, we will select the second lowest weighted edge, and so on till all the vertices traversed without any cycle formation in the MST. In the end, we finish a minimum spanning tree with total cost by adding all the traversed edges with their paths. (Such as AB+ AD+DC+BC=3+6+7+10=26).

• The time complexity, in Kruskal’s algorithm, is mostly consumed during the operation of sorting of Disjoint-Set is O(E log V), which is the overall Time Complexity of the algorithm.