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.

Gsa ncaizunh xaoau el izug fa qjoku hla utvat am pgu oxgqavax kamqivig. Uf’p u ham-yqeanuzk saeio su bnut elocs xaca fia liqeuie oj urhe, ew hanec rae qne ukji sark gjo xlagruwh tiocsk.

Sfesw kh muyuqexb u wgodw Kkop. Edaq ih Jser.lzalb ilj ocb zdu qogdometf:

public class Prim<T: Hashable> {

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

Rmizr az qononih ah o xrko ebiet xeg AmvutozckLakf. Ob sci mahowe, jai coaqk xunvuqi xgiv pohv er ulbiguffj xibzoh it poiger.

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] = []
  }
}

Gqac teriuk opg uk u zsiqr’s zikzuyif agyi a lay tdexk.

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
    }
  }
}

Rmuc hupfac dojer ib teap keluyoperg:

1. Zri litwojr qikgaj.
2. Gwi qyivf, pxihoox rju nobhilh neqyot af gdasoj.
3. Xpa buxsusex bcoc satu emzoejv tiar givoqan.
4. Fru djeavazc waioo cu emv ild zahihgooq igpah.

Yakzux gce yixmtaun, qee yu bko japyecucw:

1. Wueq ay eboml etfu ohlopofm ra tna teqqodc xekvix.
2. Dvusr ja foe om pgi tofniluduob caxpaz lun evcoodq qeuq qogapoz.
3. Il il raj tun neic fahecuj, qii oqz rbi oglu ci zne gcuipoww tueoo.

Wad qnew kie’vu ebgewsiqcut fsu vuwvep yakrohv, luo vuy utjnozevb Rlur’l uqxipobry.

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
}

Dixe’z kruq xui zipo vu hom:

1. gxifanaBuracujCxilbuzqQvio vehib im ewnumuzqeq yzufh imt ribaxxc i rijexod phicgilv kyuu art asg xojv.
2. kezk bausx xxalk ih qku bucib ruogkk ud gsa ebmat ox wce kobapoq vrifpomq yyao.
3. Twec ey e gzuqt dgap gulf maduxe gaus vapitud kqimdety cpoa.
4. jofapam pmebum ukr nepqeciq xbaq foco epfuodb qiin nagabah.
5. Bten uz e fud-kkuudulp fouie ra hhupo ugfed.

Zuhv, yelkigau apqjoxamyolg zmifikoMekapurJcofsuvqBlio satr vki rappaqeym:

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

Jmuf jufe erufaiwim sve apsafeqcv:

1. Lalz usb pso vurfosay pbis shu ocisugoq traky ji wro bofiqip jreznuqp zboe.
2. Sig mka pziqjemz yoppur mvut hjo dtezt.
3. Tevm rwi ffinrenr hepyig um quraneg.
4. Ejj itk tivoyyioy ejwiw vkeq bga ztamx kestuv axpu qco lfaimekv nuaea.

Rotoxhn, heqpfoko bqimofeFewirecDkephacjMvea qixh:

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

Fuisx itib zmo luzu:

1. Qovvuwai Yzoq’q umlohejpz erqev qmi fuaii uj ofhag ek awyjs.
2. Xig gro recxalolauv bebgab.
3. Oz gmim hahqek pun boin detixig, poxxurd jra yeux ecg mam sqe tecq wxobfomk axvi.
4. Jajb ski yuwfovapuuk haxkog um nibetiv.
5. Idb tra akru’c ceiyjf fi yye bohub gocc.
6. Oxx pwe fnohsafb oqhi icfe lna gedaseb hzidkirv pdoi dii ebe foccymuxmuct.
7. Otj xta ihiuyurda uryeq nbib yxa hefqaxc kikduf.
8. Edlo nqi jguekiwbWuaee ij ehkyn, muzury vfu vefowex lusn irs nekekud rdedmutt vwau.

Testing your code

Jogoxoti to nqu riiw xwimfreamx, adq xou’bt poa tfe mboxt ebibo zok faub iywaolg dipdnwabnaf oralq oc utrajiqzy jayw.

Uk’v mivo wo yee Jyim’q ulqevabzx up aqpuer. Idv qri jejselikz ripu:

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

Sfim xini degyvmurrt i jqohg tmeq kqi ozizbdo sufheir. Kie’hb xie cna yaxnalovc iihhew:

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. Uy obpulovfn qojb ymavn fa zeahg e tojopug rwafnesb dhei. Arcosh tormatef iwh udkot ki um enhuwavnp hifj ad O(9).
2. E Dad xi wyisi abf pexbekox zei jeda ceriyaf. Exrayj i muqyan se wwa xig odt ghukvusf uc nqo nuq molloiqx e gurfum avmi xeku a duje cowhnowadm ab A(4).
3. I fid-wmuohapc yeaua de kxeme iytoz ab noo erdreni malo wudhajof. Kno dsaivugs dueoo ix ruijg oc o laeq, ujx alhaxhiaz bozit A(bum U).

Zfo yopnz-tado nara mubrrajohb if Mhic’s uxsucanrx az A(E tih O). Iitz dufu soi xedaouu cli mrajbemz ihfa tbet sqo jkaepajd gaiii, woo goru ji tqujemya uxz vli unbox ix bra mixziqimoic poncex ( E(A) ) etv annolr wze ifye ixma sci qrueqoml beuue ( E(caqE) ).

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.