Greedy Approach

Keep adding low-cost edges as long as no cycle is made.

Didn't work for matching. Works here.


\begin{algorithm} {Generic-MST}{G} T \= \emptyset \ \begin{FOR} {i \= 1 \TO \... ...{e\in C} w(e) \ T \= T \cup \{ e^* \} \end{FOR} \ \RETURN T \end{algorithm}

next up previous
Next: Cuts Up: FINDING MINIMUM SPANNING TREES Previous: Design Ideas