The aim of minimum connector problems is to find the spanning tree of minimum weight.
- 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.
- 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.
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
- Difficulty of checking whether arcs form cycles makes it slow and hard to program.
See the other D1 notes:
- Sorting algorithms
- Packing algorithms
- Graphs and networks
- Minimum connector problems
- The shortest path
- Route inspection
- The travelling salesman problem
- Linear programming
- The simplex algorithm