# 45 Prim’s Algorithm Challenges Written by Vincent Ngo

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