Contents

1. Abstraction

2. Prim's Algorithm

3. Kruskal's Algorithm

4. Chu-Liu-Edmonds' Algorithm

5. Quiz

6. Homework

References

• Prim's Algorithm

• Kruskal's Algorithm

• Chu-Liu-Edmonds' Algorithm

Kruskal's algorithm finds a minimum spanning tree by finding the minimum edge among subtrees.

Let us create the MSTKruskal class inheriting the MST interface:

public class MSTKruskal implements MST {
    @Override
    public SpanningTree getMinimumSpanningTree(Graph graph) {
        PriorityQueue<Edge> queue = new PriorityQueue<>(graph.getAllEdges());
        DisjointSet forest = new DisjointSet(graph.size());
        SpanningTree tree = new SpanningTree();

        while (!queue.isEmpty()) {
            Edge edge = queue.poll();

            if (!forest.inSameSet(edge.getTarget(), edge.getSource())) {
                tree.addEdge(edge);
                if (tree.size() + 1 == graph.size()) break;
                forest.union(edge.getTarget(), edge.getSource());
            }
        }

        return tree;
    }
}

• L4: adds all edges to the priority queue.

• L5: creates a forest where each vertex is considered a separate tree.

• L8: iterates through all edges:

  • L11: if the target and source vertices in the edge are not in the same tree.

  • L13: if the tree contains v-1 number of edges, a spanning tree is found.

  • L14: merges the target and source vertices into the same tree.

Finding All Minimum Spanning Trees

Your task is to write a program that finds all minimum spanning trees given an undirected graph.

Tasks

• Create a class called that inherits the interface.

• Override the getMinimumSpanningTrees() method.

• Feel free to use any classes in the package without modifying.

• Write a report that explains the logic and worst-case complexity of your program and save it as hw3.pdf.

Extra Credit

• Create an interesting graph and submit both the source code (as in ) and the diagram representing your graph (up to 1 point).

Notes

• Test your code with graphs consisting of zero to many spanning trees.

• Your output must include only minimum spanning trees.

• Your output should not include redundant trees. For example, if there are three vertices, 0, 1, and 2, {0 -> 1, 0 -> 2} is considered the same as {0 -> 1, 0 <- 2} or {0 <- 1, 0 -> 2} or {0 <-1, 0 <- 2}.

Overview

A spanning tree in a graph is a tree that contains all vertices in the graphs as its nodes. A minimum spanning tree is a spanning tree whose sum of all edge weights is the minimum among all the other spanning trees in the graph.

Can a graph have more than one minimum spanning tree?

Spanning Tree

• L2: contains all edges in this spanning tree.

• L3: contains the total weight of this spanning tree.

We then define getters and setters:

• L3: the size of the spanning tree is determined by the number of edges.

Finally, we override the compareTo() method that makes the comparison to another spanning tree by the total weight:

MST

• L2: an abstract method that takes a graph and returns a minimum spanning tree.

Prim's algorithm finds a minimum spanning tree by finding the minimum edge among all incoming edges of visited vertices.

Let us define the class inheriting the MST interface:

• L9: adds the vertex 0 to the visited set and its incoming edges to the queue.

• L11: iterates through all incoming edges:

  • L14: if the visited set contains the source vertex, adding the edge would create a cycle.

  • L16: if the tree contains v-1 number of edges, a spanning tree is found.

  • L17: repeats the process by adding the source of the edge.

The add() method can be defined as follows:

• L4-7: adds all incoming edges that have not been visited to the queue.

What is the worst-case complexity of Prim's Algorithm?

Complexity

Explain the worst-case complexities of the following algorithms in terms of V and E according to our implementations:

• Prim's algorithm

• Kruskal's algorithm

• Chu-Liu-Edmonds' algorithm

Comparison

Provide an example of a graph where Prim's and Kruskal's algorithms find different minimum spanning trees from the same graph and explain how these trees are found. If you cannot find an example, explain why these algorithms always find the same minimum spanning tree given the same graph.

Report

Write a report quiz7.pdf that includes the complexity and comparison analyses.

Chu-Liu-Edmonds' Algorithm takes the following steps to find a MST in a directed graph:

1. Initially, every vertex is considered a subtree.

2. For each subtree, keep 1 incoming edge with the minimum weight.

3. If there is no cycle, go to #5.

4. If there is a cycle,

   1. Merge subtrees with the cycle into one and update scores for all incoming edges to this merged subtree, and goto #2.

   2. For each vertex in the subtree, add the weight of its outgoing edge chain to its incoming edges not in the subtree.

5. Break all cycles by removing edges that cause multiple parents.

The following demonstrates how Chu-Liu-Edmonds' Algorithm find a minimum spanning tree:

What is the logic behind updating the edge weights related to the cycles?

The following explains the weight updates in details: