• Revision:Minimum Connector Problems

TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > Minimum Connector Problems



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

Contents

Prim's algorithm

  1. Select any node the be the first node of the minimum spanning tree, T.
  2. 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.
  3. 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

  1. Select any node to be the first node of T
  2. Circle the new node of T in the top row, and cross out the row corresponding to this new node.
  3. 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.
  4. Repeat until T contains every node.

Example

Kruskal's algorithm

For a graph with n nodes.

  1. Choose the arc of least weight
  2. From the remaining arcs, choose the one of least weight that does not form a cycle with already chosen arcs
  3. 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:

  1. Algorithms
  2. Sorting algorithms
  3. Packing algorithms
  4. Graphs and networks
  5. Minimum connector problems
  6. The shortest path
  7. Route inspection
  8. The travelling salesman problem
  9. Linear programming
  10. The simplex algorithm

Comments

Try Learn together, TSR's study area

35,697
revision notes

39,308
mindmaps

39,714
crosswords

15,204
quizzes

create
a study planner

thousands
of discussions


Poll
How are you feeling about doing A-levels?
Study resources

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE