Recap graph definitions, properties, etc.
Spanning tree definition
Sub-graph tree that contains all vertices of the graph
Minimum spanning tree problem definition
Input
Output
Greedy algorithm
- Make a local solution and continue recursively to a sub-problem without changing the solution Binary search is a simple example of a greedy algorithm Hoffman code is another, a more complex one
Dynamic programming solution
- Recursively analyze all possible options
Greedy choice property
Exists an optimal solution that includes that choice, i.e. each choice does not affect the possibility of getting an optimal solution
Cut, Cut-set definition
Edge in a cut-set belongs to some MST lemma
Edge collapse/contraction definition
Generic solution
Correctness of MST-Generic lemma
Prim’s algorithm
Complexity of this algorithm is (using Fibonacci Heap):
for init times - extractMin -
- extractMin -
times - decreaseKey -
amortized All in all,
- decreaseKey -
Kruskal’s algorithm
Complexity of this algorithm is:
for initialization for sort (or something else), note that for many graphs for find and union All in all,