This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
Come up with a graph \(G\) with \(n=10\) nodes and at least \(m\ge 15\) edges that leads to the worst-case performance for Boruvka's algorithm. That is, it causes the algorithm to do the maximum number of "phases" or steps to complete. Show each step of the algortihm, and the MST that results.
Then come up with a different graph \(H\) with \(n=10\) nodes and at least \(m\ge 15\) edges that leads to the best-case performance for Boruvka's algorithm. Again, show the result from each step of the algorithm, and the final MST that you end up with.