CampusLearn
← CSC 312 Design and Analysis of Algorithms

Greedy Algorithms and Minimum Spanning Trees

Notes

Greedy Strategy Foundations A greedy algorithm constructs a solution incrementally by always making the choice that appears best at the given moment. Unlike dynamic programming, which considers past and future subproblems comprehensively, a greedy heuristic commits to local optima with the hope of achieving a globally optimal solution. While greedy algorithms are conceptually simple and computationally fast, they do not guarantee correctness for all optimization problems. For a greedy approach to yield an optimal outcome, the problem must exhibit two key mathematical properties: optimal substructure and the greedy choice property. Optimal Substructure and the Greedy Choice Property Optimal substructure dictates that an optimal solution to the overall problem contains within it optimal solutions to its subproblems. The greedy choice property states that a globally optimal solution can be reached by assembling locally optimal decisions without having to reconsider earlier steps. In combinatorial graph problems, these principles are heavily leveraged in Minimum Spanning Tree algorithms such as Kruskal and Prim. Minimum Spanning Trees A spanning tree connects all vertices of a connected, undirected, weighted graph without creating cycles. A Minimum Spanning Tree minimizes the aggregate weight of the included edges. Kruskal algorithm sorts all edges in non-decreasing order of weight and greedily inserts edges into the tree, rejecting any edge that introduces a cycle using a disjoint-set data structure. Prim algorithm starts from an arbitrary source vertex and iteratively extends the tree by choosing the lowest-weight edge connected to an unvisited vertex. Practical example Consider Kenya Power and Lighting Company planning an electrical grid expansion in Nakuru County. The company needs to connect substations in Nakuru Town, Naivasha, Gilgil, and Salgaa with high-voltage lines at minimal cabling cost. The distances between substations represent edge weights: Nakuru to Salgaa is 25 km, Nakuru to Gilgil is 30 km, Gilgil to Naivasha is 40 km, and Nakuru to Naivasha is 65 km. Using Kruskal algorithm, the engineers sort all potential connections: Edge 1: Nakuru-Salgaa (25 km) Edge 2: Nakuru-Gilgil (30 km) Edge 3: Gilgil-Naivasha (40 km) Edge 4: Nakuru-Naivasha (65 km) The algorithm greedily picks Nakuru-Salgaa, then Nakuru-Gilgil, and then Gilgil-Naivasha. When evaluating Nakuru-Naivasha, it detects that both vertices are already part of the same connected component, so the edge is discarded to prevent a redundant cycle. The resulting grid connects all four towns using exactly 95 km of transmission lines, guaranteeing the lowest capital expenditure.

Quiz

1. What data structure is predominantly used in Kruskal algorithm to detect and prevent cycles?

2. Why was the Nakuru to Naivasha line discarded in the KPLC electrification example?

3. Which property ensures that local choices lead directly to an optimal global solution without backtracking?

Sign in to submit and securely grade your quiz.