SPPU | Third Year | Sem VI | 310253 — Artificial Intelligence
Master these core concepts before running the simulation. Each card builds on the previous one.
A greedy algorithm builds a solution step-by-step, always picking the locally optimal (best-looking) choice at each step. It never goes back to reconsider past decisions.
You're shopping on a budget. You walk through the store and always grab the cheapest item that meets your need first. You don't look at the entire store before deciding — you just pick what looks best right now.
Key idea: "Make the best choice right now, and hope it leads to the best overall solution." For many problems (like MST), this greedy approach is provably optimal.
A spanning tree is a subgraph that connects all vertices in a graph using the fewest possible edges, with no cycles (loops). For a graph with V vertices, a spanning tree always has exactly V − 1 edges.
Imagine 6 villages (A–F) connected by roads. A spanning tree is a set of roads that lets you travel from any village to any other — but with no unnecessary loops. With 6 villages, you need exactly 5 roads.
A Minimum Spanning Tree is the spanning tree with the smallest possible total edge weight. There may be many spanning trees for a graph, but the MST has the lowest total cost.
You want to connect those 6 villages with roads, but roads cost money (the edge weights). The MST is the set of 5 roads that connects all 6 villages at the cheapest total cost.
Our goal: Find the MST of the given graph starting from vertex A. The optimal MST has a total weight of 20.
Prim's algorithm builds the MST one edge at a time, always choosing the cheapest edge that connects the growing tree to a new vertex.
For a graph with V vertices, we repeat this V − 1 times, adding one edge each time. Our graph has 6 vertices, so the MST will have 5 edges.
Vertices already included in our growing tree. Like a CLOSED list — once a village is connected, we don't need to reconnect it.
Edges from MST vertices to non-MST vertices. Like an OPEN list — these are our options. We always pick the cheapest one.
Think of it as expanding a road network. The MST Set is the villages already connected. Candidate edges are the roads available to build next — and you always build the cheapest road that reaches a new village.
At each step, Prim's algorithm picks the locally cheapest edge — the one with the smallest weight among all candidates. It doesn't look ahead or reconsider past choices.
This greedy strategy is provably optimal for MST. By always adding the cheapest safe edge, we're guaranteed to find the minimum spanning tree. No backtracking is ever needed — the greedy choice at each step leads to the globally optimal solution.
Prim's = Greedy + Optimal: Unlike many greedy algorithms that only give approximate solutions, Prim's greedy approach gives the exact optimal MST every time.