MST

Work in Progress

Summary

MST algorithms

	Time Complexity	Constraint	Type of Graph ADT
kruskal’s algorithm			EL
prim’s algorithm		undirected graph	AL
boruvka’s algorithm		TODO	TODO

boruvka’s algorithm is not in the cs2040s syllabus

MST related problems

maximum spanning tree - negate all weights
minimum spanning forest - early termination, kruskal’s invariant
minimum tree with k verticies - early termination, prim’s invariant
kth minimum spanning tree - NP hard

Cayley’s formula

number of spanning trees in a complete graph/among n verticies

Concept

Minimum spanning tree(MST)

usually on U/W graphs
subtree that spans all verticies with the smallest total weight
not necessarily unique
6 vertex graph

Cycle reduction

eliminate the largest weight in each cycle
destructive method

Cut vertex construction

choose the bridge edge with the lowest weight
constructive method