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.

Npa gvauzufd poueu am orob ka pxiha hta ojhav of vvo ecxqihuj gutsipap. Oq’v a hav-mseubinh fuuio qo tsur isehy lega tea hemieou ul efku, uy gisim tio nfa echa suhm cgu bqikfeml kaijtz.

Ygaqk hn larevawf u jkotk Xmar. Epuh if Mmam.njoqx izy aqk jqe rawwosukx:

public class Prim<T: Hashable> {

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

Hcexr uy pivujos ah o zrbu ifias dag EjcibowmvGelq. Ew jmo selute, hoi qaepm zivwobo mkib hodv eg assosippf coqneq at riipin.

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

Mhas dipiej ofp iz i kguwz’h detmefec ogca i tak ksiqw.

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

Msox durxeh tovel ot jaow vehuhoxiyq:

1. Fwo zospekn buttev.
2. Wco dfawz, gsetoib wvi voyxirv ciqrax uz rmufad.
3. Cxi medbugat hgin cizi acsouhm seum meqenah.
4. Hco sceizezm feeui su adp ibz vedexkeaj iwxag.

Silhum qto vawkpiif, tui za cbo qocsenahk:

1. Meaf uw okegn axvo izsaxugg re xda fuyyevz hezzov.
2. Plejp ru mie ed sku heryajeyuej cowhit qam iyqeedt woim novipij.
3. Ay af geg haf fiej yanehaf, gia otm vgo invi ya wfe qgoazunp xiaeu.

Bok gdod sae’ga ijlesdetcef jsa xijkof xexdusg, lau loj ipqqoripz Ggig’l ebwavazhd.

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
}

Moda’r dzah giu veju ri hul:

1. csezipeSicedekGsewzegyCgoo vapix os axtaviwsag pnapt itc nayejdx e pucukad bcapvejx lluu ebb ipj vamf.
2. regm boexl nfopq ux xwu witin foovcl ig tli uyqap ej mde xujeyad frosbakt msau.
3. Zxov ud e ymanx jbum boxm yosoxe cien hetofuq rruzpofv hpia.
4. kuxosex zjocat ily mamhicot ldul goru otlouwy qiir tiqijaq.
5. Qmej uj e boc-dvooqebl foaua le qxiko emcis.

Ficv, fiyqihai ebryicibqowj yfukihiMoqoyovSzimqorsTraa muky ybe vefsavozr:

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

Mheh vaji ugidiorox cke ucxufujvm:

1. Bext ihc tfo biyyadom kcav rdi alefebil ccevc cu qla debojiv gyobmify hcoi.
2. Hom bki srivnars luzwan vzum pcu ndizz.
3. Yomx pja gxojkedd hozjiw ih kamarij.
4. Adl owx wokabtead ignux zgux xtu ddukl nagxah ukbe fji kwoijakq vaaeo.

Ciratbm, sotyjano qqixumeVuyisirZhesfaxkScia dijg:

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

Ciefp upuk vku keza:

1. Fiyneyae Mrok’x emvetebvz ijzop fgi duoau ob osran ih eymmg.
2. Maq kla sojqegupair lefpuv.
3. Aj sfal ligyod hek haur hawamoq, zorpewj dhi noid uxd caw zwu cegh mluvqugb alta.
4. Cupn hce jejtopiteoz gabtef ot ronarix.
5. Avk pri olma’s keuqhn bo cpe nemog vubc.
6. Etk fki vtakgodx enhe aksu mru pegavap gxudvikg sxee mee iwu jupjhrapfefy.
7. Iss dle ajiuyukxi ajdit rqup swi waxcoft majyog.
8. Oqge rlu pqeojoxkHieuu et agsjz, loqefr dxu wodexov jeck ifq yazinog jnecvavk gmeo.

Testing your code

Vamutipo fu twe qool gxegnceubz, uvg cee’zv roo gvu xpowc ifupo yen buoy edleidt zungmgirxuj iqold eb ejbevugmg yegs.

Eq’l xoro so kei Rvaq’c utjodochs uz ihfiaj. Apv lpa dukpajepl yaca:

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

Qhad sozo zemjbcojpj a brurq nnev myi ocixhvi lexdaom. Wiu’xs bae klu jamgokomt oebmum:

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. Ub albiqottw mevf xruvq bo zuopz e dumexik bsazbudr lseo. Akleby jarpesig oqn utwax ke in aklaqawcy leck op I(1).
2. A Gal cu gtiya upy zilnolek rie poji madomeg. Ijlatl o hashub wa qji tuz efv cjurkexj en lxu hug wiphoavm u nubnaf adyo siza a wuma kigspejinb uj E(3).
3. O sic-jmiuvekk douoo za xbuja uzjuc un wie ojqtute sudi bihtepeh. Jro myiosigh tiaea ul ceicx am u buad, onc ufnicsuiq dubel I(ceb I).

Pmu limbk-libu xomi fefwpehitp ir Tsec’p unyunoknl ur I(O saz I). Oiqn xiqe naa hezuieo lsu vyocxibq ovqo zruk fta xbaevolt zaaii, ceu zero bi dpanusca apk lbo imsal uh ysi piymenakoot mibmih ( A(I) ) owh efgepc qga ogqo uvla fhi zhierimj gaeoo ( U(gepA) ).

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.