## Data Structures & Algorithms in Swift

#### Before You Begin

Section 0: 6 chapters

#### Section I: Introduction

Section 1: 3 chapters

#### Section II: Elementary Data Structures

Section 2: 6 chapters

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

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