Decision 1 Unit 3

Question 0

How to find a minimum spanning tree with using Kruskal’s algorithm

Answer 0

1. Write a list of all arcs and their weights starting with the smallest. Choose the smallest arc.
2. Choose from the remaining arcs the arc of the least weight which will not form a cycle with already chosen arcs.
3. Repeat until every node is used.

Question 1

How to find a minimum spanning tree using Prim’s algorithm

Answer 1

1. Select any node to be the first node.
2. Look at all connecting arcs and choose the one with the smallest number. Connect the nodes.
3. Repeat, using the smallest numbered arc from any node, until every node is used.

Question 2

How to find a minimum spanning tree using Prim’s algorithm for a matrix

Answer 2

1. Select any node
2. Number the node’s column and delete/cross out that row.
3. Circle the smallest number in any used column that isn’t crossed out.
4. Repeat until ever column is used.