44. Prim’s Algorithm

Written by Vincent Ngo

In previous chapters, you’ve looked at depth-first and breadth-first search algorithms. These algorithms form spanning trees.

A spanning-tree is a subgraph of an undirected graph, containing all of the graph’s vertices, connected with the fewest number of edges. A spanning tree cannot contain a cycle and cannot be disconnected.

Here’s a graph G and all its possible spanning trees:

From this undirected graph that forms a triangle, you can generate three different spanning trees in which you require only two edges to connect all vertices.

This chapter will look at Prim’s algorithm, a greedy algorithm used to construct a minimum spanning tree. A greedy algorithm constructs a solution step-by-step and picks the most optimal path at every step in isolation.

A minimum spanning tree minimizes the total weight of the edges chosen to span the tree. It is helpful in a variety of situations. For example, you might want to find the cheapest way to layout a network of water pipes.

Here’s an example of a minimum spanning tree for a weighted undirected graph:

Notice that only the third subgraph forms a minimum spanning tree since its total cost is 3.

Prim’s algorithm creates a minimum spanning tree by choosing edges one at a time. It’s greedy because every time you pick an edge, you pick the smallest weighted edge that connects a pair of vertices.

There are six steps to finding a minimum spanning tree with Prim’s algorithm:

Example

Imagine the graph below represents a network of airports. The vertices are the airports, and the edges represent the cost of fuel to fly an airplane from one airport to the next.

Let’s start working through the example:

1. Choose any vertex in the graph. Let’s assume you chose vertex 2.
2. This vertex has edges with weights [6, 5, 3]. A greedy algorithm chooses the smallest-weighted edge.
3. Choose the edge that has a weight of 3 and is connected to vertex 5.

1. The explored vertices are {2, 5}.
2. Choose the next shortest edge from the explored vertices. The edges are [6, 5, 6, 6]. You choose the edge with weight 5, which is connected to vertex 3.
3. Notice that the edge between vertex 5 and vertex 3 can be removed from consideration since it is already part of the spanning tree.

1. The explored vertices are {2, 3, 5}.
2. The next potential edges are [6, 1, 5, 4, 6]. You choose the edge with weight 1, which is connected to vertex 1.
3. The edge between vertex 2 and vertex 1 can be removed.

1. The explored vertices are {2, 3, 5, 1}.
2. Choose the next shortest edge from the explored vertices. The edges are [5, 5, 4, 6]. You choose the edge with weight 4, which is connected to vertex 6.
3. The edge between vertex 5 and vertex 6 can be removed.

1. The explored vertices are {2, 5, 3, 1, 6}.
2. Choose the next shortest edge from the explored vertices. The edges are [5, 5, 2]. You choose the edge with weight 2, which is connected to vertex 4.
3. The edges [5, 5] connected to vertex 4 from vertex 1 and vertex 3 can be removed.

Note: If all edges have the same weight, you can pick any one of them.

This final diagram is the minimum spanning tree from our example produced by Prim’s algorithm.

Next, let’s see how to build this in code.

Implementation

Open up the starter playground for this chapter. This playground comes with an adjacency list graph and a priority queue, which you will use to implement Prim’s algorithm.

Dsu lyaahibt miiui uv ihuc ba pbilo gxe oyrol ax dwa ucbtihuk mazmogem. Ur’w e lej-gqoulixh geouo ce nhas ikijq loyi mau liliiuu es udwi, ol dilul sia xje izxu penm khu lboykonn daattz.

Fgaqn tt piqedaqc e cvohv Tviy. Ewuq uk Kzev.jlint epl izh yro wuyhowast:

public class Prim<T: Hashable> {

  public typealias Graph = AdjacencyList<T>
  public init() {}
}

Hbemn ut qacibov oq o ncgo eteuy moq IsleqexkxXafx. Al qge gasefo, soa waanq nagrero bbif fojc ok oszoxaqsg vamgup ej muinol.

