Skip to content

Instantly share code, notes, and snippets.

@rambabu-patidar

rambabu-patidar/minimum-spanning-tree.md

Created September 15, 2023 18:28
Show Gist options
  • Save rambabu-patidar/958af46e2f9231f37472e0df2fcf5596 to your computer and use it in GitHub Desktop.
Save rambabu-patidar/958af46e2f9231f37472e0df2fcf5596 to your computer and use it in GitHub Desktop.
Download ZIP
minimum-spanning-tree
Raw
minimum-spanning-tree.md

MINIMUM SPANNING TREE NOTES

ST(Spanning Tree) is a tree like subgraph of a connected, undirected graph that include all the vertices of the graph. In simple words, It is a tree like structure (hence no cycle) where the edges are the subset of graph and vertices are the exact set of original graph.

MST is excatly same like ST but with one more constraint of having minimum weight sum of edges.

Properties

  • Number of vertices in MST and graph will be same (as we said exact set of original graph)
  • number of edges in MST will be 1 less than, first, number of vertices in MST and second, number of vertices in graph.
  • It should not be disconnected.
  • No cycle
  • can be more than MST for single graph

For Example for this given graph:

image

One of the spanning tree out of many is:

image

and the MST is:

image

you can try all possible spanning tree and can find that no spanning tree will have sum less than 16.

TIP: How to find the MST of a graph from given graph on paper withoud code.

  • Write all the nodes as it is from the graph without any edge included.
  • Now choose the minimum edge weight from original graph and connet the nodes which you drawn in first step
  • do it util all the points are not gets connected.

Algorithms for finding MST

  • Kruskal's Algorithm
  • Prim's Algorithm
  • Boruvka's Algorithm

Code is available in c++ repo.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment