import java.util.Queue;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;
class PrimMinimumSpanningTreeLazy {
private boolean[] visited;
private Queue mst;
private Queue pq;
private double weight;
public PrimMinimumSpanningTreeLazy(EdgeWeightedGraph G) {
this.visited = new boolean[G.V()];
this.mst = new ArrayDeque<>();
this.pq = new PriorityQueue<>();
visit(G, 0);
while (!pq.isEmpty() && mst.size() < G.V()-1) {
Edge edge = pq.poll();
int v = edge.either(), w = edge.other(v);
if(visited[v] && visited[w]) {
continue;
}
mst.add(edge);
this.weight += edge.weight();
if(!visited[v]) {
visit(G, v);
}
if(!visited[w]) {
visit(G, w);
}
}
}
public Iterable edges() {
return mst;
}
public double weight() {
return weight;
}
private void visit(EdgeWeightedGraph G, int v) {
visited[v] = true;
for(Edge edge : G.adj(v)) {
if(!visited[edge.either()] || !visited[edge.other(edge.either())]) {
pq.add(edge);
}
}
}
static class EdgeWeightedGraph {
private final int V;
private final List[] adj;
public EdgeWeightedGraph(int V) {
this.V = V;
adj = new ArrayList[V];
for (int v = 0; v < V; v++) {
adj[v] = new ArrayList<>();
}
}
public void addEdge(Edge e) {
int v = e.either(), w = e.other(v);
adj[v].add(e);
adj[w].add(e);
}
public Iterable adj(int v) {
return adj[v];
}
Iterable edges() {
Set allEdges = new HashSet<>();
for(List list : adj) {
allEdges.addAll(list);
}
return allEdges;
}
public int V() {
return V;
}
int E() {
int edges = 0;
for(List edge : adj) {
edges += edge.size();
}
return edges/2;
}
}
static class Edge implements Comparable {
private final int v;
private final int w;
private final double weight;
Edge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
int either() {
return v;
}
int other(int v) {
if(this.v == v) {
return w;
}
return v;
}
public int compareTo(Edge that) {
if(this.weight < that.weight) {
return -1;
} else if(this.weight > that.weight) {
return 1;
}
return 0;
}
double weight() {
return weight;
}
public String toString() {
return "Edge: " + v + "-" + w + ", Weight: " + weight;
}
}
private static EdgeWeightedGraph dummyGraph() {
String[][] input = {
{"0", "7", "0.16"},
{"2", "3", "0.17"},
{"1", "7", "0.19"},
{"0", "2", "0.26"},
{"5", "7", "0.28"},
{"1", "3", "0.29"},
{"1", "5", "0.32"},
{"2", "7", "0.34"},
{"4", "5", "0.35"},
{"1", "2", "0.36"},
{"4", "7", "0.37"},
{"0", "4", "0.38"},
{"6", "2", "0.40"},
{"3", "6", "0.52"},
{"6", "0", "0.58"},
{"6", "4", "0.93"}
};
EdgeWeightedGraph G = new EdgeWeightedGraph(8);
for(int i = 0; i < input.length; i++) {
int v = Integer.parseInt(input[i][0]);
int w = Integer.parseInt(input[i][1]);
double weight = Double.parseDouble(input[i][2]);
Edge edge = new Edge(v, w, weight);
G.addEdge(edge);
}
return G;
}
public static void main (String[] args) {
PrimMinimumSpanningTreeLazy primMinimumSpanningTreeLazy =
new PrimMinimumSpanningTreeLazy(dummyGraph());
System.out.println("PrimMinimumSpanningTreeLazy: Weight = "
+ primMinimumSpanningTreeLazy.weight());
System.out.println("MST edges: ");
primMinimumSpanningTreeLazy.edges()
.forEach(edge ->
System.out.print(edge.either() + "-" + edge.other(edge.either()) + ", "));
}
}
Output
KruskalMinimumSpanningTree: Weight = 1.81
MST edges:
0-7, 1-7, 0-2, 2-3, 5-7, 4-5, 6-2,
Comments
Post a Comment