## Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

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

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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