Minimum Spanning Tree.md

Minimum Spanning Tree on undirected graph

• This is combinatorial optimization problem
• This has optimal substructure https://leetcode.com/problems/connecting-cities-with-minimum-cost/

Kruskal's algorithm

• Use greedy approach
• Sorted edges by weight
• Apply Union and Find algorithm

Prim's algorithm

• Invented by Dijkastra and named as Prim's algo as it was already discoved by Prim
• This is based on captured/discovered/undiscovered approach
• Start from some vertex
• treat this vertex as source
• At each step, there is single structure, which expands slowly
• Structure remains connected https://leetcode.com/problems/connecting-cities-with-minimum-cost/