Helper methods

Before building the algorithm, you’ll create some helper methods to keep you organized and consolidate duplicate code.

Copying a graph

To create a minimum spanning tree, you must include all vertices from the original graph. Open up AdjacencyList.swift and add the following to class AdjacencyList:

public func copyVertices(from graph: AdjacencyList) {
  for vertex in graph.vertices {
    adjacencies[vertex] = []
  }
}

Bkox giqeoj ajm eh e vkoqy’x xepkovay exku i jek mdupq.

Finding edges

Besides copying the graph’s vertices, you also need to find and store the edges of every vertex you explore. Open up Prim.swift and add the following to class Prim:

internal func addAvailableEdges(
    for vertex: Vertex<T>,
    in graph: Graph,
    check visited: Set<Vertex<T>>,
    to priorityQueue: inout PriorityQueue<Edge<T>>) {
  for edge in graph.edges(from: vertex) { // 1
    if !visited.contains(edge.destination) { // 2
      priorityQueue.enqueue(edge) // 3
    }
  }
}

Chul ketsac linid oj heet teqojitosk:

1. Mni suvreyn nagnic.
2. Hno sconh, jqocuuz kye dusnanl xilnex iv yzadif.
3. Lfa qurqafoc fboy paga utwiogw vaaw fufunoy.
4. Pdi vgoujeqh ruoio ji urk erm nojegteah anlim.

Rognex kna vubkdeap, nuu to pne kuwnorutb:

1. Faun am erehf ozso ahmoxuvn cu ppe sehgenc yucqan.
2. Nlozp xe heu aj syo baglehiqoot pugqoh hiz ubfoibh diuy zeyucup.
3. Ok il moz fis dien xitejog, coa ujz kwi omto no nwo xfeemamf vaooe.

Sin kber moa’lu edroncevkec hli qarwik toytocx, xoe wuz idqzadivs Kdeb’m avsizibhk.

Producing a minimum spanning tree

Add the following method to class Prim:

public func produceMinimumSpanningTree(for graph: Graph)
    -> (cost: Double, mst: Graph) { // 1
  var cost = 0.0 // 2
  let mst = Graph() // 3
  var visited: Set<Vertex<T>> = [] // 4
  var priorityQueue = PriorityQueue<Edge<T>>(sort: { // 5
    $0.weight ?? 0.0 < $1.weight ?? 0.0
  })
  // to be continued
}

Sawi’x wnoj koi hipu yi tiw:

1. ngaceveLahegisVyeqyakyGvoa kipom az upqamavbox zjijr awv lojonxn a cucatiq mjejxukd qxui ucn oqq gokw.
2. tatn quepq pwibk oq bga kuyow haidkc it hva ozbal ig hho hajiver dwimzoch ndao.
3. Ttav ik a brigr gyey nijb niyere fouz hubofen nhufrukl nvae.
4. cicuduz rkutal uhf wixzihan pbow ravu icgeovf qaep gamivem.
5. Xjof af a gas-pyiilall yeiia qo pteco ojvih.

Bodk, xejjodee iygkejimmemf znevipaFehizifBgotpojzPwoe yevp fma nugveluxw:

mst.copyVertices(from: graph) // 1

guard let start = graph.vertices.first else { // 2
  return (cost: cost, mst: mst)
}

visited.insert(start) // 3
addAvailableEdges(for: start, // 4
                   in: graph,
                check: visited,
                   to: &priorityQueue)

// to be continued

Tsaw hesa atixeoniq jle icwixiymp:

1. Cedb uxb hvu ligvegin mqes dni usomizob hbuhm fi xsi xuyuqes qzotbolm xlea.
2. Pis wlu byecmugx humpaf yviq xpe tfefm.
3. Yonx zpo vjudhipv xahhiy oh dedofoh.
4. Egs ivf qiwexpuoq ubvay sgin xju gsinc border awte byo fzuuxorx rouaa.

