加权无向图的实现最简单的方法是扩展无向图的表示方法:在邻接表的表示中,可以在链表的结点中增加一个权重域。但这里用另一个方法来实现:我们实现两个类,权重边类和无向图类。无向图类中组合权重边类来实现加权无向图。
加权边API:
public class Edge implements Comparable<Edge> Edge(int v,int w,double weight) 构造函数 double weight() 边的权重 int either() 边两端的顶点之一 int other(int vertex) 另一个顶点 int comparable(Edge that) 比较 String toString() 对象的字符串表示
实现:
public class Edge implements Comparable<Edge> { //实现Comparable接口
private int v;
private int w;
private double weight;
public Edge(int v,int w,double weight)
{ this.v = v; this.w = w; this.weight = weight;}
//获取边的一个结点和另一个节点
public int either() {return v;}
public int other(int vertex) {
if(vertex == v) return w;
else if(vertex == w) return v;
}
//实现接口中的compareTo()方法
public int compareTo(Edge that) {
if(this.weight() < that.weight()) return -1;
else if(this.weight() > that.weight()) return 1;
else return 0;
}
public double weight() {return weight;}
public String toString() { return String.format("%d-%d %.2f", v,w,weight); }
}
加权无向图API:
public class EdgeWeightedGraph int V() 图的顶点数 int E() 图的边数 void addEdge(Edge e) 添加边 Iterable<Edge> adj(int v) 和v相关联的所有边 Iterable<Edge> edges() 图的所有边
实现:
public class EdgeWeightedGraph {
private int V;//顶点数
private int E;//边数
private Bag<Edge>[] adj;//一个边类型的背包
public EdgeWeightedGraph(int V){
this.V = V;
this.E = 0;
adj = (Bag<Edge>[]) new Bag[V];
for(int v = 0; v < V; v++){
adj[v] = new Bag<Edge>(); //二维数组
}
public int V() {return V;}
public int E() {return E;}
//添加边
public void addEdge(Edge e) {
//获取边的两个顶点
int v = e.either();
int w = e.other(v);
//因为是无向图,互相添加边,调用的是背包的add()方法
adj[v].add(e);
adj[w].add(e);
E++;
}
//和v相关联的所有边
public Iterable<Edge> adj(int v){ return adj[v]; }
//图的所有边
public Iterable<Edge> edges(){
Bag<Edge> b = new Bag<Edge>();
for(int v = 0; v <V ; v++)
for(Edge e : adj[v])
if(e.other(v)>v) b.add(e);
return b;
}
}