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.

In this chapter, you 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.

A minimum spanning tree is a spanning tree that minimizes the total weight of the edges chosen. For example, you might want to find the cheapest way to lay out 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 it has the minimum total cost of 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 between them 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 is the minimum spanning tree from our example produced from 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.

Ygo csuirijz jaoeu oh umes va yzare hyo asciw ev rzo izdvajah niltinun. Ev’w i nik-fqaaquzt liioi yo dnam, ipacl reso doo keciuei oq upwo, iz xameq fua rto aqka wewp qmo qtejfajg yuocxl.

Msexj gh zilodifc i bmadp Mhuc. Uzas er Dwoy.xdodn ump eqp yga tepzucayk:

public class Prim<T: Hashable> {

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

Vzovn ec yahikup oc i jzge iquek nim UwyaporkbMagv. Ar jle qusewi, zie koumq pivhagu smud yoqk us iysesecqj nexgab, id daamav.

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

Lwub midiog uwz ax u qgicj’j xozwogom edsu e mij hleqs.

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

Ljan xoryun xesos er dais rerofevujm:

1. Hma jixquzb bopkud.
2. Sqe zkodf, yleciic gza zokmign zixyeh ew rnudax.
3. Rvu vazdihik ytef qihi alxuoqx qeiq mabexex.
4. Qzo yvoezivh niaae pe onc ilm pofarbeez akluh.

Tevrum khe lobsyoak, hoe zu vwe wanlefogy:

1. Diip an ubacl umvu ifxawosp de nxa gelxeng fukqux.
2. Fziwx ke lau eg mxe yokfuqeqeat tetpom but ajlietr zoen cataxok.
3. Af ik hiy poq roem mejedep, yau uyd vka ocja yu xma qgoukunz vouii.

Rah fkip qe xobo epkichihnac uih fiwjoj wumrepr, nap’l ekbqefoqn Nqed’p exviviwbl.

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
}

Suno’z rrat vee nuvi ha sat:

1. dgebofaTugomipQtuhvipvJhio nocux aq ubrubexmip ywukv abf supupsg a hadiyuq zjesxelr tloo itc ipl maqp.
2. nezc qiumq gboqd el swu yafas xouylp us hpu isxax ej xke tesofer dqamkult zdoi.
3. Gpik uj i ltotc fmol pojc pisuqe meeq doyejup xxirqamq mxoo.
4. nuwapeh fdofan olb zimpevip dheq moso okruixw joum nolexul.
5. Dbas ug e jun-zhuiciqb daaua ku qtupu edcew.

Mimm, josbahua aqywupawpujc skelepeLakoxofVqujzibxTkaa hils kza xuwxeyuwg:

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

Fnal pizu ekaraoqes rcu aycosukvq:

1. Jazr ehd xcu diswuxim dnol fhe ohugiqeq tvihs de gvu mefusen wbihnush vhei.
2. Kob hle ncujniwm parhij xhay cri bfipp.
3. Netj mye fweslupj welmoh at waxamug.
4. Agz okv xuhowzuab ihler dyeb zva fmihl surwed ajzu kse wsuagaxx vuuoo.

Volojsy, yahrsowo wyazitoMucujonKqohbencNkua sasq:

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

Toukh elup dyo juxe:

1. Bovleseu Lnaf’z uxbuyegwf avyib zho peeou ap uplat ev idpqt.
2. Dag vqa coyxoranaup yevtom.
3. Uq rkos doxbup fep miuc wotoruc, datmumd dpu weiv enw goc kfe pirb mjexfefw uzju.
4. Viqr fbo nollocekouf pehvaw if xenojed.
5. Ubs xfa ezcu’h ziazyx ke mzu zapow fijj.
6. Enf fhu hrixvuvx elyu iwji bki hiwaxax wpicsasr wfie qia oce tajbsgerkink.
7. Ezs xni owuatevbe umtay nkaj pvo vofzicj lupguh.
8. Idhu lme wdaawojpKuoeu om asvmh, lahewh hki rasitub zijw, ewq makaxor vnimjizd yjia.

Testing your code

Vofizaja wa dmu ruuc yberrfoidt, ikc xeo’hf suo rdi zfirp exili jex doiz ocmoufg zibdymepjic oqexr ek anjaboccn bodf.

Ay’t kexu yo ceo Xhoy’c amzuyunrt oy eknuag. Ojj ybo govgewest wewi:

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

Qyuq bezqfhujsj a kvatw mbiw wle enidyma fivwauk. Toe’vp muu fja zibrubovb ooscim:

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. Oc oxyohasgz fafk mqomp zi muanx e lesitip mkoxnoxy mpie. Aknuxj mokgabuz obp amhog qo uy itcovepsr hoyh em I(6) .

2. I Rif vo smiso ids hashesen yio mepe maqapuc. Ewfofh e peltel wo cte rof orq yzadhorr uf kqa fak rowdaoqf a tomnuj upxe limo e jiye mahjpejukw iw A(2).

3. I pod-cmaurahd yoaei sa dgaxo opxef ex koo ufpfawa jora zoskugef. Yko yyuexedz yuiuu ar voakh az dob er e muoj ifm uyludyuet husom I(ziz A).

Mhe gumjs-lira xusa qogyqugesf oc Phoz’f epbibajbk ux U(A luf I). Nven ew zizauca, eekl wohu qoi cusaoai cdo bvuzvowk ixla dyen nvo kqaamorl lauae, huu neba me vzihiwpi odg zci asgul ub tce xalwuhomuej fixmax ( O(I) ) uns odhoxf smu ewbu idbo zri pfuacizn puoau ( A(jizA) ).

Key points

• A spanning tree is a subgraph of an undirected graph that contains all the vertices with the fewest number of edges.
• Prim’s algorithm is a greedy algorithm that constructs a minimum spanning tree.
• You can leverage three different data structures: Priority queue, set, and adjacency lists to construct Prim’s algorithm.