5.3 Prims Algorithm

Question 1

What is a (minimum) spanning tree of a graph

Answer 1

• Spanning tree = Tree with all vertices of a graph
• Minimum spanning tree = minimum total weight

Question 2

What is a minimum Steiner tree

Answer 2

• Introducing phantom vertices to decrease total weight

Question 3

What is the core idea behind Prim’s algorithm

Answer 3

Since includes all vertices working greedily produces an optimal result

Question 4

What is the formal mathematical definition of Prim’s algorithm

Answer 4

Question 5

Why does Prim’s algorithm work

Answer 5

Question 6

Prim’s algorithm proof exchange argument

Answer 6

Question 7

Prim’s algorithm psuedocode and time complexity

Answer 7

Can be improved to O(|E| + Vlog|V|) with Fibonacci heap