Prim’s Algorithm

Before focusing on the methods of greedy algorithm we need to have a basic understanding of spanning tree, what is spanning tree?

Spanning tree is a sub-graph of an undirected connected graph, which includes all the vertices of the graph with a minimum possible number of edges. If a vertex is missing then it is not a spanning tree.

As we can witness in one of the examples: this a graph G = (V,E) where V are the vertices and E represent the edges. (Number of edges are (n-1) for n vertices) so for the particular example vertices = n = 6 so edges for its spanning trees = n-1 = 6–1 = 5. Ne thing to keep in mind for spanning is to avoid forming cycles in the sub-graphs.

A weighted graph is a graph in which each branch is given a numerical weight. Therefore, a type of labeled graph in which labels represents the weight as you would have witnessed in the knapsack problem.

Minimum spanning tree is just a spanning tree of a given graph with less than or equal to the weight of every other spanning tree. One way of finding minimum spanning tree is to manually make all possible spanning trees compare their weights to find the minimum which requires too much of effort and time. So, to find the minimum spanning tree many methods are introduced Prim’s algorithm is one of those methods.

Prim’s Algorithm is a greedy algorithm that is used to find the minimum spanning tree from a graph. It finds the subsets of the edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized. Prim’s algorithm can be used in network designing, to make network cycles and also to lay down electrical wiring cables.

Prim’s Algorithm works on the principle to step by step pick the minimum weight connecting the two sets. We can enhance our knowledge on Prim’s Algorithm by once going through the following steps:

1. Begin with choosing any vertex randomly.

2. Now, discover all its neighbors and their respective branch weights.

3. Pick the minimum weight and locate the following vertex.

4. Again, repeat the step 2 & 3 till all the vertexes are located.

5. Once all the vertices are located calculate the total of the branched weights.

Now, lets see the working of the Prim’s Algorithm through an example:

As we can see in the following example by following the steps we need to choose a vertex at random and then discover its neighbors and select the branch with minimum weight and in the example if we start with 1 then 6 and 2 are its neighbors with 28 and 10 respective weight so we go with 6 as 10 is minimum then again we look at 6 neighbors and follow the previous steps again and again till all vertexes are covered but avoid forming cycles.

Minimum Spanning Tree: 10+25+22+12+16+14 = 99