# Minimum Spanning Tree ## Solution - Grow a spanning tree by finding the edges that are _safe_ iteratively. - A _cut_ - An edge _crosses_ the cut - An _light edge_ crossing the cut - _safe edge_ = adding this edge to $A$ ==maintains the property== that $A \subseteq T$, e.g. no cycle, low weight. - When the algorithm is running $G_A$ will be a forest, in which each connected component is a tree. As the algorithm runs, light edges crossing each connected components are picked to form the spanning tree. ```python def MST(G, w) A = set() # some set while A is not spanning tree: find an edge (u, v) that is safe for A A.add( (u, v) ) return A ``` - Based on the generic method, algorithms of [[kruskal|Kruskal]] and [[prim|Prim]] each uses a specific rule to determine a safe edge. - Kruskal: $A$ is a forest with all vertices, safe edge is a lowest-weight edge in the graph that connects two distinct components. - Prim: $A$ is a single tree, safe edge is a lowest-weight edge connecting the tree to a vertex not in the tree. - Both takes $O(E\lg V)$ time (using bin-heap for Prim)