Minimum Spanning Trees

Spanning Tree

• Binary search tree.

Exercise

• Source codes.

• Unit tests.

• Create a package cs323.graph.

• Download the Graph and Edge classes and put it under graph.

• Create a package cs323.graph.span.

• Download the SpanningTree class and put it under span.

• Download the MSTAlgorithm interface and put it under span.

Minimum Spanning Tree

• Create classes MSTPrim, MSTKruskal, and MSTEdmonds under span.
• Inherit the MSTAlgorithm interface.
• Override the getMinimumSpanningTree method in each class by implementing Prim's, Kruskal's, and Chu–Liu-Edmonds' algorithms, respectively.
• @param graph a graph containing at least one spanning tree.
• @return a minimum spanning tree.

Prim's Algorithm

1. Pick a vertex.
2. Put the picked vertex to a set and add all its incoming edges to a priority queue using their weights.
3. Remove the minimum edge in the queue and check if the set contains the source of this edge.
4. If the set contains the source, add the edge to a tree.
5. If all edges in the tree form a spanning tree, return the tree.
6. Otherwise, go to #2 by picking the source of the edge.
7. Go to #3 unless the queue is empty.

Kruskal's Algorithm

1. Create a forest in which each set consists of each vertex in the graph.
2. Create a priority queue containing all edges in the graph.
3. Remove the minimum edge in the queue and check if the source and the target belong to the same set in the forest.
4. If the source and the target do not belong to the same set, add the edge to a tree and merge the source and the target sets.
5. If all edges in the tree form a spanning tree, return the tree.
6. Go to #3 unless the queue is empty.

Chu–Liu-Edmonds’ Algorithm

1. Initially, every vertex is considered a tree.
2. For each tree, keep 1 incoming edge with the minimum weight.
3. If there is no cycle, go to #5.
4. If there is a cycle, merge trees with the cycle into one and update scores for all incoming edges to this tree, and goto #2.
5. For each vertex in the tree, add the weight of its outgoing edge to its incoming edges not in the tree. Break all cycles by removing edges that cause multiple parents.

Quiz 6

• 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.

Quiz 7

• What is the worst-case complexity of Chu–Liu-Edmonds’ Algorithm when V is the number of vertices and E is the number of edges in a graph? Explain how you come up with this complexity.