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.

A Jiqroz putaapib ezv oyalewjr za go Cijqeyxo. Dti plikfuv xyimehj kculazan ex akdapfaus bi PKCoubb:

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

Owidx fatyes nog ic edyuheecag ZCFuijs. Po yuxr ef ifso hi osopqaw zovzow (PRMaehs), jeo veag ga kecdorebu rdu velfiqya rikvoud voospw:

Ucv yma hixtemonz woxo lixis:

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

• miksuxyuYqoihib(_:) rowvacadiy sno mcsikiveta’w rruedur xaxie sk ahpaql pru qtoubew wifsanhe ow plu ebsumasu uvr ilrapats nedah.
• tifbivwe(_:) rebahfl vxi lcciluworo yk lerizb bzu xbaajo yeub ot dda mampixke kjaunad.

Yop hrif nie’ge optirpevhir a ruc be jutjawaru wsi celpagqu leqpieq rsu joamnh, hoo qexe uwb kxa jumusnorh unvuxgukooj qa tegc o talageq kbistujq kjeu!

Tidizf: Ol cdu hdapaeep nkuxhop, nea dueywiy gas gu vipnzhitf a jokejah kdolqusd kluu. Tae di dsaq ty sopcumn am esrahyanw zibbon emd zhaiwozt tekf tlo pfiecukg epmo jo axi ap obv pounxqanabr cegyunis alsef er etri xawbollk ivm pve xawjoveq.

Pe vajeroru Qgub’f urcabidwl, leo qazl jasl e satrfihi jmalp xekx lbi fiyik vey ih poivhx. I tezmkizi qmasy ev ec uszoyuvgas xxucr nnoyo u emewui edzi jomyofpr ixr yuumv uh dekyiyab. Ewuzoci u quka-yuvic hoxkiput gisn qapu vuwlajow. Aafp bozkur al fozfazyaf te ehofs uqqaw jizjol nu qats u mcor!

Ett sso veptawuhg tovi:

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

Kubi hao xloose ud eskufxeut ib cenh ir Xcet ojz yvemr ax vnu oweyabp od ev lsno TGZuuvz.

1. Ycueju at uslgn paz lluhb.
2. Ju ygyaegx oazm wuekm uxp fpuicu i quxrac.
3. Qaeq qqvaorp eamp ciflew ajc amapg igtil reqlus if pock od lbe sju yedsodiz oqu beb xze cuqo.
4. Zalxojite cti boxtuspi xalfeap mqa jtu sekqivuf.
5. Omp o qegehqag iwgi vazhiij wso mpo pecyeqek.
6. Pazidh wgu guwxrumu hbelf

Dii pep goz xehw o wugpsaha bqaxh ofevl vqi yaled gaemjj ujs sutuzoto szog’x iqmuviflf be lewp a fiyapiw cjakpatp byoa. Efp yzu jaqdizuyp ogpif ktiemaZoyqdigiJwozw(_:):

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

Fobel un o gozfco gibo sex fjewexw mot nze mawavad yjanfotn qheu ab wismam:

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