Q18Data Structures

In the mathematical field of graph theory, the concept of a spanning tree is foundational for optimizing network designs, routing protocols, and clustering algorithms. Understanding spanning trees and the greedy algorithms utilized to minimize their total cost is a critical competency in advanced data structures.

1. Theoretical Definition of a Spanning Tree

Given a connected, undirected graph mathematically denoted as $G=(V,E)$—where $V$ represents the set of all vertices (nodes) and $E$ represents the set of all connecting edges—a Spanning Tree $T=(V,E^{\prime })$ is rigorously defined as a specific subgraph of $G$ that strictly satisfies three immutable criteria:

• Total Vertex Inclusion: The subgraph $T$ must physically include every single vertex present in the original overarching graph $G$. None can be orphaned or omitted.
• Acyclic Topology: The subgraph $T$ must be structurally a tree, meaning it is mathematically impossible to find any closed loops or cycles within its edge connections. A traversal from any node to any other node has exactly one unique path.
• Edge Minimization: Consequently, to satisfy the above two conditions simultaneously, if the original graph $G$ possesses $N$ vertices, every valid spanning tree $T$ must contain exactly $N-1$ edges.

While a single dense graph can theoretically spawn thousands of vastly different valid spanning trees, engineering problems usually demand optimization. In a weighted graph—where every edge is assigned a numerical cost, length, or resistance—the overarching objective is to discover the Minimum Cost Spanning Tree (MST). This is the specific unique spanning tree whose aggregate edge weights sum to the absolute mathematical minimum possible value.

2. Kruskal's Greedy Algorithmic Paradigm

Kruskal's algorithm is a highly efficient, greedy algorithmic approach specifically designed to compute the MST of a given weighted graph. A "greedy" algorithm makes the locally optimal choice at every discrete stage with the hope of discovering the global optimum. Kruskal's methodology achieves this by sorting edges and iteratively building a forest.

Step-by-Step Algorithmic Procedure:

• Step 1 (Edge Sorting): Extract every single edge from the graph $G$ and rigorously sort them into a sequentially ordered list strictly in ascending order based on their assigned numerical weights. This ensures the algorithm evaluates the cheapest options first.
• Step 2 (Forest Initialization): Initialize a dynamic "forest". Treat every single isolated vertex in $V$ as its own independent, disconnected tree component. If there are $N$ vertices, you start with exactly $N$ isolated trees.
• Step 3 (Greedy Edge Selection): Iteratively traverse the sorted edge list from cheapest to most expensive. For every candidate edge $(u,v)$ connecting vertex $u$ to vertex $v$, perform a crucial cyclic check.
• Step 4 (Cyclic Validation via Union-Find): Determine if vertex $u$ and vertex $v$ already belong to the same connected tree component within the forest. If they do, adding this edge would disastrously create a closed cycle, violating the spanning tree definition. Therefore, unequivocally reject and discard the edge.
• Step 5 (Component Merging): If vertex $u$ and vertex $v$ currently belong to completely separate, disjoint tree components, accept the edge. Add it to the official MST set, and mathematically merge (Union) the two separate tree components into a single, larger connected component.
• Step 6 (Termination Condition): Continuously repeat Steps 3 through 5. The algorithm definitively terminates the exact moment the MST successfully accumulates exactly $N-1$ accepted edges. At this precise point, all vertices are guaranteed to be interconnected into a single, unified minimum spanning tree.

3. Practical Application and Step-by-Step Trace

We will now rigorously apply Kruskal's algorithm to the specific provided graph configuration. The graph consists of exactly 6 distinct vertices ($V=\{A,B,C,D,E,F\}$) and 9 weighted edges. To form a valid spanning tree, we strictly require $N-1=6-1=5$ edges.

Phase 1: Sorting the Edge List:

We compile and sort all available edges by weight in strict ascending order:

• 1. Edge (B, C) - Weight: 1
• 2. Edge (A, C) - Weight: 2
• 3. Edge (D, E) - Weight: 2
• 4. Edge (E, F) - Weight: 3
• 5. Edge (A, B) - Weight: 4
• 6. Edge (B, D) - Weight: 5
• 7. Edge (D, F) - Weight: 6
• 8. Edge (C, D) - Weight: 8
• 9. Edge (C, E) - Weight: 10

Phase 2: Iterative Greedy Selection:

We systematically evaluate each edge from our sorted list:

• Iteration 1: Evaluate Edge (B, C) [Weight 1]. Vertices B and C are disconnected. Action: ACCEPT. Components merge. (Edges in MST: 1)
• Iteration 2: Evaluate Edge (A, C) [Weight 2]. Vertices A and C are disconnected. Action: ACCEPT. Components merge. (Edges in MST: 2)
• Iteration 3: Evaluate Edge (D, E) [Weight 2]. Vertices D and E are disconnected. Action: ACCEPT. Components merge. (Edges in MST: 3)
• Iteration 4: Evaluate Edge (E, F) [Weight 3]. Vertices E and F are disconnected. Action: ACCEPT. Components merge. (Edges in MST: 4)
• Iteration 5: Evaluate Edge (A, B) [Weight 4]. Vertices A and B are already intimately connected through vertex C (A-C and C-B exist). Adding this edge creates the closed cycle A-C-B-A. Action: REJECT.
• Iteration 6: Evaluate Edge (B, D) [Weight 5]. Vertex B (in the A-B-C component) and vertex D (in the D-E-F component) are completely disconnected. Action: ACCEPT. This massive bridge connects the two remaining large sub-components. (Edges in MST: 5)

4. Final Synthesis and Verification

We have successfully acquired exactly 5 accepted edges. The algorithmic termination condition is satisfied. The process definitively halts.

The accepted Minimum Spanning Tree encompasses the edges: (B, C), (A, C), (D, E), (E, F), and (B, D). To verify the ultimate optimal cost, we simply aggregate their weights: $1+2+2+3+5=13$. The total minimum cost of the spanning tree is precisely 13 units.