加权无向图是一种为每条边关联一个权重值或是成本的图模型。这种图能够自然地表示许多应用。在一副航空图中，边表示航线，权值则可以表示距离或是费用。在一副电路图中，边表示导线，权值则可能表示导线的长度即成本，或是信号通过这条先所需的时间。此时我们很容易就能想到，最小成本的问题，例如，从西安飞纽约，怎样飞才能使时间成本最低或者是金钱成本最低？
在下图中，从顶点0到顶点4有三条路径，分别为0-2-3-4,0-2-4,0-5-3-4,那我们如果要通过那条路径到达4顶点最好呢？此时就要考虑，那条路径的成本最低。
加权无向图中的边我们就不能简单的使用v-w两个顶点表示了，而必须要给边关联一个权重值，因此我们可以使用对象来描述一条边。
| 类名 | Edge implements Comparable |
|---|---|
| 成员变量 | 1.private final int v：顶点一2.private final int w：顶点二3.private final double weight：当前边的权重 |
| 构造方法 | Edge(int v,int w,double weight)：通过顶点v和w，以及权重weight值构造一个边对象 |
| 成员方法 | 1.public double weight():获取边的权重值2.public int either():获取边上的一个点3.public int other(int vertex)):获取边上除了顶点vertex外的另外一个顶点4.public int compareTo(Edge that)：比较当前边和参数that边的权重，如果当前边权重大，返回1，如果一样大，返回0，如果当前权重小，返回-1 |
/**
* 边
*
* @author alvin
* @date 2022/11/3
* @since 1.0
**/
public class Edge implements Comparable<Edge> {
//顶点一
private final int v;
//顶点二
private final int w;
//当前边的权重
private final double weight;
//通过顶点v和w，以及权重weight值构造一个边对象
public Edge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
//获取边的权重值
public double weight() {
return weight;
}
//获取边上的一个点
public int either() {
return v;
}
//获取边上除了顶点vertex外的另外一个顶点
public int other(int vertex) {
if (vertex == v) {
return w;
} else {
return v;
}
}
@Override
public int compareTo(Edge that) {
//使用一个遍历记录比较的结果
int cmp;
if (this.weight() > that.weight()) {
//如果当前边的权重值大，则让cmp=1；
cmp = 1;
} else if (this.weight() < that.weight()) {
//如果当前边的权重值小，则让cmp=-1；
cmp = -1;
} else {
//如果当前边的权重值和that边的权重值一样大，则让cmp=0
cmp = 0;
}
return cmp;
}
}之前我们已经完成了无向图，在无向图的基础上，我们只需要把边的表示切换成Edge对象即可。
| 类名 | EdgeWeightedGraph |
|---|---|
| 成员变量 | 1.private final int V: 记录顶点数量2.private int E: 记录边数量3.private Queue[] adj: 邻接表 |
| 构造方法 | EdgeWeightedGraph(int V)：创建一个含有V个顶点的空加权无向图 |
| 成员方法 | 1.public int V():获取图中顶点的数量2.public int E():获取图中边的数量3.public void addEdge(Edge e):向加权无向图中添加一条边e4.public Queue adj(int v)：获取和顶点v关联的所有边5.public Queue edges()：获取加权无向图的所有边 |
/**
* 加权无向图的实现
*
* @author alvin
* @date 2022/11/3
* @since 1.0
**/
public class EdgeWeightedGraph {
//顶点总数
private final int V;
//边的总数
private int E;
//邻接表
private Queue<Edge>[] adj;
//创建一个含有V个顶点的空加权无向图
public EdgeWeightedGraph(int V) {
//初始化顶点数量
this.V = V;
//初始化边的数量
this.E = 0;
//初始化邻接表
this.adj = new Queue[V];
for (int i = 0; i < adj.length; i++) {
adj[i] = new ArrayDeque<>();
}
}
//获取图中顶点的数量
public int V() {
return V;
}
//获取图中边的数量
public int E() {
return E;
}
//向加权无向图中添加一条边e
public void addEdge(Edge e) {
//需要让边e同时出现在e这个边的两个顶点的邻接表中
int v = e.either();
int w = e.other(v);
adj[v].add(e);
adj[w].add(e);
//边的数量+1
E++;
}
//获取和顶点v关联的所有边
public Queue<Edge> adj(int v) {
return adj[v];
}
//获取加权无向图的所有边
public Queue<Edge> edges() {
//创建一个队列对象，存储所有的边
Queue<Edge> allEdges = new ArrayDeque<>();
//遍历图中的每一个顶点，找到该顶点的邻接表，邻接表中存储了该顶点关联的每一条边
//因为这是无向图，所以同一条边同时出现在了它关联的两个顶点的邻接表中，需要让一条边只记录一次；
for (int v = 0; v < V; v++) {
//遍历v顶点的邻接表，找到每一条和v关联的边
for (Edge e : adj(v)) {
if (e.other(v) < v) {
allEdges.add(e);
}
}
}
return allEdges;
}
}
