Network algorithms 1. Minimum spanning trees

Question 1

What is a minimum connector or minimum spanning tree?

Answer 1

Starting with a given network, a minimum connector, or a minimum spanning tree, is the least weight connected graph which includes every vertex.

Question 2

What are the 2 types of algorithm used to find a minimum spanning tree, and applied to what?

Answer 2

Kruskal’s algorithm applied to the network and Prim’s algorithm applied to the network or to the network table.

Question 3

How can you use Kruskal’s algorithm to find a minimum connector in a network?

Answer 3

1. Select the shortest edge in a network
2. Select the next shortest edge which does not create a cycle
3. Repeat step 2 until all vertices have been connected

Question 4

How can you use Prim’s algorithm to find a minimum connector in a network?

Answer 4

1. Start at any vertex
2. Select the shortest edge connected to that vertex
3. Select the shortest edge connected to any vertex not connected
4. Repeat step 3 until all vertices have been connected

Question 5

How do you use Prim’s algorithm in a tabular format?

Answer 5

Say you build a tree starting from F (will specify in question)

• Delete the row corresponding to F, mark column F with a (1)
• Look down column F and find smallest value not crossed out. Put box round it (say this is row D)
• Delete row D. Label column D with a 2
• Look down column D and find smallest value not crossed out. Put box round it (say this is row C)

-Delete row C …

Repeat until all vertices have been connected

Question 6

What is the complexity of Kruskals and Prims algorithm?

Answer 6

Quadratic complexity for both - O(n^2)