Algorithms On Networks

Question 1

Identify 2 algorithms to create a minimum spanning tree

Answer 1

1. Kruskal’s algorithm

2. Primm’s algorithm

Question 2

What are the 4 steps to do Kruskal’s algorithm?

Answer 2

1. Sort all arcs into ascending order of weight
2. Select the arc of least weight to start the tree
3. Consider the next arc of least arc that doesn’t form a cycle
4. Repeat step 3 until all vertices are connected

Question 3

What are the 3 steps to do Prim’s algorithm?

Answer 3

1. Choose any vertex to start at
2. Select the arc of least weight that joins a vertex that is already in the tree to a vertex that isn’t in the tree
3. Repeat step 2 until all vertices are connected

Question 4

Identify 3 differences between Kruscal’s and Prim’s algorithm?

Answer 4

1. Prim can start at any point
2. Prim can be used on a matrix
3. Kruscal requires an ordered list of arcs

Question 5

Why do you not need to check for cycles when using Prim’s algorithm?

Answer 5

In Prim you add a new node to what you already have and are not adding arcs. Therefore if you add a new node each time you can’t make a cycle