8.1. Abstraction

This section discusses spanning trees in a graph.

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

Let us define the SpanningTree class under the graph.span package:

public class SpanningTree implements Comparable<SpanningTree> {
    private final List<Edge> edges;
    private double total_weight;

    public SpanningTree() {
        edges = new ArrayList<>();
    }

    public SpanningTree(SpanningTree tree) {
        edges = new ArrayList<>(tree.getEdges());
        total_weight = tree.getTotalWeight();
    }
}

• L1: inherits the Comparable interface.

• L2: contains all edges in this spanning tree.

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

We then define getters and setters:

public List<Edge> getEdges() { return edges; }
public double getTotalWeight() { return total_weight; }
public int size() { return edges.size(); }

public void addEdge(Edge edge) {
    edges.add(edge);
    total_weight += edge.getWeight();
}

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

@Override
public int compareTo(SpanningTree tree) {
    double diff = total_weight - tree.total_weight;
    if (diff > 0) return 1;
    else if (diff < 0) return -1;
    else return 0;
}

MST

Let us create the interface MST that is inherited by all minimum spanning tree algorithms:

public interface MST {
    public SpanningTree getMinimumSpanningTree(Graph graph);
}

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