5.1. Design and Analysis of Algorithms

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. 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.

Kruskal's algorithm is a method for finding the minimum cost spanning tree in a weighted undirected graph. Unlike Prim's algorithm, which builds the tree incrementally from a starting edge, Kruskal's algorithm sorts all edges based on their weights and adds edges one by one. The main condition for adding an edge is that its inclusion should not form a cycle in the tree structure.

Imagine you are building a network of roads between cities, and you want to minimize the cost of construction. You would first list all possible roads sorted by their cost. You would then begin constructing the cheapest road first, followed by the next cheapest, while ensuring that you don't create a loop that connects back to the starting point, just like you wouldn't want a road that leads you back to where you started.

Now, in the process of adding the edge, it may not actually construct a tree, all it make sure, it does not violate the tree property, then it does not produce a cycle. So, if we keep adding edges, so long as we do not produce cycles and at the end the claim is we get a minimum cost spanning tree.

When implementing Kruskal's algorithm, for each edge being considered, we check whether adding it would create a cycle. As long as the edge keeps the property of being acyclic, it can be added to the tree. This is crucial because a spanning tree must remain a tree, meaning there cannot be cycles within it.

Think about stringing lights around a garden. You want to ensure that the string doesn’t loop back to a previous point, which would create a tangled mess. Each time you add more string (each edge) to your setup, you check to ensure it continues around the garden without intersecting with any parts of the string already laid out.

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.

Initially, we sort all the edges in the graph by their weights. After sorting, we start with an empty tree and examine each edge in sorted order. This process continues until we have added n-1 edges, where n is the number of vertices in the graph. This is because a tree with n vertices must contain exactly n-1 edges.

Imagine a team of builders lining up materials needed for construction by cost. They start with the cheapest materials and progressively select the next best option, ensuring they don’t run out of resources (cycles in terms of graph). They continue this until they have enough materials to complete the project.

So, long as length of the tree in terms of 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. If it does form a cycle, we just discarded and go ahead.

The algorithm continues checking edges one by one. If an edge can be added without creating a cycle, it is added to the tree. Conversely, if adding the edge would create a cycle, it is disregarded, and the algorithm moves on to the next edge. This ensures that the constructed structure remains a tree.

Picture a puzzle where you are adding pieces one at a time. If adding a piece causes two pieces to overlap (which creates a cycle), you set that piece aside and try the next piece until your puzzle is complete.

So, Kruskal's algorithm is also a greedy algorithm, in this case we do not make incremental choices, local choices at every point, we will look at what we do next, based on what we know now.

Kruskal's algorithm is classified as a 'greedy' algorithm because it makes decisions based solely on the immediate smallest edge available. It does not consider the future implications of adding an edge but instead focuses on the current option that minimizes cost at that moment.

Imagine a person choosing a route to travel. If they opt for the road with the least amount of tolls at each junction without considering the final destination, they are acting greedily. They might save money at each step, but this method could lead them to a longer route overall.

So, once again we will use the same result that we used for Prim's algorithm, this minimum separator lemma. So, recall what the lemma said, it said if you take a set of vertices and separate out into two non-empty groups U and W ... this edge must be there at every spanning tree.

The Minimum Separator Lemma states that if you divide a set of vertices into two non-empty groups, the smallest edge connecting these two groups must be part of any minimum spanning tree. This provides a theoretical foundation for why including certain edges is crucial in Kruskal's approach.

Think of separating two teams in a game. The quickest way to allow interaction (and thus a win) between them must involve the shortest possible bridge (the smallest edge). If this connection is absent, no minimum connection can be made between the teams.

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, we must first check it forms cycle and if it does not form a cycle you must include.

To ensure we do not form cycles when adding edges, we keep a record of which vertices belong to which components. By doing this, we can check whether two endpoints of an edge are in separate components. If they are, adding the edge will not create a cycle.

Think about a social network. Each person represents a component, and checking if two individuals can form a friendship without overlapping existing connections is like ensuring that linking two edges doesn’t form a loop. If they can be connected without breaking existing friendships, the connection is valid.

So, the easiest way to check whether the edge does not form a cycle is to keep track of the components… for every j in our set now the problem is that these components could have been merged earlier.

The Union-Find data structure is essential for efficiently managing the components of the graph. It supports two main functions: finding which component a vertex belongs to and merging two components. This allows Kruskal's algorithm to operate efficiently without the overhead of linear scans through all components.

Consider a family gathering where you need to find out if two people are members of the same family (component). The Union-Find structure allows you to quickly determine their family ties and also to unite families when marriages occur, efficiently updating the connections without having to check each extended family member each time.

So, what is the complexity well a first step in Kruskal's algorithm requires it to sort edges. So, we know that we can sort n merges and m log m time, but n is at most n square, so log in will be 2 times log n.

The overall complexity of Kruskal's algorithm involves sorting the edges, which takes O(m log m) time, where m is the number of edges. After sorting, the algorithm iterates through the edges, making union-find operations that can be amortized to a logarithmic time complexity, resulting in an efficient overall time of O(m log n).

Think about organizing a library's book collection. The initial sorting of books by title might take considerable time. However, once sorted, adding a new book only requires checking its position in the sorted collection, much quicker than if you had to sort everything again from scratch.

--