2.5.1. Prim's Algorithm

So, our target right now is to build a minimum cost spanning tree. So, there are two naturally greedy strategies that one can think of. One is, since you are looking for a minimum cost tree to start with this smallest stage and incrementally build the tree. So, we keep adding edges to the existing tree, so that the new graph remains a tree and it grows as little as possible it terms of cost. This will give raise to an algorithm which is called prim’s algorithm.

In Prim's Algorithm, the goal is to find the minimum cost spanning tree of a graph. This means we want to connect all the vertices (or nodes) with the smallest total edge cost without forming any loops. To achieve this, we start with the smallest edge available in the graph. We then continuously add the smallest edge that connects a new vertex to our growing tree, ensuring that we do not form cycles. This incremental approach leads us to build a tree with minimal cost.

Imagine you are building a power line network in a new community. You want every house connected, but you also want to minimize how much you spend on materials. You start by connecting the house that has the least distance to its nearest neighbor. Then, every time you add a new connection, you choose the shortest remaining available line that connects a new house until everyone is connected.

The strategy in Prim’s Algorithm is to start with the smallest weight edge and then incrementally grow a tree. So, we start with a smallest edge here which is the edge weight 6 between 2 and 3. Now, we have to look at the existing tree which consists of this order the graph and decide whether to add one of these four edges to extend it.

In this step of Prim's Algorithm, we initiate our tree by selecting the smallest edge. For instance, if the smallest weight is 6, we choose the edge connecting vertices 2 and 3, effectively starting our spanning tree. Next, we check all edges connected to our newly added vertex to see which can be added next while keeping our tree a single connected component. We always choose the edge with the lowest weight that connects a new vertex to the existing tree.

Think of Prim's Algorithm as building a highway system. You start by constructing a short road between two towns that are closest together (the smallest edge). After that, every time you want to build a new section, you look for the next shortest road that connects a new town to the existing roads until all towns are linked.

If we look at possible edges that we can add, we have this edge, we have this edge and we have this edge. Now, the smallest among these is the edges with wait 18, but if I had that we get a cycle. So, this is not a good edge to add. So, therefore, we must add one of the other 2, again to pick the smaller one, which in this case is the edge labeled with weight 20.

An important aspect of Prim's Algorithm is to avoid adding edges that would create cycles. Once we have added our smallest edge, we look at potential edges that can connect to our growing tree. If we find an edge that would lead to a loop (a cycle), we discard this option and instead choose the next smallest edge that maintains the tree structure. For example, if the smallest remaining edge would create a cycle, we choose a different edge that connects without forming a loop.

Picture a family trying to connect different rooms in a house with new wiring. They must ensure that the wiring forms a single path without looping back on itself. If they find that laying a new wire in a certain direction would connect back to an already connected point, they would choose a different route to avoid redundancy.

So finally, we add that in this is a tree that we can get. So, this is the final tree, we get from Prim’s Algorithm, let us starting from the smallest edge and incrementally growing the tree.

After expanding our tree with several edges, we continue to apply the same process of adding edges. The goal remains to choose the cheapest option that keeps our tree connected without forming cycles. Once we have added enough edges to connect all vertices (n - 1 edges for n vertices), we finalize our minimum cost spanning tree. This tree is characterized by the property that it has the least total weight among all possible spanning trees.

Think of the last steps of connecting a neighborhood's roads. After strategically placing the necessary links to connect all homes, the infrastructure is complete! You ensure every street serves a purpose without creating unnecessary detours or roundabouts.

--