5.3. Tracking Edge Addition

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 designed to find a minimum cost spanning tree in a graph. Unlike Prim's algorithm, which grows a tree from a starting point by adding closer edges, Kruskal's algorithm processes edges in order of their weights. By prioritizing the smallest edges, it ensures that any chosen edge won't create cycles, as cycles would violate the tree structure (which should be acyclic). As the algorithm progresses, it builds up a tree by adding edges that connect different components of the graph without forming any cycles.

Imagine you're trying to connect different cities using roads so that you spend the least amount of money. Instead of starting in one city and extending roads from there (like Prim's), you first look at all available roads and build connections starting from the cheapest options, always ensuring you don't create routes that circle back to a city you've already connected.

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

A crucial aspect of Kruskal's algorithm is that it actively avoids adding edges that would create cycles. Each time an edge is considered for inclusion in the tree, the algorithm checks if including it would link two vertices already in the same component. If they are in different components, the edge can be added, contributing to the overall tree structure. This ensures that the tree remains valid with no cycles, which is essential for a spanning tree.

Think about connecting neighborhoods with bike paths. If you connect neighborhood A to neighborhood B with a path, then later try to connect neighborhood A back to neighborhood B with another path, that would just create a loop. You want straight connections that cover all neighborhoods without making any circles.

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 have not yet added n minus 1 edges.

In practicing Kruskal's algorithm, all edges are first sorted by their weights from smallest to largest. Starting from an empty tree, the algorithm examines edges sequentially. As edges are considered based on their weight, the process continues until 'n - 1' edges have been added to the spanning tree (where 'n' is the number of vertices), ensuring the requirement that a tree contains 'n - 1' edges is met.

Visualize it like making a playlist of your favorite songs based on preferences, where you select the top songs (the cheapest in terms of best choices) until you have just enough to fill a concert set (the required number of unique tracks). You want to choose wisely without repeating any song.

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

To manage cycle formation, Kruskal's algorithm keeps track of distinct components. Each time an edge is evaluated for addition to the tree, the algorithm checks if the vertices of the edge belong to different components. If they do, the edge can be added, and the components are merged. This cycle detection method is crucial because it prevents the creation of cycles within the tree as it's built.

Consider a group of friends trying to form teams for a game. Each friend represents a component, and while trying to form teams, you need to avoid grouping someone with a friend they always play with (creating a loop of play). Hence, you only mix friends who haven't played together yet.

So, we will find that what we need to do is maintain this component structure. So, assume that we want to deal with a set of components and at any given time there are many individual elements which belong to these components.

To optimize Kruskal's algorithm, a union-find data structure (or disjoint-set) is utilized to manage and merge components efficiently. This structure allows for rapid checking of component membership and efficient merging of components, which significantly reduces the time complexity of the algorithm from a potential quadratic time to a more manageable logarithmic time for operations related to merging and checking component status.

It’s similar to managing a large network of friends on social media. When you want to add friends to a group, you need to quickly find whether each person is already in the group (check their component), and if not, you merge them into the group. Having a good system in place means you can do this faster and more effectively.

--