Prim’s Algorithm is similar to Kruskal’s Algorithm. It’s a greedy algorithm that finds the MST (minimum spanning tree) for a weighted, undirected graph. Starting at an arbitrary vertex, the algorithm builds the MST one vertex at a time where each vertex takes the shortest path from the root node. Let’s move to our example.
Although we can begin with any vertex, we’ll choose vertex A for this example. Vertex A has direct edges to B and I. The cost to vertex B is 7 and the cost to vertex I is 15. Since Prim’s algorithm is a greedy algorithm, it chooses the edge with the lowest weight, which is edge A-B in this case. The numbers in green represent the order of vertex discovery.
Vertices A and B can now see vertices C and I. Vertex B has access to C and vertex A has access to I. Looking at vertex C, the distance from B to C is 5; the distance from A to I is 15. Prim’s algorithm chooses the smallest edge, which in this case is from B-C.
The algorithm must consider all the edges that are visible from all of the already discovered vertices. The undiscovered, visible edges now are A-I, C-E, C-D, and C-G. By comparing the weights of each edge, Prim’s algorithm concludes that the lowest weight is from vertex C to vertex E, so it chooses that edge.
The algorithm now has access to edges A-I, C-D, C-G, and E-D. Edge E-D has the lowest cost, so the algorithm chooses it next.
Prim’s algorithm now must consider the following edges: A-I, C-G, and D-F. Edge C-D is not considered since both vertices have already been found. If that edge is chosen, a cycle would be created. Edge C-G contains the smallest weight, so it’s chosen next.
There are three undiscovered vertices left. Prim’s algorithm will choose the least costly edge from the following: A-I, D-F, G-F, and G-I. Edge G-F contains the least costly edge, so it’s chosen next.
Prim’s looks at edges A-I, F-H, and G-I. Since G-I is the smallest edge, Prim’s chooses it next.
Finally, vertex H can be accessed via edge F-H or edge I-H. Since edge I-H is smaller, Prim’s algorithm chooses it.
Since all the vertices have been found, the algorithm ends. The minimum spanning tree has been found. The order of vertex discovery is as follows: