### Minimum Spanning Tree Using Kruskal’s algorithm

##### Given a weighted, undirected and connected graph. The task is to find the sum of weights of the edges of the Minimum Spanning Tree

Kruskal’s algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.[1] It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

##### Spanning Tree – A tree that spans all the vertices of a connected and undirected graph .

Spanning Tree Properties

- for graph G(V, E), it contains exact (V-1) edges
- Remove (E-V+1) edges
- Maximally acyclic – Means after adding an edge will be cycle
- Minimally connected – means removable of an edge from spinning tree it will give more than one components
- maximum possible spinning tree is V ^ (V-2)

##### Solution:

- In Kruskal’s algorithm use disjoint set with find – union operation
- its greedy

##### Algorithm

- Take all edges
- Sort edges in ascending order
- Iterate all edges one by one
- find disjoint set of source vertex of edge
- find disjoint set of destination vertex of edge
- if both sets are different then,
- add edge to output list
- union both sets

- return output list of edge

Latest Source Code:

Github: MinimumSpanningTreeKruskalAlgorithm.java

**Output:**

Minimum Spanning Tree Edges: 0 - 1 --> 2 1 - 2 --> 3 1 - 4 --> 5 0 - 3 --> 6