Minimum Spanning Tree (Prim's)

DSA · Graphs

Theory

A minimum spanning tree (MST) connects all vertices of a weighted undirected graph using the minimum total edge weight, with no cycles. Prim's algorithm grows the tree from one starting vertex, always adding the cheapest edge that connects a vertex inside the tree to one outside it. With a priority queue it runs in O(E log V).

Why we use it

MSTs give the cheapest way to connect everything, such as laying cable or pipes.

When to use it

Use MSTs for network design, clustering, approximating travelling-salesman routes, and connecting cities or offices at minimum cost.

How it works

  1. Start from any vertex; heap of edges
  2. Pop the cheapest edge to an unvisited vertex
  3. Vertex already in tree? Yes: Skip. No: Add vertex and edge to tree.
  4. Push its edges to unvisited vertices
  5. Stop when all vertices are in the tree

Syntax

in_tree = {start}
while not all vertices in tree:
    pick cheapest edge (u in tree, v outside)
    add v and the edge

Time: O(E log V) with a heap

Example

graph = {
    "A": [("B", 2), ("C", 3)],
    "B": [("A", 2), ("C", 1), ("D", 4)],
    "C": [("A", 3), ("B", 1), ("D", 5)],
    "D": [("B", 4), ("C", 5)],
}

def prim(start):
    in_tree = {start}
    chosen, total = [], 0
    while len(in_tree) < len(graph):
        best = None
        for u in in_tree:
            for v, w in graph[u]:
                if v not in in_tree and (best is None or w < best[2]):
                    best = (u, v, w)
        in_tree.add(best[1])
        chosen.append(best)
        total += best[2]
    return chosen, total

edges, cost = prim("A")
print("MST edges:", edges)
print("Total cost:", cost)

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic