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

A Vertex requires its elements to be Hashable. The starter project provides an extension to CGPoint:

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

Every vertex has an associated CGPoint. To form an edge to another vertex (CGPoint), you need to calculate the distance between points:

Add the following code below:

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

• distanceSquared(_:) calculates the hypotenuse’s squared value by adding the squared distance of the opposite and adjacent sides.
• distance(_:) returns the hypotenuse by taking the square root of the distance squared.

Now that you’ve established a way to calculate the distance between two points, you have all the information you need to form a minimum spanning tree!

Recall: In the previous chapter you learned how to construct a minimum spanning tree. You do this by picking an arbitrary vertex and greedily pick the cheapest edge to one of its neighboring vertices till all the vertices are connected by an edge.

To leverage Prim’s algorithm you must form a complete graph with the given set of points. A complete graph is a undirected graph where all pair of vertices are connected by a unique edge. Imagine a 5 sided pentagon with 5 vertices. Each vertex is connected to every other vertex to form a star!

Add the following code:

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

Here you create an extension as part of Prim, and check to see if the element is of type CGPoint.

1. Create an empty new graph.
2. Go through each point and create a vertex.
3. Loop through each vertex, and for every other vertex as long as the vertex is not the same.
4. Calculate the distance between the two vertices.
5. Add a directed edge between the two vertices.
6. Return the complete graph

You can now form a complete graph using the given points, and leverage prim’s algorithm to form a minimum spanning tree. Add the following after createCompleteGraph(_:):

public func produceMinimumSpanningTree(with points: [CGPoint]) ->
                                      (cost: Double, mst: Graph) {
  let completeGraph = createCompleteGraph(with: points)
  return produceMinimumSpanningTree(for: completeGraph)
}

Below shows a sample data set showing how the minimum spanning tree is formed:

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