Minimum Connector

The minimum connector problem gives a way to join every vertex in a network so that the total weight of the edges used is minimised.

Figure 1: Roads connecting towns in southern England

The towns in southern England are to be connected with a new fibre-optic cable system. The hub of the system is to be in London. What is the minimum length of cable needed to connect the towns?

There are two algorithms that we can use to solve this type of problem:

  1. Kruskal’s algorithm
  2. Prim’s algorithm

We will look at each of these individually and see the benefits of Prim’s algorithm for computational purposes.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.