> For the complete documentation index, see [llms.txt](https://emory.gitbook.io/dsa-java/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emory.gitbook.io/dsa-java/minimum-spanning-trees/abstraction.md).

# 8.1. Abstraction

## 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?

{% embed url="<https://www.slideshare.net/jchoi7s/minimum-spanning-trees-238996840>" %}

## Spanning Tree

Let us define the [`SpanningTree`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/graph/span/SpanningTree.java) class under the [`graph.span`](https://github.com/emory-courses/dsa-java/tree/master/src/main/java/edu/emory/cs/graph/span) package:

```java
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`](https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/lang/Comparable.html) interface.
* `L2`: contains all edges in this spanning tree.
* `L3`: contains the total weight of this spanning tree.

We then define getters and setters:

```java
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:

```java
@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`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/graph/span/MST.java) that is inherited by all minimum spanning tree algorithms:

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

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