@Param $G(V, E, W)$, a weighted, undirected graph

@Returns $F$, A subgraph of $G$ that contains all vertices of $G$ and minimizes the sum of its weights:

$$ \sum_ {e\in F.\texttt{Edges}}W(e) $$

where $W:E \to \R$ is the weight function.

$\star$ Def. Safe Edge / Crossing the Cut

An undirected edge $uv$ from $G\backslash F$ is safe with respect to intermediate spanning tree $F$ if

1. $uv$ is the edge with minimum weight in $G\backslash F$
2. $uv$ has exactly 1 vertex in some component of $F$

This is the edge that’s **crossing the cut** and the greedy choice for Prim’s and Kruskal’s.

@Hint If both $u$ and $v$ are in $F$, then we get a cycle. If neither are in $F$, then $uv$ is not connected to $F$

The Only MST Algorithm

function GenericMST(G: Graph) -> Set<Edges>:
	F = {} // empty tree or empty set

	while F is not a spanning tree:
			add a safe edge to F

	return F

We just need to fill in the details for:

1. The while loop condition; what does it mean for $F$ to not be a spanning tree?
2. Classifying a safe edge. This might not be a direct translation of the definition above.

$\star$ Prim’s & Kruskal’s

Both Prim’s and Kruskal’s MST have a nice 1 liner describing the entire algorithm.

Prim: Keep adding minimum weight safe edges to $F$

Kruskal: Scan the edges by increasing weight. If the current edge is safe, add it to $F$