Be the first user to complete this post

  • 0
Add to List
Medium

Introduction to Minimum Spanning Tree (MST)

What is a Spanning Tree?

In an undirected and connected graph G=(V,E), a spanning tree is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges. A graph may have several spanning trees. The cost of the spanning tree is the sum of the weights of all the edges in the tree

What is a Minimum Spanning Tree?

minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. Number of edges in MST: V-1 (V – no of vertices in Graph).

Example:

Algorithms for finding the Minimum Spanning Tree:

Applications:

Minimum spanning trees have direct applications in the design of networks, including computer networks, telecommunications networks, transportation networks, water supply networks, and electrical grids. Also used in

  • Approximating travelling salesman problem
  • Approximating multi-terminal minimum cut problem
  • Approximating minimum-cost weighted perfect Cluster Analysis
  • Handwriting recognition
  • Image segmentation
  • Circuit design

Reference - wiki



Also Read: