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

Post a Comment

You must be logged in to post a comment.