Home iOS & Swift Books Data Structures & Algorithms in Swift

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.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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.

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

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

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

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.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

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 raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.