Spanning Tree

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:

1. Start with the original graph, without the edges
2. Sort the edge list by weight, (ascending for minimum spanning tree, descending for maximum spanning tree)
3. Go through the edge list, always adding always adds an edge to the tree if it does not create a cycle.
4. Initially, each node of the graph belongs to a separate component. However, when an edge is added to the tree, two components are joined.
5. 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

// Sort edge list in O(NlogN) time.
for (...) { 
    if (!same(a,b)) unite(a,b); 
}

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