ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Mnimum Spanning Tree tutorial 1. Introduction to minimum spanning tree

prodevelopertutorial August 18, 2019

First thing to understand is that this topic will come under Graphs not trees.

 

Before solving questions related to Minimum Spanning Tree [MST], we shall take a look on what are MST?

 

In Minimum Spanning Tree, there is a sub part Spanning Tree.

 

Spanning Tree Introduction:

 

Given a connected undirected graph, a spanning tree of that graph is a sub graph that has all the vertices and also a tree.

 

Means, a spanning tree should be connected [connected to all the vertices], acyclic [should not have any cycle] and should have all the vertices.

 

Below is a simple graph

Introduction to Minimum Spanning Tree:

 

Below are the different number of spanning tree for that graph.

Introduction to Minimum Spanning Tree:

 

Note:

 

If there are “n” vertices, then a spanning tree should have “n-1” edges. In the above image, we have 4 vertices, hence our spanning tree has “4 -1 = 3” edges.

 

Then what is Minimum Spanning Tree?

 

Consider the below weighted graph:

 

Introduction to Minimum Spanning Tree:

 

Now you are a sales person, and let us consider each vertices as cities, and you need to visit all the places with minimum amount possible.

 

Below image is the solution for it.

 

Introduction to Minimum Spanning Tree:

 

So where do we use MST?

 

We use MST in

  1. Network Design
  2. Maps
  3. Face Verification

 

In the next MST problems, we shall look at more complex problems with cycle and how to solve them using Prims and Kruskal’s algorithm.

Further Reading:

AJ’s definitive guide for DS and Algorithms. Click here to study the complete list of algorithm and data structure tutorial. 85+ chapters to study from.

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io