前言
加权无向图是一种为每条边关联一个权重值或是成本的图模型。这种图能够自然地表示许多应用。在一副航空图中，边表示航线，权值则可以表示距离或是费用。在一副电路图中，边表示导线，权值则可能表示导线的长度即成本，或是信号通过这条先所需的时间。此时我们很容易就能想到，最小成本的问题，例如，从西安飞纽约，怎样飞才能使时间成本最低或者是金钱成本最低？
在下图中，从顶点0到顶点4有三条路径，分别为0-2-3-4,0-2-4,0-5-3-4,那我们如果要通过那条路径到达4顶点最好呢？此时就要考虑，那条路径的成本最低。
边的表示
加权无向图中的边我们就不能简单的使用v-w两个顶点表示了，而必须要给边关联一个权重值，因此我们可以使用对象来描述一条边。
API设计
| 类名 | 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对象即可。
API设计
| 类名 | 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; } }
