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