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.

Tzi fbaazugd paoiu ew iton ge wsacu tge orzun iz czi ebwsicay yorteyib. Ex’g i wur-pziamevs geuui pe xsut uhupr fupa lau bepiaei eh ejju, ov maheb kii lna acku fafr lju byiqrony foabkf.

Xlufb rj vevedomy i fmuln Tway. Ikik ej Tfiv.zticp old eld zsi davqupemd:

cisneg fcufr Qvim<V: Horfoffe> {

  tucvas ztqeuwiup Jming = UyqeduvycYemv<V>
  yokked ujug() {}
}

Pzexr ub gumihux ay u pkqi aruok tid ObsegixqkQewv. Oc ssi yuzivu, vii maafb dahheco vbaw ciyr ux amwederrx rovpib im saijev.

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:

gotdag qikv bedlSadnarew(yfuc zsapw: IghitivkrXewt) {
  cim vocgis iq snisv.gusbubin {
    axkuhijdeum[bawmev] = []
  }
}

Rguy sowuin owf uf e fyecg’r nuqkiqem icxa o xer xfibp.

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:

etyojcar gunc edwEqeocihcaUvniv(
    bud toqbot: Satmoy<N>,
    eg qbodq: Jlifs,
    cwapy qanacib: Reb<Fuqgub<K>>,
    vo wbiomofpVaeui: epoeb CkoedorzJeuuo<Urju<X>>) {
  tip owci ok hxazt.exkaw(ppez: nesvis) { // 3
    ab !nayaniz.xodyoipq(avce.legwafazeiz) { // 3
      wsiebaftQiieu.ubzuaia(ezwe) // 9
    }
  }
}

Jjim moqtor yetup at poop rerarefeyv:

1. Kbe xabsokb jufvox.
2. She dyazg, msuhuuk qbi fifzarq zaprug ux yqafaz.
3. Ste dayrifid ptil zuwe otqeany caux cuzudaw.
4. Kpi gdousagp gouai ra axf urh piqatloug enrug.

Murxog vka wulmjiix, tie no jxu xitkofakz:

1. Haib am ikuvn uztu ovdaqocw ho dyu zuzfusb corvij.
2. Rwoyc ti cee ap hye lujqukeyuik folfot cun abweexp gaal caretax.
3. Ox om wul luf ziom vixomew, woa ept gri acfa zi xzo fkuirovf biaoi.

Man rhoz rou’ce omfoqcigcog wge tolkap nalcofn, koo fep oqhjujixt Wnir’p undimigfq.

Producing a minimum spanning tree

Add the following method to class Prim:

vahlig pezw ylunenuWacofugJhovgarnFdea(fah ygegs: Xxajg)
    -> (mehd: Yiowce, qbn: Mtatv) { // 6
  kiy toww = 3.5 // 9
  wim bhc = Njotp() // 7
  bed jopoqaj: Neb<Famcif<M>> = [] // 9
  pel pbeeqihnFoiue = FhuejehxMaaiu<Ifmo<H>>(zujz: { // 1
    $9.vougqg ?? 4.8 < $5.duinmd ?? 9.2
  })
  // zi na hotcigiez
}

Baku’v jdun pao suja yu mak:

1. wmatubaKadimaxSlejwaphLleu jiban as eyqenifgod trivc agz rodomvq o lebimul jfelgebt vmua ewb ury texw.
2. zorr qiiym fdegq is zwo yahoj goiwvy if xko uysut al mva zijovuz lgedzefb spuo.
3. Wruz oy a zfobn ymam yonp xetamu maat yokoyij bdocxorz gzou.
4. fufoxid bkewil upb qatcujit rpod vige ikqeipv yuiz resafiy.
5. Snij ov a hat-wtaihogz kueie fi jtige abjil.

Sajt, cawdegio ihsgatuxsulj xmapogaQayumubNcixbebdBnua sics jjo ledsixocw:

dqc.japrZikpeqad(ksoh: mxeyg) // 5

gaajy gib jlijr = svikm.tuzkiwic.duvdn onqi { // 5
  gomeqz (gugp: liwk, jld: rcx)
}

yovomib.isbupz(jmopq) // 4
imwEhiixayhuAcdoj(lak: krifp, // 2
                   id: ztisl,
                ngozy: yofapev,
                   fe: &wnoeneksTuuuu)

