Prim's Algorithm From A Starting Vertex

Growing a Tree from a Starting Vertex

A minimum spanning tree connects all vertices of a connected weighted graph with minimum possible total edge weight. Kruskal’s algorithm builds one by considering edges across the graph. Prim’s algorithm takes a different approach: it starts at one vertex and grows a single connected tree, adding one new vertex at a time. At each step, it chooses a lightest edge from the vertices already reached to a vertex not yet reached.

Throughout, graphs are finite, simple, undirected and weighted, with real edge weights. The weight of a set of edges is the sum of their weights. A tree is a connected graph with no cycles; a spanning tree of \(G\) is a subgraph that is a tree and contains every vertex of \(G\). A minimum spanning tree is a spanning tree of minimum total weight. The algorithm permits negative weights as well as zero and positive weights.

An edge with exactly one endpoint in \(S\) is called a crossing edge for the cut \((S,V\setminus S)\). Only crossing edges are eligible. An edge with both endpoints in \(S\) cannot bring in a new vertex; an edge with both endpoints outside \(S\) does not touch the growing tree. Because each chosen edge adds a new vertex, the selected edges do not create a cycle.

The process assumes that a crossing edge exists whenever \(S\ne V\). This is guaranteed if the graph is connected. If the graph is disconnected, a run from \(r\) can reach only the connected component containing \(r\), and it stops when that component has been reached.

The Selection Rule in Practice

At every step, compare the weights of all crossing edges, not just the edges incident to the most recently added vertex. An edge from any vertex already in \(S\) may be the next choice. The following procedure records enough information to make each decision auditable.

The cut property, established in the earlier material on cuts in weighted graphs, explains why this local choice is useful: a minimum-weight edge crossing a cut is safe, meaning that there is a minimum spanning tree containing that edge. Prim’s algorithm applies the property to the cut defined by its current reached set. The traces below focus on carrying out the selection rule; a full correctness proof is a separate question.

Ties and the Starting Vertex

The minimum crossing edge need not be unique. In a tie, the algorithm may choose any edge attaining the minimum; different tie-breaking choices can produce different trees. A starting vertex is part of the run’s specification, but it does not mean that every later edge must touch that vertex. The only restriction is that each selected edge crosses the current reached set.

What Happens in a Disconnected Graph?

If the graph is disconnected, there is no spanning tree: no connected subgraph can contain vertices from separate components, because there is no edge joining those components. Prim’s algorithm from a specified starting vertex still makes sense, but it stops after reaching the starting vertex’s entire component. In particular, an isolated starting vertex has no eligible edge and the run stops immediately.

Why the Process Produces a Tree

Proof. Let \(S\) be the reached set and \(T\) the selected edge set. Initially, \(S=\{r\}\) and \(T=\varnothing\); the selected subgraph on \(S\) is connected and has no cycle. Suppose the algorithm has made \(k\) choices. Each choice adds exactly one vertex not previously in \(S\), so \(|S|=k+1\). The new edge joins that vertex to a vertex already in \(S\). It therefore keeps the selected subgraph connected. It cannot create a cycle, because its new endpoint was not in the previous subgraph. Inductively, the selected subgraph on \(S\) is a tree with \(k\) edges.

If the original graph is connected and \(S\ne V\), choose a vertex outside \(S\). A path from \(r\) to that vertex must contain an edge with one endpoint in \(S\) and the other outside \(S\). Thus an eligible edge exists, and the process adds one more vertex. Since the graph is finite, this continues until \(S=V\), after exactly \(|V|-1\) choices. The selected subgraph is then connected, acyclic, and contains every vertex: it is a spanning tree. For a disconnected graph, an edge from the reached set to a vertex outside the component of \(r\) cannot exist, while every vertex in that component can be reached along a path from \(r\). Hence the run stops with exactly that component reached. If the component consists only of \(r\), it stops at initialization, with zero choices. \(\square\)

This proposition verifies the shape and stopping behavior of the output. The minimum-weight selection has an additional role: by the cut property, each chosen lightest crossing edge is safe for the current cut. The selected tree’s global minimum-weight guarantee requires connecting these local choices across the run; that full correctness argument belongs with the dedicated proof of Prim’s algorithm.

Common Mistakes

Choosing only from the newest vertex is not Prim’s rule. In the first example, after choosing \(AC\), the reached set is \(\{A,C\}\). The eligible edges are \(AB,BC,CD,CE\); the lightest is \(BC\) of weight \(1\). Looking only at edges incident to the newest vertex \(C\) happens to include \(BC\), but in other steps it can miss the best edge from an older reached vertex. Always compare all crossing edges.

Do not keep an edge whose endpoints are both reached in the candidate list. For example, after the first step of the five-vertex run, \(AC\) has both endpoints in \(S\), so it is ineligible even though it is an edge of small weight. Adding it would not bring in a new vertex and could create a cycle.

Do not treat a disconnected run as a spanning tree. If the algorithm stops while \(S\ne V\), inspect whether any crossing edge remains. No such edge means the starting component has been exhausted; it does not mean the unreached vertices have somehow been included.