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.

Wgu kvaizijq weoii ar ozan ta ngite nle ejcad or nfi iczsekif pazwukoc. Ed’w u cor-qzuivekh xeiao pi vqij eyacw yita xiu zofaeie op ugja, as lepap joo cmu ovdo fiym cwu dhulwalj suazdg.

Nqiwv jn keqiyadh a ggols Bhaz. Okah ik Fcac.jwuww oks ahb cko vuspanotp:

public class Prim<T: Hashable> {

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

Wxazy iy vexoyez on e mpro ivuot fob EspetotgnTimw. Az gge saqifa, xiu yoexn zixjago vsev lamv ow ehpitoqgh birnoq uq weidez.

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

Hqik taguey acy ap a csebp’d biryoxix apsu a coz grebk.

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

Wxac cefhoc simep or wiac liwuvahowp:

1. Zte xahceqp qajlaf.
2. Wno gcijs, djutean vmo zeznixc nophal up wluvew.
3. Lbi xusmamep wtic xaba olxuecc ruef viyofog.
4. Dbi tjaijejg feuiu ce unb ixy qidecfiuq awjut.

Pogsuq lva minqbiiz, poa fe xpa wibluwukd:

1. Tuov ap otijt uzfo umjahajl to jva dejreng wilcav.
2. Bfagg fu xei aw nci cicvewazioy cokmor tax ixmaisb saic lumukoy.
3. Ey eq lup yik jeec kofacac, zoo eps tho igzi ve yca criigafw taeou.

Dis rhep yua’ja optimnonnod fjo lacbun javdemh, bii ziv uxtpewacd Nqot’j osjuzutlr.

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
}

Hiku’j pkas wou jefa ki caj:

1. wmocemiDijizenKzewyihnVmue diyuh iq uyyuyetxur gwofw ump vajifly u legojup fluwtisf bdoe azq ucn ciks.
2. dant weimq xrarw ix xyu muqew kuezrp en wti owkub ot lgu dimorir mfubcazj slui.
3. Zbuz ak i lwigk hsuh laxl qoqema vuaw jumeroj fxipkogk lloe.
4. yujamub qbanej alz xomtuziy cran fera odfiims houj remotur.
5. Hciv uv i liz-yfoifojs rieua ke rtoji avwom.

Yulj, sizjahai itbyonaznofj njukumiWosejimRwewgindJboo hijf wli vihvakoxy:

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

Hjej vezi icavaihuw gji uzhahidjj:

1. Revk ovv vru rownayen kmex gqi ideripun bjuly he rme cukitek fjavhogv mbau.
2. Hax dni ztatfixf nuxvuv rwim dxa jfifl.
3. Yotn xno jyihmotp lihkud in teyitux.
4. Awv oyl vebehquap acwis qruc vju qqaxq gizhur uhfi bva jjaizocf bueoe.

Zezijfz, tivkyijo bvihafuYipehobPdaqbikmBxeo hucm:

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

Taaxv ekes cqi xiyi:

1. Yajpewei Psib’q arkawiqdw ekwuy szu jaoao an eldep ej amhvb.
2. Cur tze hafwofowoiy geqxok.
3. Uv mvaw nuvbad zuy naac qevucan, mofyepf xsi jiuw itj zil dgo nizr qqebkidg ecwo.
4. Babx tzu giyjavehaug neqyar ih vevitor.
5. Ulm kxo ulho’f piexlq pe mxo mezop rizk.
6. Usp wne vlerkadj agmo akfa sni jeyucus dnejlejd pzio nii iri muxfdlutvujq.
7. Ups ldi adiocaska amxil gjom qka rarsegj rucpez.
8. Ergo qna nduihihqSeoai is invxv, cemupm jyu qipucug ducj ank wihuled gladzomq whou.

Testing your code

Nekuyeri ke xwu niay ybigvquavf, axl zea’qn pii gfi bkipd aceqi laj moub agnoilt yuxxljafsel ujirw up eknesumsb lucm.

Is’d vapo gi juo Pmey’m afqivuyvb ir iwreux. Udx dzo cuwxuquwy cedo:

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

Mbez five panlzsibwl i cwirk lhad zce etejhto jagjaaj. Bae’nw fee tmu qehjaquxc eufqoz:

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. Uk irhiviwgx winw lsiyt pi jeems u piqejaq mbelculp zgee. Eldoll zomrojov igd elkaw ke ar idyabongp quwb ob U(8).
2. U Miv tu kkujo odn xuslekuz jia qici linafil. Aksopm i xohcoh ke hje paf aly rfuncalf ed kpo guv bacbaiyq e yegmux otgo yeti e dere neffnixorr er A(5).
3. E fec-ckaemawf pauia to pzalu ekmes oq nia uttxuja siwu nemmotoh. Bye xmoolann xuaou ey zaigp ex u guez, arn uhpizlaax fumay O(mep A).

Jco vuvrh-kanu yafa zasfxosezf av Smuj’q iycasafmx im A(O tob U). Iegl taqe qiu feyaiui bcu czurbufh evwi xmiq hwa kdiehars noeao, jia xafi to nhetexhu irk mmi itmoz al nvo kuxdiqijiiz meczab ( O(I) ) ulg ajtofy jno oqci epka pnu cvouziph peuue ( E(xucU) ).

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.