5.1.1. Kruskal's Algorithm

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. So, prim's algorithm starts with some edge and gradually expands the edge into a tree, whereas Kruskal's algorithm follows the other strategy, which is to order all the edges in ascending order of weight.

Kruskal's Algorithm is another approach to find a minimum cost spanning tree in a graph. Unlike Prim's algorithm which builds a tree starting from a single edge, Kruskal's algorithm begins by sorting all the edges of the graph based on their weights. This means it organizes the edges from the smallest weight to the largest, setting the stage for building the minimum spanning tree step by step.

Think of Kruskal’s algorithm like planning a road trip. Instead of starting at one city and expanding outwards, imagine you have a map with various roads listed by length. You would first list all the roads by their length and then choose the shortest ones first to connect cities, ensuring you don't create any loops in your route.

So, it keeps trying edges from smallest to largest and for every edge if it can add the edge without violating a tree property, it adds it. Now, in the process of adding the edge, it may not actually construct a tree, all it makes sure, it does not violate the tree property, then it does not produce a cycle.

In Kruskal's algorithm, after sorting the edges, the algorithm repeatedly checks if the smallest edge can be added to the growing tree. Each time it checks an edge, it ensures that adding this edge does not create any cycles — which is crucial because a spanning tree cannot have cycles. If the edge can be added without creating a cycle, it is included in the tree.

Imagine you're building a fence in your backyard. You need to add panels without creating any loops. Whenever you decide to install a new panel, you must check that it doesn't lead back to the starting point; otherwise, the fence would have a circular path, which is not the design you're aiming for.

So, here is a kind of high-level view of the algorithm, so let the edges be sorted in order e1 to em. So, we start with an empty tree, so again we will keep the tree as the list of edges and now we are going to scan this in order, 1 to m. So, let i be the index of the edge to be tried next. So, long as we are not yet added n minus 1 edges.

The algorithm starts with an empty tree and iterates through the sorted list of edges. It continues this process until it has added 'n - 1' edges (where 'n' is the number of vertices). Since a tree with 'n' vertices must consist of 'n - 1' edges, reaching this count signifies a complete minimum spanning tree.

Let’s say you're collecting stamps, and you need a total of 10 stamps for your collection. You start with none and look for the best stamps to collect. Each time you find a new stamp (like adding an edge), you check whether adding this stamp fits in your collection without duplicating a type you already have. You keep doing this until you reach your goal of 10 unique stamps.

Now, once we have n minus 1 edges we can stop. So, so long as the length of the tree in terms of the number of edges is not n minus 1, we have to add some more edges. So, we look at the next Ei, if Ei does not form a cycle when added to TE we append, then we look at i plus 1.

The condition of having 'n - 1' edges is critical in determining when to stop adding edges. If adding an edge would create a cycle, the algorithm simply discards that edge and moves on to the next. It continues this loop until the desired number of edges has been added, ensuring the final result is a valid spanning tree.

Consider building a bridge system between several islands. You want to connect them, but if a bridge connects two islands in a way that forms a circle with other bridges, it would not serve the intended purpose. Thus, each time you consider a new bridge, you check that it doesn’t connect back to form a loop before deciding to build it.

Kruskal's algorithms is also a greedy algorithm. Here, we make a choice well in advance, we say right at the beginning let us sort all the edges and do it in that order.

Kruskal's algorithm is classified as a greedy algorithm because it makes a sequence of decisions by selecting edges based on their weights, starting from the smallest. This strategy is to optimize the overall solution – in this case, to ensure the sum of weights of selected edges is minimized in order to form the minimum cost spanning tree.

Think of someone shopping for the best deals on essential groceries. Instead of grabbing the first items they see, they might first list all items by price and start purchasing the cheapest ones first, ensuring that their total spending is minimized.

So, now we have to just decide how to keep track of this property of forming a cycle. Remember that whenever we add an edge, you must first check it forms a cycle and if it does not form a cycle you must include.

To efficiently manage cycle detection, the algorithm employs the union-find data structure. This structure helps track and merge components efficiently, minimizing the need to scan through all vertices, thus speeding up the process of determining whether an edge can be added without creating a cycle.

Imagine you have a group of friends who sometimes join or leave the group. To quickly find out if two friends belong to the same group (and therefore if adding a new member would create a loop), you keep a simple record of who belongs to which group, enabling quick updates each time someone joins or leaves.

The first step in Kruskal's algorithms requires it to sort edges. So, we know that we can sort in m log m time, but n is at most n square, so log n will be the same as log m. So, this sorting text m log m time.

The overall complexity of Kruskal's algorithm is primarily driven by the edge sorting step, which has a time complexity of 'O(m log m)'. The additional operations for merging components and checking cycles can add complexity, but properly utilizing the union-find structure can help maintain efficient performance.

Think of sorting your bookshelf. First, you organize all your books by title (which takes time depending on how many books you own) before figuring out which ones can fit together on each shelf (which is quick if you have a good cataloging system). With the right sorting approach, you can minimize the total time spent organizing your books.

--