Revision - Minimum Connector Problems

The aim of minimum connector problems is to find the spanning tree of minimum weight.

Prim's algorithm

  • Select any node the be the first node of the minimum spanning tree, T.
  • Consider the arcs connecting the nodes currently in T to those outside of T. Pick the one of minimum weight. Add this arc and node to T.
  • Repeat step 2 until all nodes are within T.

Advantages

  • Simple

Disadvantages

  • Time taken to check for smallest weight arc makes it slow for large numbers of nodes
  • Difficult to program, though it can be programmed in matrix form.

Matrix formulation of Prim's algorithm

  • Select any node to be the first node of T
  • Circle the new node of T in the top row, and cross out the row corresponding to this new node.
  • Find the smallest weight left in the columns with circled headings. Circle this weight. Then choose the node whose weight the row is in to join T.
  • Repeat until T contains every node.

Example

Kruskal's algorithm

For a graph with n nodes.

  • Choose the arc of least weight
  • From the remaining arcs, choose the one of least weight that does not form a cycle with already chosen arcs
  • Repeat until n-1 arcs have been chosen

Advantages

  • Simple

Disadvantages

  • Difficulty of checking whether arcs form cycles makes it slow and hard to program.

Also See

See the other D1 notes: