This section discusses Prim's Algorithm that finds a minimum spanning tree in an undirected graph.
public class MSTPrim implements MST {
@Override
public SpanningTree getMinimumSpanningTree(Graph graph) {
PriorityQueue<Edge> queue = new PriorityQueue<>();
SpanningTree tree = new SpanningTree();
Set<Integer> visited = new HashSet<>();
Edge edge;
add(queue, visited, graph, 0);
while (!queue.isEmpty()) {
edge = queue.poll();
if (!visited.contains(edge.getSource())) {
tree.addEdge(edge);
if (tree.size() + 1 == graph.size()) break;
add(queue, visited, graph, edge.getSource());
}
}
return tree;
}
}This section discusses Chu-Liu-Edmonds' Algorithm that finds a MST in a directed graph.
private void add(PriorityQueue<Edge> queue, Set<Integer> visited, Graph graph, int target) {
visited.add(target);
for (Edge edge : graph.getIncomingEdges(target)) {
if (!visited.contains(edge.getSource()))
queue.add(edge);
}
}private void add(PriorityQueue<Edge> queue, Set<Integer> visited, Graph graph, int target) {
visited.add(target);
graph.getIncomingEdges(target).stream().
filter(edge -> !visited.contains(edge.getSource())).
collect(Collectors.toCollection(() -> queue));
}This section discusses Kruskal's Algorithm that finds a minimum spanning tree in an undirected graph.
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();
}
}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();
}@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;
}public interface MST {
public SpanningTree getMinimumSpanningTree(Graph graph);
}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;
}
}0 -> 10 <- 20 <- 10 -> 20 <-10 <- 2