Greedy Edge Selection (MST & Matching Intuition)

Greedy edge strategies sort or prioritize edges—safe for MST cut property; dangerous without proof on general graphs.

Why this shows up in the real world

Maps & routing, social networks, and dependency systems are modeled as graphs—vertices are places or tasks, edges are roads or prerequisites.

Core idea (explained for students)

Sort edges by weight ascending (Kruskal). Under constraints, filter infeasible edges before greedy pick. Exchange argument proves MST greedy steps.

Try this in Python

class UnionFind:
    def __init__(self, n: int) -> None:
        self.p = list(range(n))
        self.r = [0] * n

    def find(self, x: int) -> int:
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.r[ra] < self.r[rb]:
            ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]:
            self.r[ra] += 1
        return True


uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
print(uf.find(0), uf.find(3))

Common mistakes

• Greedy shortest path on general graphs (not Dijkstra).
• Picking local best edge without global feasibility check.

Key takeaways

• Prove or cite cut property for MST edges.
• Constraints → often matroid or DP, not naive greedy.