4.1.2. Executing Prim's Algorithm

So, let us try and execute before during the complexity analysis of these things. So, remember we can start anywhere. So, let us start at 1, right. We start at 1 and we mark our tree consisting of form. Now, since this is an edge start at 1, we have to update the values in the neighbours of 1, namely at 2. So, we mark for 3. We say that is the distance which we mark in green, so the tree is 18 because the tree consist vertex 1 and it is neighbour in the tree which is at the distance is the vertex 1. Similarly, the other neighbour of 1 is 2.

Prim's algorithm starts with any arbitrary vertex. In this case, we choose vertex 1. We create a tree starting with this vertex. Next, we examine the neighbors of vertex 1, which in this example are vertices 2 and 3. We determine the distances from vertex 1 to these neighbors. The tree has vertex 1, and we note the distances to its neighbors for future consideration.

Imagine you are at a social gathering, and you want to build connections. You decide to talk to a friend (vertex 1), and from there, you identify other friends around you (neighbors) that you might want to connect with, noting how far they are from your initial point. You make a mental note of who is closer and might be easier to reach out to first.

Now, having added 2, we have this update. So, we look at the neighbours. So, the neighbours of 2 are the vertex 3 and vertex 5. For the vertex 2, we have a new distance 6. So, if you go via to the distance of 3 to the tree 6 and there it could be connected to 2 which is 6 is smaller than 18, right. So, 18 was earlier best estimate of how far 3 were in the tree.

Once we add vertex 2 to our growing tree, we check its neighbors, which are vertex 3 and vertex 5. By calculating the distances from vertex 2 to these neighbors, we update our records if we find a shorter path. Here, the previous distance from the tree to vertex 3 was 18, which now gets updated to 6 because moving from vertex 2 to vertex 3 is more efficient.

Returning to the social gathering analogy, after connecting with friend 1 (vertex 1) and then to friend 2 (vertex 2), you discover that friend 2 knows other friends (vertex 3 and 5) you haven’t reached out to yet. You find out that the first friend (vertex 3) is actually closer than you thought, making it easier to establish that connection.

Now, we again pick the smaller of the two. So, we will pick this vertex 3 to add to the tree, right. Once we add it, you will obtain the status of 4 because that is the only new label we do not update the status of 1 because 1 is already been added to the tree.

After updating the distance information, we need to select the next vertex to add to our tree. We choose the vertex with the minimum distance to the tree, which in this instance is vertex 3. Once it's added, we proceed to check its neighbors, which allows us to update distance values for those vertices.

Continuing with our gathering example, after bonding with friend 2, you learn that friend 2 can also introduce you to friend 3 (vertex 3), who can help you further expand your social circle. You log this information and move on to make more connections with friends based on who’s closer or whom you should reach out to next.

So, the complexity also is similar to Dijkstra's algorithm. We have an outer loop which runs n times order n times because we have to add n minus 1 edge to form that tree and each time we add vertex with the tree.

The overall structure and function of Prim's algorithm share similarities with Dijkstra's algorithm regarding complexity. Prim's algorithm includes an outer loop that runs proportional to the number of vertices in the graph. For each iteration, it incorporates one vertex, gradually completing the minimum spanning tree structure.

If we liken this process to building a network of friends, each time you meet someone new, you form a stronger connection until all friends are part of your network. The effort required to maintain and expand this network mirrors the efficiency needed in each round of Prim's algorithm, ensuring connection with the closest friends first.

Overall complexity exactly let x of m log n plus m log n. So, this comes from finding the minimum because n time we have to find the minimum and this comes from the updates, because we have to do m updates overall. Each update takes log n times.

Prim's algorithm's efficiency can be enhanced by using data structures like heaps. This allows the algorithm to find the minimum distance quickly and perform updates efficiently. The result is an overall time complexity that can be expressed as O(m log n), where m is the number of edges and n is the number of vertices, providing a clearer scope of the algorithm's performance.

Think of searching for the best connection among friends as efficiently as possible. With the right organizational tools, like a contact app that sorts friends by closeness or recent talks, you can efficiently find and reach out to the right people quickly. This better structuring mirrors how heaps improve the algorithm's performance.

--