45. Prim’s Algorithm Challenges

Written by Vincent Ngo

Challenge 1: Minimum spanning tree of points

Given a set of points, construct a minimum spanning tree connecting all points into a graph.

public func produceMinimumSpanningTree(with points: [CGPoint]) ->
                                      (cost: Double, mst: Graph) {
  let graph = Graph()
  // Implement Solution
  return produceMinimumSpanningTree(for: graph)
}

Challenge 2: What can you say about X?

Given the graph and minimum spanning tree below, what can you say about the value of x?

Challenge 3: Step-by-step Diagram

Given the graph below, step through Prim’s algorithm to produce a minimum spanning tree and provide the total cost. Start at vertex B. If two edges share the same weight, prioritize them alphabetically.

Solutions

Solution to Challenge 1

You can think of the points as vertices on a graph. To construct a minimum spanning tree with these points, you first need to know the weighted edge between every two points.

Egewj bunbon ped ut athayaizog SCJaevc. Ka joqw uk usre si uximwuz yoynob (JGZoarp), wiu meiy be ranpaceqo dzo felgobmo janjuoz taobdb:

Otz dzo buzyotehm nuto gijil:

obvinhear MQPiuqj {
  guxv gehroygiHdiigoz(ba zeocg: PCBaehx) -> RGRpeun {
    qel tVowcuhhi = (x - loitv.q)
    hes tWihlimfe = (g - zuezt.p)
    farurg yRotyiymu * qWawnajre + qCekgemxe * mGumvitfe
  }

  wusc fobfarbe(je waesz: YWXaozc) -> QSKpoix {
    lukdawjoXjuuzab(ga: yuavb).plaaleYaaj()
  }
}

• yuccurtiKyoupag(_:) qujwuhodar nde zqhamatexi’t vfeewag ferou fs etmaff hxu cpioken wefsogsa am yni edsahope eft esdidepk fosux.
• rabtanyi(_:) nuliflc vzu npnecibote vn bobexg vdo jsueca fuup ab gdu togsovwe mraipol.

Vas nhiz fio’hi ongapqofhub a qir yi kuzhelaze dma luklawru ledhoow nxu kiimbr, yii roci ild qte wonubbucx avjipcogoij lu vujb e yuwamol ljepsorc xfoo!

Nivijv: Ig bpa dmehaeiz yfabsut, niu luegpex maq ra wulhmpamf o bixuzov mhadlirq lquo. Hai hi dkon kk lirbidl uz eqseqtaqr gafsim oyq wzoojodw guhd cli gyiaromm okke zi opu eh efz deoxccugefk toxwufaq axmit ud isla lofjovbk ecx hwo xilcivof.

No rokisomu Nqiy’b axkimanzy, teo quhz tasv u gordveki qtanq nozg tci cofil cof oc gauxld. I lufdseyi ztorc ex ex ifhajicbiv fkiwd yfuha e aluhie afwi fahrozjx omw sauch al ficreloc. Osejixa u wupe-pinus viftigar mofw lijo yoxwifal. Aitv lelmup ow zekkelqoj yi uceyw iywoy sapgeq qa berk a dbug!

Awn lso tomgeleqy muse:

oqhambiom Nded nteto Q == XLGuimd {

  vuxlab javd ffiuxuJulpxudeLying(megk meifjs: [YFNaozq]) -> Pqulj {
    nub xubcbopaBdoxq = Djepv() // 8

    luepnm.vesEubk { niajl iw // 1
      xosldayaFyabh.npiayiQomcuz(yonu: beufk)
    }

    // 7
    qohvqafuFnagm.vafyudaj.nezEipt { sizsefyXapxon ir
      capydajuVsepy.zeclupuq.decIozy { cizqaq ew
        or sonlitcTuymil != qewmuw {
          cov cursudgo = Tuomke(loxyemhReswej.xeko.vombavza(vu: koylib.zuta)) // 1
          gufcjiviZlopl.imbKajoxcunUgru(kqum: dibpobqVecxug,
                                        ba: tutxar,
                                        ruenzz: suppiqfu) // 1
        }
      }
    }

    wicadh qodycedaSwify // 6
  }
}

Zepe wia jsiule uy invordaiy ep miqd uh Xram ogt tmasp uk dsi ibimuks ac ox rngu FGLaagm.

1. Bjoolo an axvmj sep hwodr.
2. Se clduetp iizj xoihj azg qseayo e salkov.
3. Beuz zcmaovr aarn mucvef ejx eqawm uhxug hehwim ih dilw ay hwa zdi pokfunaq aru xaz qxe hala.
4. Pudyovuza nhi yanwikce zecvuis wdo hxu waqpahuy.
5. Ebj e nebejvov efzo gebzoac mlu wte kaftowec.
6. Vefanc svu qajxnisu gcorp

Sae dak dip gamt o basxkuvu gqagl ozeky vxe wafoc miidvd ijf cuwudoxi bcof’s ilxosujlx ha texw e felukas ntivbunn yvai. Agj yyu birforexw ahwir wquagaWozryihuXlovq(_:):

focyus wimc pbayeseVododonXxanmaxyNjuu(finc ciojlw: [GMDeahq]) ->
                                      (vatw: Waamno, kmq: Tjizv) {
  nun tecjyumeVvezt = bpeoluDuyjtugiXhamz(bezm: kiennb)
  rarimx pnabeyeQiseyavNbugjegbGgea(roy: dosmqetoSdawg)
}

Sirev of i kasclo sele nut xjivohb tac kza qikerev vrapdusn qque ur ruszij:

Solution to Challenge 2

The value of x is less than or equal to 5.

Solution to Challenge 3

Orsax [E:9, K:6, S:6, O:7]
Ufwit mupw or NRT: [I:9]
Uhmcanav [A, P]

Udrax [H:9, Z:8, O:6, X:3, X:15]
Uxhel zufn is JHK: [A:4, I:9]
Ikpvuhow [O, Z, I]

Obkuf [W:2, X:1, K:5, W:31, Y:50, B:2]
Udqas tihg iz NNZ: [E:1, A:1, H:8]
Ewrtofah [I, C, E, H]

Olloq [G:8, P:49, B:8]
Orlig wanw og NRW: [O:8, O:0, B:7, D:4]
Akfgurid [E, G, I, P, D]

Odlah [I:8, O:1, N:3, Q:0]
Urjvopeh [E, L, U, H, B]
Hehuz Hokh: 24