## Table of contents

Minimum Spanning Tree's concept is compulsory for learning Kruskal and Prim's Algorithm.

Let's get started!

*Minimum Spanning Tree*

A minimum Spanning Tree (MST) is a subset of edges of connected, weighted and undirected graph which:

Connects all vertices together

No cycle

Minimum total edge

Real Life Problem

Connect five island with bridges

The cost of bridges between island varies based on different factors

Which bridge should be constructed so that all island are accessible and the cost is minimum

We don't want any circle between them and the cost should be minimum. By using minimum spanning tree, our solution will look like this :

We have constructed bridge between these islands. The cost is minimum (40) and there is no cycle between them. You can go in the same way and come back to in the same way. Don't mix it with Single short shortest path.

Here, in MST, there is no source node. In SSSP, we take one island as a source then find the single root to other islands.

MST find the cheapest way that connects all vertices. But in SSSP, we are taking a source vertex and then finding the shortest, cheapest path to other vertices.

So you need to be careful about them, specially in interview.

*Disjoint Set*

It is a data structure that tracks elements partitioned into disjoint, non-overlapping sets. Each set has a representative to identify it.

Make set

makeSet(N): used to create initial set.

Union

union(x,y): merge two given sets.

Find Set

findSet(x): returns the set name in which this element is there.

*Disjoint set in python*

```
class DisjointSet:
def __init__(self, vertices, parent):
self.vertices = vertices
self.parent = parent
for v in vertices:
self.parent[v] = v
self.rank = dict.fromkeys(vertices, 0)
def find(self, item):
if self.parent[item] == item:
return ite,
else:
return self.find(self.parent[item])
def union(self, x, y):
xroot = self.find(x)
yroot = self.find(y)
if self.rank[xroot] < self.rank[yroot] :
self.parent[xroot] = yroot
elif self.rank[xroot] > self.rank[yroot] :
self.parent[yroot] = xroot
else:
self.parent[yroot] = xroot
self.rank[xroot] += 1
ds = DisjointSet(vertices)
ds.union("A", "B")
ds.union("A", "C")
print(ds.find("A")
```

Time complexity: O(1), Space Complexity: O(N) (we are inserting n number of elements)