Prim's Algorithm: Step-by-Step Execution

Step 1: Start with vertex A
A
B
C
D
E
4
2
3
1
5
6
7
8
Priority Queue:
A-E: 1
A-B: 2
A-D: 3
A-C: 4
We start by selecting an arbitrary vertex (A). We add all edges connected to A to our priority queue, sorted by weight.
Step 2: Add vertex E to MST
A
B
C
D
E
4
2
3
1
5
6
7
8
Priority Queue:
A-B: 2
A-D: 3
A-C: 4
E-B: 5
E-C: 6
E-D: 8
We select the edge with the lowest weight (A-E: 1). E is now part of our MST. We add all edges from E to our priority queue, but only if they connect to vertices not yet in the MST.
Step 3: Add vertex B to MST
A
B
C
D
E
4
2
3
1
5
6
7
8
Priority Queue:
A-D: 3
A-C: 4
E-C: 6
B-C: 6
E-D: 8
Next, we select the edge with the lowest weight (A-B: 2). B is now part of our MST. We add any new edges from B to vertices not in the MST to our priority queue.
Step 4: Add vertex D to MST
A
B
C
D
E
4
2
3
1
5
6
7
8
Priority Queue:
A-C: 4
E-C: 6
B-C: 6
D-C: 7
We select the edge with the lowest weight (A-D: 3). D is now part of our MST. We add any new edges from D to vertices not in the MST to our priority queue.
Step 5: Add vertex C to MST (Completed MST)
A
B
C
D
E
4
2
3
1
5
6
7
8
Priority Queue:
Empty - All vertices in MST!
We select the edge with the lowest weight (A-C: 4). C is now part of our MST. All vertices are now included in our MST. The algorithm is complete! The total weight of our MST is 1 + 2 + 3 + 4 = 10.