# Kruskal’s Algorithm

Kruskal’s Algorithm uses a greedy strategy to build minimum and maximum Spanning Trees. We use the Union-Find Structure to implement it.

Intuition:

- Start with the original graph, without the edges
- Sort the edge list by weight, (ascending for minimum spanning tree, descending for maximum spanning tree)
- Go through the edge list, always adding always adds an edge to the tree if it does not create a cycle.
- Initially, each node of the graph belongs to a separate component. However, when an edge is added to the tree, two components are joined.
- When all nodes belong to the same component, and a minimum spanning tree has been found.

You can solve the Travelling Salesman Problem with that?

### Implementation

$→$ See Disjoint Set Union to implement these functions.