Greedy Algorithms & Minimum Spanning Trees

CSE310 Recitation — Consolidated Deck

Greedy Basics Activity Selection Fractional Knapsack Kruskal Prim

Agenda

Greedy fundamentals
When greedy works (and when it doesn’t)
Examples: Activity Selection, Fractional Knapsack
MST recap & properties
Kruskal’s Algorithm — walkthrough + pseudocode
Prim’s Algorithm — walkthrough + pseudocode
Kruskal vs. Prim comparison

Tip: Use ←/→ or Space to navigate.

What is a Greedy Algorithm?

Definition: Make the locally optimal choice at each step hoping to reach a global optimum.

Local vs Global

Local view: choose what looks best right now.
Global view: best overall solution.

Works well when…

Greedy-choice property
Optimal substructure

When does greedy work?

✅ Works

Minimum Spanning Tree (Kruskal, Prim)
Fractional Knapsack
Huffman Coding
Activity Selection

❌ Fails

0/1 Knapsack
Traveling Salesman Problem
Longest Path
Subset Sum

Example 1: Activity Selection

Given activities with start/finish times, select a maximum-size set of non-overlapping activities.

Strategy: sort by earliest finish time.

Example 2: Fractional Knapsack

Items can be split into fractions. Capacity W = 50.

Item 1
v=60, w=10, ratio=6.0

Item 2
v=100, w=20, ratio=5.0

Item 3
v=120, w=30, ratio=4.0

Pick by highest value/weight ratio.

Greedy for Graphs

Minimum Spanning Tree (MST): connect all vertices with minimum total edge weight.

Shortest Paths: find cheapest routes between vertices. (Not covered here.)

We focus on MST: Kruskal and Prim.

MST Properties

Cut property: For any cut, the lightest crossing edge is in some MST.
Cycle property: For any cycle, the heaviest edge is in no MST.
Connected, undirected, weighted graphs; result has V−1 edges.

Kruskal’s Algorithm

Sort edges by weight; scan from lightest to heaviest, adding an edge if it doesn’t create a cycle (use Disjoint Set Union).

Sort edges ascending by weight
Make each vertex its own set
For each edge (u,v): if Find(u) ≠ Find(v), add and Union(u,v)
Stop when we have V−1 edges

Kruskal: Example & Walkthrough

Click Step to start. Target: 7 vertices ⇒ 6 MST edges.

Kruskal: Pseudocode

function Kruskal(G):
    MST = ∅
    sort edges by weight
    for v in V: MakeSet(v)
    for (u,v,w) in edges:
        if Find(u) ≠ Find(v):
            MST ← MST ∪ {(u,v)}
            Union(u, v)
    return MST

Prim’s Algorithm

Grow a tree from any start vertex. Always add the cheapest edge from the tree to a new vertex (use a min‑priority queue).

Pick a start vertex and mark it visited
Push all edges from visited → unvisited into a PQ
Extract the cheapest (u,v); if v unvisited, add (u,v), mark v visited
Repeat until all vertices are visited

Prim: Walkthrough

Start from A. Click Step to grow the MST.

Prim: Pseudocode

function Prim(G, s):
    MST = ∅
    visited = {s}
    PQ = edges from s
    while |visited| < |V|:
        (u,v,w) = PQ.extractMin()
        if v ∉ visited:
            MST ← MST ∪ {(u,v)}
            visited ← visited ∪ {v}
            push edges from v into PQ
    return MST

Kruskal vs. Prim

Aspect	Kruskal	Prim
Approach	Edge‑driven	Vertex‑driven
Data structure	Disjoint Set (Union‑Find)	Min‑Heap (PQ)
Typical graphs	Sparser	Denser
Complexity	O(E log E)	O(E log V)
Start vertex	None needed	Any (result independent)

Wrap‑up

Greedy is powerful with the right structure (cut & cycle properties).
Kruskal and Prim always produce an MST on connected, undirected, weighted graphs.
Practice on different graphs to see where each shines.