Q21Data Structures

Prim's algorithm operates completely differently from Kruskal's edge-based approach. It is fundamentally vertex-centric. The algorithm conceptualizes the Minimum Spanning Tree (MST) as a single, rapidly expanding, cohesive entity. It initializes from an arbitrary starting vertex and continuously expands outward like a shockwave by greedily pulling in the absolutely cheapest available edge that connects the established MST to a previously undiscovered exterior vertex. This process mathematically prevents cycles and guarantees optimal total weight.

Algorithmic Trace

We are presented with a graph of 7 vertices ($0,1,2,3,4,5,6$) connected by 11 weighted edges. We initialize two structural lists: the Visited Set (representing the MST) and the Unvisited Set.

Initialization: Let us arbitrarily select Vertex 0 as the absolute mathematical origin point. Visited Set: {0} Unvisited Set: {1, 2, 3, 4, 5, 6}

Iteration 1: Analyze all edges extending outward from the Visited Set ({0}): - Edge (0, 1) $\to$ Weight 2 - Edge (0, 3) $\to$ Weight 6 The algorithm greedily selects the minimum available edge: (0, 1). Vertex 1 is absorbed. Visited Set: {0, 1}

Iteration 2: Analyze edges extending from {0, 1}: - Edge (0, 3) $\to$ Weight 6 - Edge (1, 2) $\to$ Weight 3 - Edge (1, 3) $\to$ Weight 8 - Edge (1, 4) $\to$ Weight 5 Minimum edge is (1, 2). Vertex 2 is absorbed. Visited Set: {0, 1, 2}

Iteration 3: Analyze edges extending from {0, 1, 2}: - Edge (0, 3) $\to$ Weight 6 - Edge (1, 3) $\to$ Weight 8 - Edge (1, 4) $\to$ Weight 5 - Edge (2, 4) $\to$ Weight 7 Minimum edge is (1, 4). Vertex 4 is absorbed. Visited Set: {0, 1, 2, 4}

Iteration 4: Analyze edges extending from {0, 1, 2, 4}: - Edge (0, 3) $\to$ Weight 6 - Edge (1, 3) $\to$ Weight 8 - Edge (2, 4) $\to$ Weight 7 (Redundant, both in set) - Edge (4, 3) $\to$ Weight 9 - Edge (4, 5) $\to$ Weight 1 - Edge (4, 6) $\to$ Weight 4 Minimum edge is (4, 5). Vertex 5 is absorbed. Visited Set: {0, 1, 2, 4, 5}

Iteration 5: Analyze edges extending from {0, 1, 2, 4, 5}: - Edge (0, 3) $\to$ Weight 6 - Edge (1, 3) $\to$ Weight 8 - Edge (4, 3) $\to$ Weight 9 - Edge (4, 6) $\to$ Weight 4 - Edge (5, 3) $\to$ Weight 11 - Edge (5, 6) $\to$ Weight 2 Minimum edge is (5, 6). Vertex 6 is absorbed. Visited Set: {0, 1, 2, 4, 5, 6}

Iteration 6: Analyze remaining edges connecting to unvisited vertex 3: - Edge (0, 3) $\to$ Weight 6 - Edge (1, 3) $\to$ Weight 8 - Edge (4, 3) $\to$ Weight 9 - Edge (5, 3) $\to$ Weight 11 Minimum connecting edge is (0, 3). Vertex 3 is absorbed. Visited Set: {0, 1, 2, 3, 4, 5, 6} (All Vertices Included!)

Final Synthesis and Conclusion

The mathematical algorithm explicitly terminates as every single vertex from the original graph has been successfully fully absorbed into the overarching Spanning Tree structure.

The definitively constructed Minimum Spanning Tree is composed precisely of the following calculated edges: (0, 1) [wt: 2] (1, 2) [wt: 3] (1, 4) [wt: 5] (4, 5) [wt: 1] (5, 6) [wt: 2] (0, 3) [wt: 6]

The absolute total optimal minimum cost of the network is the mathematical summation of these isolated weights: $2+3+5+1+2+6=19$.