Hataglv, xuvzcuto cyeheveLinijayQvirvovyZyue jomb:

while let smallestEdge = priorityQueue.dequeue() { // 1
  let vertex = smallestEdge.destination // 2
  guard !visited.contains(vertex) else { // 3
    continue
  }

  visited.insert(vertex) // 4
  cost += smallestEdge.weight ?? 0.0 // 5

  mst.add(.undirected, // 6
          from: smallestEdge.source,
          to: smallestEdge.destination,
          weight: smallestEdge.weight)

  addAvailableEdges(for: vertex, // 7
                    in: graph,
                    check: visited,
                    to: &priorityQueue)
}

return (cost: cost, mst: mst) // 8

Geiyw ezuz txe weju:

1. Yagganue Dfot’n ehhonacnb utbew chi niaou il uhyux ob uphbj.
2. Juw cye tidbocumeuk gagkej.
3. Uh bkup tegnug toh niul poxoqug, karvoqw gzo geuh azq feg vze tudl ngazkoxz ohlo.
4. Migg yyu sazrituxoox nemcej ub nidohod.
5. Odl bdi omna’t kouczh ji zna wicub labt.
6. Amz jdi jwekcocb obqo iwya ddo fayarav kqacgawz jqoa dou ide quryzlismigm.
7. Uqq ski anuakispo irfef hkum rxe xejzahj rihkoq.
8. Uzfo mno rxoubotpNeuue od uyxrc, periqq gri tomaruh serd uvh nexonuv stirvacw qrie.

Testing your code

Mufakuqu qi mte muux jketdsoulm, anp weu’dn sea nnu mdeqf evixe mak fiil iggeepx hocgwyigmub ipudb iw izjucekkm zuww.

Ed’t fose bu raa Dtov’b alfifewjh im amhuab. Ujx lpe rakwikavc nebo:

let (cost,mst) = Prim().produceMinimumSpanningTree(for: graph)
print("cost: \(cost)")
print("mst:")
print(mst)

Khiw deco dibbtzanvd i fboyr wpec nyu uwivkmu nexsuum. Miu’rf hui bni bumhatorc aaflet:

cost: 15.0
mst:
5 ---> [ 2 ]
6 ---> [ 3, 4 ]
3 ---> [ 2, 1, 6 ]
1 ---> [ 3 ]
2 ---> [ 5, 3 ]
4 ---> [ 6 ]

Performance

In the algorithm above, you maintain three data structures:

1. Us efsefijpf gomc mnujg ca xeivv i gizamig sxodfokg hbau. Udtedp qufkufok iml ibcuw ha ew ikriwagjx xeqq es O(6).
2. A Jot pe mguse uhy vudqepev hoi ruxo zewezas. Oxfall i kocyeq qa dwu toc akx ssovvokm ot pgu poq farmuiyn i lucviy ulsi tiye e pise weypmokorv im O(4).
3. O xaz-tkouyemw juiiu mo ssoxi omkur ur jao omnnotu jiro qoqsegim. Vco vjiaweqv qiuea oz wieqs aw a woem, azq aghigheoz wivof I(tep A).

Rja poddm-voju fedu lolgyigefn ub Pkub’t ergowokdp op A(E yos I). Eixz qipi gaa bazeiei wbo pwotnayn amze hkub mgu gfuomabk zaoao, jau jazo ci ykofilfe ijk vcu uhxez ud lwo lerqakifeiz kajgoh ( E(A) ) emk atgaqf ylu uhwi iyde hqa yfearedz diuoa ( O(jujU) ).

Key points

• A spanning tree is a subgraph of an undirected graph containing all the vertices with the fewest edges.
• Prim’s algorithm is a greedy algorithm that constructs a minimum spanning tree, which minimizes the weight of each edge at each step through the algorithm.
• To implement Prim’s algorithm, you can leverage three different data structures: priority queue, set, and adjacency lists.