5.3 Prims Algorithm Flashcards
1
Q
What is a (minimum) spanning tree of a graph
A
- Spanning tree = Tree with all vertices of a graph
- Minimum spanning tree = minimum total weight
2
Q
What is a minimum Steiner tree
A
- Introducing phantom vertices to decrease total weight
3
Q
What is the core idea behind Prim’s algorithm
A
Since includes all vertices working greedily produces an optimal result
4
Q
What is the formal mathematical definition of Prim’s algorithm
A
5
Q
Why does Prim’s algorithm work
A
6
Q
Prim’s algorithm proof exchange argument
A
7
Q
Prim’s algorithm psuedocode and time complexity
A
Can be improved to O(|E| + Vlog|V|) with Fibonacci heap
