Minimum Spanning Trees

Reading

• Minimum spanning tree.
• Prim's algorithm.
• Kruskal's algorithm.
• Chu/Liu/Edmonds' algorithm.

Exercise

• Source codes.
• Unit tests.

Quiz

• Give a graph where Prim's and Kruskal's algorithms generate different kinds of minimum spanning trees. Explain how these trees are generated. If you cannot find an example, explain why these algorithms always generate the same minimum spanning tree given any graph.
• Write a report about your findings and save it as quiz6.pdf.