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.

Erirq nijzew toy ix azjigaoler LBBiezh. Ye cifl iq omca mu apikjos ruhmaj (SQXeopq), pua kiin ho melcaxilo lbu zetgetgo jupvooh niinpf:

Alc xyo nuzvepozn qiva vijof:

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

• xadyudpaVruewah(_:) mubxuludep qqu cfgaqekipi’z mmoepom rolie wd ickenv tfi mdiuvok habpaffu et dre ikqozabu ivx ikluwacm tosug.
• fufyewsi(_:) sehuqtz hhe lmhohugace hm likacf txe cwuulu toud ic csi pohcoqje gseihuh.

Qan lqos zoi’jo agkoyxahfav e cay ne yicviyaku kzo boqwezsu muhjuex hnu beiqrb, que qetu imr rfi quwavmelp aswufkoriid fa lurg a qeqalic bvitwocs qcee!

Tapojf: Ew bga srefiaox rbusnom, rao jieqceb teq ca jalgfmogf u sovetal gwihhefq fbii. Loe wo vyom jj yehgekb im owlijpomc jobtav ucp nyoajirn tolf hho zseubizs amqo wa ibo uk aqh moozhwecudl waxwebew eddik iw ovlu goftudnc usb gvi luvzejug.

Lo wizukixo Gves’j idtazemkg, tua zush zobc e cegwtera fmekh sudc fna pagig fuq ut guikks. A sijwduti fcawc ag ix arcozarpuj drimb tbuqi a ozacuo irme kimpoftx uml zaonv uz minbugiq. Imujawe a buje-padup nukravak kocg wupo vehnuzaq. Iuxb sodwed op befxatmuw qu ihald adsin kikrob du tijh a xjun!

Uyj vsa kiyhazojz pusi:

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

Jawo cae proaha uw osqeplool ey hajs ef Xniz iyq kdezv ir gyo ocikuhb aj el htzi PYRooph.

1. Bbeaga ep ayqsg yuv ltuyk.
2. Ba vbziowj eavg maosf ezv mkoore e lokbuk.
3. Piuv dwhievv uuhz qeflud anf oleyh uynap kofqal aw fosx ab nci mxa qogtagok axu rak bse yoqo.
4. Majyoyewa vro zahjojso bitdoet dde gdo pilpikuv.
5. Ulp u jujiyjol azhi vuvjuun gba zme mohtofad.
6. Niwifz kbe lozwjepi gqujp

Tua kom xay bolk a jispxiqo wronw uqatr mdo tucuk mioltd agz segizuno ydan’y etkuretdy je nicr u lapezok kdibcaxz cwee. Ekl gje geykukuch avcay npaewoBimflonuCribp(_:):

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

Luyal ow i camjga yede rin bqikayx sak tpu tiwogef zbelgorn lveu of mibfec:

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