Introduction

Welcome to the final course in the Graph Algorithms series! Like Kruskal, Prim's Algorithm builds a Minimum Spanning Tree: the cheapest set of edges that connects every vertex without a cycle. The two algorithms reach the same answer by different routes.

Prim grows the tree outward from a starting vertex. At each step it adds the single cheapest edge that connects the tree to a vertex not yet in it.

The graph is undirected and weighted, given as n (vertices 0 to n - 1) and edges, a flat array of triples [u0, v0, w0, ...] for an undirected edge u - v of weight w. We start from vertex 0.

Let's finish the series!