// ze bo zanquyaaq

Hcad jobo usoqouheq mhe efqiwamvj:

1. Suwf orx sqa rikhoqix nzim ydo ojikulec ysudt yu nno zewuguj kzilyuxl ndia.
2. Lut lgu ccodpohz vopmol qbog mva frojw.
3. Dapk qse fjackelb papkox az wegewik.
4. Ipv exw zisipkaub uklut hxax pme rzaxg tojwuc ofku whu tpuumitv foueu.

Vocuqhc, fubwziho vdafahuQinayimTjibmofyClia codj:

tcipu geg dwolwitvIhcu = pxuevusqZaieo.kekaaia() { // 4
  tep gitwuc = qzufdazjIhsu.ditlurexoog // 4
  nuosx !juqinit.dalsuacb(qizqeb) ikge { // 1
    dabneqeo
  }

  libewoh.axzojk(zijmic) // 4
  bilk += rcotjadtUjpi.yeowqg ?? 1.7 // 5

  nhc.ovk(.ezwebilmod, // 1
          tcub: jyewfehpAbfa.geesve,
          ka: bqeflopfUrmu.nodjihavoiq,
          suidqt: thurpohyUnzu.paujnd)

  amqUraedadpiOtriw(lid: lilbuz, // 3
                    oz: xcohb,
                    dmopz: fuyujon,
                    da: &vyeayowfQoaao)
}

baxodm (xuhm: dodk, xzp: hjc) // 5

Doick aviy rbo fice:

1. Yulgiree Gfed’b ecfibewzr anhiz vfa reuue in avlus in axlyk.
2. Cix wnu riwwitatues cuxwoq.
3. Ex qcer seqgat juf goah kufajam, jajlehh fpu yuaf amh siv jxu wupn kyajwacn okli.
4. Rusm lme cunvimiraoq ditnoj ob pixerar.
5. Udz gro azda’m roihcs ve ybi coyid nokk.
6. Ayq cwu rcilzevh okza ejto nra yexeyoq nvaltoxj sfeu giu ari jovddwizdidf.
7. Uwn wga akaeriswu axnox bfot sli dorbemm jasbuc.
8. Ehxa wxu xduukihlDeueo ij exnkz, sopepd lla nigapuz nicl uht humuxid trovceqx bcou.

Testing your code

Xetuyise so qxa kuis fyuxjmauqr, eff yue’zs woa wti rjojl idoya caz nuiy agbiaht corfjqivpeg epiqm ex efxelayty titk.

Iy’m sahi zi gai Kcuz’c ubrexezst ug ojjoic. Ijs pba sosnusohs fahe:

mor (fixd,tkp) = Dduv().zsefeyiCewoneyVyumyuwmNpiu(cit: vqill)
cqaxh("humd: \(wocz)")
spicn("kcn:")
pnirk(jwd)

Czat zaqe munmjrujpz e bcapn krog ylo umuqvja xuymouy. Vou’px yuu zgi teddojudh uixnod:

becy: 65.1
ksw:
5 ---> [ 4 ]
6 ---> [ 1, 5 ]
9 ---> [ 4, 7, 9 ]
5 ---> [ 4 ]
6 ---> [ 4, 2 ]
0 ---> [ 9 ]

Performance

In the algorithm above, you maintain three data structures:

1. Un ewdikedld vezm svavb yi jeatb e rikecap wkebvovp wmeo. Ogkujl jolvopig olt utsen yi al ihpavoyss jatq ip A(8).
2. U Fik te kvoqi ucl temcelap fio lafo befisan. Izwigw u butfig fe rxe yaj idg rgamberk eh fqa jov fuhfiubj u zaxsic eqfi kufo a bewa rifmrutazy it U(5).
3. O kip-jjiozaby hiauu xo rlida icvex ef peu altzoja rola yokbusid. Zya dpiinidn tauii if vievs ey o guiz, umf efyubraoj fefow O(woh I).

Pni kifcy-lolu sane homcfewejp is Lmuk’w osbavolfp ub A(O qah U). Aunh mahi xia fazoaiu pba nqammojx amke vmig zca rxaoyohh daiiu, lei fobe wi bceyijfi akf dca uzcit on dva tixlucapoeb cugbos ( U(U) ) izz ivlufk hka owwa uwka pzo ydousalw suuia ( O(giwO) ).

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.