Jarnik's algorithm, commonly called Prim's algorithm, builds a minimum spanning tree by repeatedly choosing the smallest-weight edge from the current tree to an unvisited vertex. The result connects every reachable vertex with minimum combined weight and no cycles. section 4.3
A Swift implementation follows this pattern:
- Represent edges with comparable, summable weights; WeightedEdge compares edges by weight. section 4.3
- Store candidate edges in an ascending PriorityQueue and track visited vertices. section 4.3
- Visit the starting vertex, add its outgoing edges, repeatedly select the smallest valid edge, and visit the newly reached vertex. section 4.3
- Ignore edges whose destination is already visited; invalid starts return nil. section 4.3
Connecting metropolitan areas
Applied to a weighted graph of 15 U.S. metropolitan areas, the algorithm selects edges such as Seattle–San Francisco (678), Los Angeles–Riverside (50), and Washington–Philadelphia (123), producing a spanning tree with total weight 5,372. section 4.3
Use the highlighted network to trace how selected edges connect all 15 metropolitan areas without cycles. section 4.3
