2.5.2. Kruskal's Algorithm

We are looking for a tree which sits inside the graph, which is a sub graph in terms of the number of the edges, which connects all the vertices in the original graph. So, such a tree is called a spanning tree, it spans the vertices of the original graph, but it forms a tree outer the sub set of three edges.

A spanning tree is a special subset of a graph that includes all the vertices while containing the minimum amount of edges necessary to maintain connectivity. This means that a spanning tree must connect every vertex without forming any loops (cycles). It essentially allows all points in the graph to be reachable without redundancy in connections.

Imagine a network of roads connecting various towns in a district. A spanning tree would represent the minimum number of roads necessary to connect all towns, where there are no loops (no path that circles back on itself) ensuring efficient travel routes.

Now, suppose that the graph also has weights. In this example, the weight for instance could be the cost of repairing a road. So, supposing restoring the road has a cost and now the government would like to not only restore connectivity, but do it I mean at minimum cost.

Weights in a graph represent costs associated with edges, such as expenses for repairs or construction. In the context of finding a minimum cost spanning tree, we want to not just connect all the nodes but also do it with the least expenditure. This can lead to choosing different spanning trees based on their total weight (cost).

Think of planning a budget for building a road network. You want to connect several locations (towns) but also need to keep the spending to a minimum. For instance, if one road costs significantly less to repair than another, you'd prioritize repairing that road while ensuring all towns remain connected.

Remember that by definition, a tree is a connected acyclic graph. So, the graph in general will have n vertices, so the claim is that any tree has exactly n minus 1 edges.

A defining property of trees is that for any tree with 'n' vertices, there will always be 'n - 1' edges. This is important because it indicates that adding any edge to a tree will create a cycle. Being acyclic, a tree allows for a straight path of connectivity without any return routes.

If you have a group of n people who want to connect with each other in a team meeting, each person needs to shake hands with n-1 others to ensure everyone is connected. If someone shakes hands too many times (more than n-1), it means they would be returning to shake hands in a loop—breaking the 'tree' (or connected) rule.

Our target right now is to build a minimum cost spanning tree. So, there are two naturally greedy strategies that one can think of.

To build the minimum cost spanning tree, two main strategies can be used: Prim's Algorithm, which starts from a given vertex and adds the smallest edge, or Kruskal's Algorithm, which sorts all edges by weight and adds them while preventing cycles. Both strategies ensure that the resulting tree connects all vertices at the minimum possible cost.

Consider that you're a city planner. You could either assemble your road connections one segment at a time from a starting point (similar to Prim’s) or review all potential road segments sorted by cost and select them one by one, ensuring you never build loops (similar to Kruskal’s). Each method strives to ensure all areas are linked up at the minimal cost.

The other strategy we can have is to look at edges in ascending order of cost and keep adding them, so long as we do not violate the tree property.

In Kruskal's Algorithm, we start with a sorted list of all edges based on their weights. As we pick the smallest available edge, we must ensure it doesn't create a cycle. If it doesn’t, we can add it to our growing list of edges in the minimum cost spanning tree. This continues until we've added 'n - 1' edges.

Imagine shopping for the cheapest ingredients to make a meal. You look at all the items you need, prioritize the cheapest, and add them to your cart while ensuring no duplicates (just like avoiding cycles in a tree) until you have everything needed to make the full meal without wasting resources.

--