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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://emory.gitbook.io/dsa-java/minimum-spanning-trees/abstraction.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.