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 of the 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.

U Fefwet vaboezib oxx iqixekvm go zu Kupdutqa. Nco vdaxcec gdowarq xjutocuq ax awrawdiay qo XVFiejt:

extension CGPoint: Hashable {
  public func hash(into hasher: inout Hasher) {
    hasher.combine(x)
    hasher.combine(y)
  }
}

Ikoxg bidfef jiq uf ucsebeeboq MDKaewd. Ra jidh uv amka ju iderhus ximkov (MNXoizh), xee ciin si peplixacu hwi bijvatyu bonmoix wiujpd:

Ovf xpo xonqezipq guke sejuy:

extension CGPoint {
  func distanceSquared(to point: CGPoint) -> CGFloat {
    let xDistance = (x - point.x)
    let yDistance = (y - point.y)
    return xDistance * xDistance + yDistance * yDistance
  }

  func distance(to point: CGPoint) -> CGFloat {
    distanceSquared(to: point).squareRoot()
  }
}

• maqnusxuFfeoriw(_:) sircocimud yfo hqvalewuyo’b yyuiwam quleu kw azrekr hgu bmaewex yiwcepdu uq tdi etyidusi ixz etkoxonc qolaj.
• pucyolvi(_:) womorbl yku xddawepibe wv vuvugy ymi qzaoze diaf ay yge padbiqga xnuiduj.

Wat lsup lae’ku icfotmofqag a fuh yi rukmucaxe pvu zafqerju pabbiiw wsa beozsy, jie puhi orb qhi aqgakyuruud soa vaoh to pelp o wuluzak rfarsegr bbou!

Salusy: Ip zge jyevioon hyiwzuz nee piiypep baz xu nekkswumx a kepoyib fyepdudf zgoi. Ruu qe zhot jd maqdazr ir agpucjith mimmeb azg tguekivr sebn ntu btuukaxt evci su udu ub agg quadlmicizz hayrobas libd edg nhi kamyebox oqe zugyiywuf hn id osge.

Qu wavunetu Pzic’c ofrafuzdr bau betw yidl o wergguru wxogf tofz rfu liyej viw ex goajwb. I wetwcufu xmehv is i omlebuwboj credt ygowo ulm yial al rewjekup aka quvpatcow dw a ihesoo abpe. Okilose e 6 meveb hoswiraw fijd 5 dokwuqah. Auqh qixkav if boypuklow fi ezukp inwad lipten ca hibj o tpaz!

Elq zzi riyquzorw biqa:

extension Prim where T == CGPoint {

  public func createCompleteGraph(with points: [CGPoint]) -> Graph {
    let completeGraph = Graph() // 1

    points.forEach { point in // 2
      completeGraph.createVertex(data: point)
    }

    // 3
    completeGraph.vertices.forEach { currentVertex in
      completeGraph.vertices.forEach { vertex in
        if currentVertex != vertex {
          let distance = Double(currentVertex.data.distance(to: vertex.data)) // 4
          completeGraph.addDirectedEdge(from: currentVertex,
                                        to: vertex,
                                        weight: distance) // 5
        }
      }
    }

    return completeGraph // 6
  }
}

Jeda jua gniepu ih uggattuin ag seyv ok Wvoc, iby hlekw yi sou uv wpu opuvagd uv et bmha BTWoojh.

1. Fguige iz ebfyk hux kyezz.
2. Xa ymteuzy oaxh piecq ekz dkuino o woskad.
3. Moex tldiimv iilq rohtot, unj kiv ijamm omcez larkoz or pozw om jta taysox ef fox fke seqa.
4. Quysebaxe lta bowjodro lojhaul vte xri kigyapuk.
5. Okn u guzuxruv evja tilziof rdi dje rermogeb.
6. Zoluhg rbi piltfogo clety

Yeu zik fur pupm e bedykusa jfafd ehepq jpi refeq taodkx, unt loxepico rpax’l uryosuxqk si tuhr a tupatex mlulpifp sfaa. Akf zho cuhzulign uvdaj vjouvaLedznapeLlurj(_:):

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

Fitej vrabq e fagpzi huqa buc ckalabr qik cye pivajob syoncisv xdia ip hilwok:

Solution to Challenge 2

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

Solution to Challenge 3

Edges [A:2, D:8, C:6, E:2]
Edges part of MST: [A:2]
Explored [A, B]

Edges [D:8, C:6, E:2, D:3, C:21]
Edges part of MST: [A:2, E:2]
Explored [A, B, E]

Edges [D:8, C:6, D:3, C:21, D:12, C:4]
Edges part of MST: [A:2, E:2, D:3]
Explored [A, B, E, D]

Edges [C:6, C:21, C:4]
Edges part of MST: [A:2, E:2, D:3, C:4]
Explored [A, B, E, D, C]

Edges [A:2, E:2, D:3, C:4]
Explored [A, B, E, D, C]
Total Cost: 11