Prim's Minimum Spanning Tree

Watch a minimum spanning tree grow outward from a start node — at every step, the cheapest edge crossing the cut pulls one new node into the tree.

Time: O(E log V)

Space: O(V + E)

Uses: Min-Heap

Greedy: Cut Property

Start Node:

Speed: 1100ms

Step 1 of 0MST weight: 0

Not in tree

Frontier (cut)

Joining

In MST

MST edge

MST edges: none yet

Time:O(E log V)

Space:O(V + E)

Data Structure:Min-Heap

Strategy:Greedy (cut)

Question 1 of 3

What does Prim's algorithm build?

DSAverse

Graph Algorithms

Loading Graph Algorithms...

BFS Traversal

visited: 0 / 7