可以对比加权无向图的实现。
加权有向边API:
public class DirectedEdge DirectedEdge(int v,int w,double weight) double weight() 边的权重 int form() 指出这条边的顶点 int to() 这条边指向的顶点 String toString() 对象的字符串表示
实现:
public class DirectedEdge {
private int v;
private int w;
private double weight;
public DirectedEdge(int v,int w,double weight) {
this.v = v;this.w = w;this.weight = weight;
}
public double weight(){ return weight; }
public int form(){ return v; }
public int to(){ return w; }
public String toString(){ return String.format("%d->%d %.2f", v,w,weight); }
}
加权有向图API:
public class EdgeWeightedDigraph EdgeWeightedDigraph(int v) 含有V个顶点的空有向图 int V() 顶点总数 int E() 边的总数 void addEdge(DirectedEdge e) 将e添加到该有向图中 Iterable<DirectedEdge> adj(int v) 从v指出的边 Iterable<DirectedEdge> edges() 该有向图中的所有边 String toString() 对象的字符串表示
实现:
public class EdgeWeightedDigraph {
private int V;//顶点数
private int E;//边数
private Bag<DirectedEdge>[] adj;//邻接表
public EdgeWeightedDigraph(int V) {
this.V = V;
this.E = 0;
adj = (Bag<DirectedEdge>[]) new Bag[V];
for(int v=0;v< V;v++) {
adj[v] = new Bag<DirectedEdge>();
}
}
public int V() {return V;}
public int E() {return E;}
public void addEdge(DirectedEdge e) {
adj[e.form()].add(e);
E++;
}
//从v指出的边
public Iterable<DirectedEdge> adj(int v){return adj[v];}
//该有向图中所有的边
public Iterable<DirectedEdge> edges(){
Bag<DirectedEdge> bag = new Bag<DirectedEdge>();
for(int v = 0; v<V; v++)
for(DirectedEdge e : adj[v])
bag.add(e);
return bag;
}
}