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:

A, B, C, E, D, G, F, I, H.

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Algorithm and many more.