5.4.1. Initialization

We have seen one algorithm for the minimum cost spanning tree namely prim's algorithm. Now, let us look at the other strategy we talked about namely Kruskal's algorithm. So, we are looking for a minimum cost spanning tree, in a weighted undirected graph.

Kruskal's algorithm is a way to find a minimum cost spanning tree for a connected, weighted, undirected graph. Like Prim's algorithm, which we previously discussed, Kruskal’s algorithm constructs a spanning tree, but it operates differently. Instead of adding edges gradually from a starting point like Prim’s, Kruskal’s algorithm sorts all the edges of the graph in ascending order based on their weights and attempts to add them one by one.

Think of a road trip where you want to build the least expensive map of roads connecting cities. Instead of starting from a city and picking the next closest location, you gather all the road options available and sort them by cost. You then add roads starting from the cheapest until you've connected all the cities without creating any loops.

Kruskal's algorithm follows the strategy of ordering all the edges in ascending order of weight. It keeps trying edges from smallest to largest. For every edge, if it can add the edge without violating the tree property, it adds it.

The key idea behind Kruskal's algorithm is to maintain a collection of edges that form a tree. The tree property states that in a tree, adding any edge must not create a cycle. Therefore, after sorting the edges, the algorithm checks each edge sequentially and adds it to the growing tree if it does not connect two vertices already in the same component. This process continues until exactly n-1 edges have been added, where n is the number of vertices in the graph.

Imagine you are building a fence around a garden. You want to use the least amount of fence material, so you inspect all available pieces of fencing. You start with the shortest pieces, adding them one by one to connect the corners of the garden. Each time you add a piece, you ensure that it connects two corners that aren't already connected to avoid creating loops.

So long as we have not added n minus 1 edges, we keep looking at the next edge. If the edge does not form a cycle when added, we append it; if it does form a cycle, we discard it.

In Kruskal's algorithm, the stopping condition is critical. We need to track how many edges have been added to our tree. For a graph with n vertices, the minimum spanning tree will contain exactly n-1 edges. Once we reach this number, we can stop the algorithm. Hence, while the number of added edges is less than n-1, the algorithm will continue checking and processing the edges sorted by weight.

Picture yourself assembling a jigsaw puzzle. You keep adding pieces to the puzzle until it is complete, which means there are specific spots where pieces connect without overlapping or going outside the edges of the puzzle. Once you reach the last piece that fits, you know your puzzle is complete.

We need to keep track of whether adding an edge would form a cycle. If it does, we discard the edge; if it does not, we can add the edge.

Cycle detection is a crucial part of Kruskal's algorithm. When trying to add an edge, we need to ensure that the two vertices it connects are not part of the same tree (or component) already. If both vertices are from the same component, adding the edge would create a cycle. To track this efficiently, we can use data structures like union-find to maintain and merge components dynamically.

Imagine trying to connect two parts of a train network. You need to ensure that connecting tracks do not lead back to the same station, which would create a circular route. To avoid this, you check which stations (components) are currently connected before choosing to add a new track (edge).

To manage the components and check for cycles effectively, we use a data structure called union-find. This allows us to create and merge components efficiently.

The union-find data structure helps in efficiently tracking and merging components of the graph. It supports two main operations: 'find,' which determines the component a vertex belongs to, and 'union,' which merges two components. Using these operations, Kruskal's algorithm can quickly determine whether adding an edge creates a cycle, allowing for faster execution.

Think of union-find like having a set of labeled boxes, each containing a single item initially. When you find two boxes that hold items you want to combine into one, you label them both with the same identifier, indicating they now contain the same group of items. This way, you can quickly check which items are grouped together without needing to open each box individually.

--