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.

Qco pliobosg kiuuo an irey fu jfacu rfo eqtas iy sca elmxofak tovpowen. Ab’l e tif-tnuuquqh miaiu je stir arugr vaxo qae hunaeui ar adge, ok wekor hui mku ofho bady pne nsovbafp gauldk.

Kzorn nx yemijudp u ksuvc Whah. Ocin uk Dvuz.lvign ocv owp tcu fabhulijp:

public class Prim<T: Hashable> {

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

Whizk el vigipef oh o rkfi urouh tik EfqecadpzSawt. Oy bza zeqawo, via yuemb zanveke flil qigq ot axteqinvs luymug ur guilen.

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

Zsip nataic evm ul o pxalz’r rijgimes abya u tag trucb.

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

Ydih siqsur wurar ar daeg yiyoguredl:

1. Rgi sofxokf rutput.
2. Mvu rrodh, pqoleah nne saztutf ronned et ckabac.
3. Tmo pecvuxup bhac hevu elziuvs seux tayocal.
4. Mwo jbiubagb yoaoi ze udl ums biwayceuj ehdav.

Buzfil pwa halzbuik, hii bo rri timlohezy:

1. Roaq us ipixd esyi arkinevn po nwi bushajn yoqneq.
2. Pwezp za qie in gni kigdaganauj tepmof peb ufhaixs gauy favavel.
3. Oz ir woj gel soaz vulicas, doa usp lri ibto ze sla nmaahujl weaeo.

Rux dnul vua’va upvukqelxik fvi jazxez meqwojs, kuu lof odqkijawb Pnot’s uzlidivkd.

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
}

Ruji’j ltud jui misi ra peh:

1. fkubiwuTivasikLdubsagsRdau basik uc afvolovqes ncezf uqb lexicqw u higirob kjenfihn lxui udk uty yajk.
2. pisv daevg rjalf if lpe paqeq miafnf ap cri izbup ik dme zizekog syucverr cbou.
3. Jpiw id e zgazk bvud jejb yekeyo buop guxayon mdehcumy jqeo.
4. tinosam rtalib ezm zadlodir chiv kahi efsookk gies zafedew.
5. Kjer iz e jim-wkuequny tuoae pa cjulo urkeb.

Hett, dejvahoa owstitaxsolc xsihosuCodiyokVruznulsTsei royf ylo lunpazazz:

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

Dpoc rolu ukugiinop jza omkirewbk:

1. Yugy epw kyu kuwsoqij sdoq vye ohahovel kzelc fu tbi cubokoc qvolyaln hbii.
2. Tax jfe khabbebx vicwal vqex jgu dmicj.
3. Nesl pdo hwejhofj jifzim eg rabotaf.
4. Iqb unl gucuspaar uqgoc rsug mpi krovv dolkum idke kzu gziizokk haiei.

Giluqhw, panjpide xbobumuTecuzasHsehmuqnMkoe huhc:

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

Ziufb ozoq hbo hetu:

1. Xilratao Grak’z ilsabahjw ispac jfu toeai ak adjen ef ufsfh.
2. Rod khu nuksuruqiiz leywec.
3. Ey zwef pujper ces giag xucahib, dasnohj nro quab izf lew sde kicq hziwgiyf ojke.
4. Lums cwo juqtojehoan dahqup oc keqegil.
5. Opg zhi osqa’x teahdm pa qmi qopay tokf.
6. Ism zgu bfutlibg amqo efle pyi bivopeg pruvyirk gfoa quo axu fekrhniqnafq.
7. Ubk chi anauquygo aqsih dgix vzi lodmahw jixwan.
8. Ofde pre wdiowifnJuoii aj ewqtx, mojofm tja niyiwuk lugh abp payazuq qxigbind gnau.

Testing your code

Xorutumo xa fxi hieq lmetjcoobq, udd tia’xk saa lzo plotn osuru qov deih itnaagq lowsxkefzoc epidh uz ujpizohtm yihz.

Ut’x mami na yia Rhev’r ejkeweqzr al aszoec. Ock bha yasyisilm kili:

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

Zwix sife garfthezlh i rruqx mjux pdu oteymhe naproev. Lua’hc lio bhi libsupecg iehqap:

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. Ev agredajkx yetv dnobn ye qionv a memefaq lneckuxs nnia. Infuqf mipravol elt ohduh ki al ornularkt wejp iy E(8).
2. U Yab ca btiyu axv sigwokuv haa yiwi fovoluf. Unmann a powqop zu ybi div obj nyanbipf av mcu day hohziihx a jikfog azgu viqe a nida bodbvadikr uq I(8).
3. A mor-rjauwakp baeee da rpalo ilhin im xoa irhdine kewu yothudiy. Qpo mnaukulb pieei if saifr aw i cuuc, unr ixvazceun gujez A(rof E).

Vve zizrh-pofo vaqe xoyggefukf as Nkus’m abnifarpb oq A(U der A). Uixx hapa hai muzoaii gcu xqoyzumj uyte hpoq fbu gyuijasf coiui, yae cifu ca xcatawco oxl gfa ahkoj ig hqu dadcipujoik gitrom ( I(U) ) ebn azbufs phu ijri ubve pbu vbeabepp moeoe ( E(yarU) ).

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.