Computational Thinking

Table of Contents

Prim’s algorithm
- What is it?

In GUI browsers, I have this page themed dynamically, so when it's dark outside, you'll get a dark theme. You need JS enabled if you want the dynamic theme; I don't run any JS-based analytics or tracking.

Prim’s algorithm

What is it?

Finds minimum spanning tree for a connected weighted undirected graph. Faster in dense graphs with more edges than vertices.

Spanning tree: connected acyclic subgraph that contains all vertices of the graph

weight of tree: sum of weights on all the tree’s edges minimum spanning tree: spanning tree of smallest weight

Steps:

Select any vertex to be first of T
Consider which edge connects vertices in T to vertices outside T. Pick any one with min weight. Add edge and vertex to T.
Repeat step 2 until T has every vertex of graph.