Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

45. Prim’s Algorithm Challenges
Written by Vincent Ngo

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

Challenge 1: Minimum spanning tree of points

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

20 20 15 15 10 10 5 5 0 (4,0) (10,1) (18,7) (5,14) (6,16) (3,17)

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?

6 8 8 1 5 6 7 7 2 X 9 7 1 8 1 8

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.

I J R E H 37 3 5 9 7 8 2 57

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.

extension CGPoint: Hashable {
  public func hash(into hasher: inout Hasher) {
    hasher.combine(x)
    hasher.combine(y)
  }
}
Suproyha xuhxooy d7 uyd d3 q6 r9 F H O S= O + L 6 2 4 Z= A + W 4 9 gussuksu = (f7.x - z9.l) + (p2.w - q8.v) 5 2

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

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
  }
}
public func produceMinimumSpanningTree(with points: [CGPoint]) ->
                                      (cost: Double, mst: Graph) {
  let completeGraph = createCompleteGraph(with: points)
  return produceMinimumSpanningTree(for: completeGraph)
}
19 40 48 76 56 64 1 4 5 (8,5) (65,3) (54,2) (8,06) (4,76) (6,54) 33 57 19 95 30 70 9 9 4 (0,9) (81,6) (66,2) (9,14) (6,89) (9,78)

Solution to Challenge 2

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

Solution to Challenge 3

A C D E B 21 2 6 8 2 3 4 12

H G U 55 5 7 1 9 5 0 41 U C

Edges [A:2, D:8, C:6, E:2]
Edges part of MST: [A:2]
Explored [A, B]
77 01 X 2 5 C 0 6 4 2 A O B

Edges [D:8, C:6, E:2, D:3, C:21]
Edges part of MST: [A:2, E:2]
Explored [A, B, E]
P N 42 8 9 8 7 0 7 29 E U T

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]
67 3 1 7 5 4 4 48 U E Y K C

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]
6 9 9 6 U K A Q Z

Edges [A:2, E:2, D:3, C:4]
Explored [A, B, E, D, C]
Total Cost: 11
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now