5.4. Detailed Explanation of 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. 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 the it does not produce a cycle. So, if we keep adding edges, so long as we do not produce a cycles and at the end the claim is we get a minimum cost spanning tree.

Kruskal's Algorithm is used to find the minimum cost spanning tree of a graph. Unlike Prim's Algorithm, which builds the spanning tree incrementally from an initial point, Kruskal's Algorithm looks at all the edges of the graph and sorts them by weight. It begins by considering the lightest edge and adds it to the tree if doing so does not create a cycle. The algorithm continues this process, adding edges while ensuring that no cycles are formed, until the spanning tree is complete when enough edges are added (n - 1 edges for n vertices).

Imagine a person trying to connect a series of cities with roads while minimizing the cost. They start by looking at the least expensive road first. If adding that road between two cities connects them without creating a loop back to the original city, they build that road. They continue to add roads this way until they have connected all the cities with the least total cost, ensuring no unnecessary circular routes are created.

So, here is a kind of high level view of the algorithm, so let the edges be sorted in order e 1 to e m. 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 try next. So, long as we are not yet added n minus 1 edges. Remember that if you add n minus 1 edges and we have a connected graph, it must be a tree. This is one of the various characterization that we said about trees.

Initially, all edges of the graph are sorted in ascending order based on their weights. The algorithm then begins with an empty set, which will eventually hold the edges of the spanning tree. It keeps track of how many edges have been added. As long as the number of edges is less than n - 1 (where n is the number of vertices in the graph), it examines the next edge in the sorted list. If adding that edge does not create a cycle with the already included edges, it is added to the tree.

Consider a gardener planting trees (representing vertices) in a field. They plan where to place each tree using string (the edges). They take out the string one piece at a time, testing if adding it between two trees forms a closed loop. If it does, they skip that piece; if not, they tie it and move on. They continue until they have tied all the trees together without looping back.

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 the it does not produce a cycle. So, if we keep adding edges, so long as we do not produce a cycles and at the end the claim is we get a minimum cost spanning tree.

During the execution of Kruskal's Algorithm, it is essential to ensure that each added edge does not create a cycle. A cycle is formed when a path exists that allows traversal between two connected vertices without using the same edge twice. To avoid this, we track which vertices are connected by maintaining components. If the vertices connected by the current edge are part of different components, it is safe to add it.

Think of a city trying to connect multiple neighborhoods. Each neighborhood can be seen as a component. As roads are added, planners check if two connected neighborhoods are already linked by another road. If they are, they won't add the new road; they would end up creating a shortcut that loops back into itself, which is unnecessary.

So, what is the complexity well a first step in Kruskal's algorithms 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. So, order of log n is the same as order of log m. So I can also write this is m log n, so this will be just another way of writing. So, this sorting text m log m time.

The efficiency of Kruskal's Algorithm is primarily based on two operations: sorting the edges and checking for cycles. Sorting the edges requires O(m log m) time, where m is the number of edges. After sorting, the algorithm processes each edge, leading to an overall complexity of O(m log m + n^2), where n is the number of vertices. The complexity can be improved using data structures like union-find, which allows for faster cycle detection.

Imagine a factory assembling a product from various parts. The factory organizes all the parts first before assembly (sorting) for orderly processing. If the factory uses a more sophisticated assembly line (efficient data structures), they will reduce the time it takes to combine parts (connect components) and check if any part doesn't fit without causing a problem (cycle detection).

So, this is now detailed explanation of the algorithm, so as before we let e 1 to e m being the edges sorted by weight, initially we said let every vertex 1 t on is in its own components for every j among to n components of j is j. So, 1 is the components 1 and 2 is components 2 and so on, now we start off with an empty set of edges and now we are going to run through as we set before these edges in ascending order.

The union-find data structure is used to efficiently manage and determine the connected components during the execution of Kruskal's Algorithm. Each vertex initially represents its own component. When an edge is added, the algorithm checks if the two vertices (endpoints of the edge) belong to different components. If they do, the components are merged, enabling fast future checks of connectivity.

Think of every person at a social gathering representing a vertex. Initially, everyone is in their own group (component). As people meet and interact (edges are added), they form bigger groups. The union-find structure provides a quick way to see if two people are from the same group (connected) or from separate groups (disconnected) and helps in merging groups efficiently.

--