三、加权无向图
加权无向图是一种为每条边关联一个权重值或是成本的图模型。这种图能够自然地表示许多应用。在一副航空图中，边表示航线，权值则可以表示距离或是费用。在一副电路图中，边表示导线，权值则可能表示导线的长度即成本，或是信号通过这条先所需的时间。此时我们很容易就能想到，最小成本的问题，例如，从西安飞纽约，怎样飞才能使时间成本最低或者是金钱成本最低？
在下图中，从顶点0到顶点4有三条路径，分别为0-2-3-4,0-2-4,0-5-3-4,那我们如果要通过那条路径到达4顶点最好呢？此时就要考虑，那条路径的成本最低。
3.1 加权无向图边的表示
加权无向图中的边我们就不能简单的使用v-w两个顶点表示了，而必须要给边关联一个权重值，因此我们可以使用对象来描述一条边。
API设计：
代码：
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){ //如果传入的顶点vertext是v，则返回另外一个顶点w return w; }else{ //如果传入的顶点vertext不是v，则返回v即可 return v; } } @Override public int compareTo(Edge that) { int cmp; if (this.weight()>that.weight()){ //如果当前边的权重大于参数边that的权重，返回1 cmp=1; }else if(this.weight()<that.weight()){ //如果当前边的权重小于参数边that的权重，返回-1 cmp=-1; }else{ //如果当前边的权重等于参数边that的权重，返回0 cmp=0; } return cmp; } }
3.2 加权无向图的实现
之前我们已经完成了无向图，在无向图的基础上，我们只需要把边的表示切换成Edge对象即可。
API设计：
代码：
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 Queue<Edge>(); } } //获取图中顶点的数量 public int V() { return V; } //获取图中边的数量 public int E() { return E; } //向加权无向图中添加一条边e public void addEdge(Edge e) { //获取边中的一个顶点v int v = e.either(); //获取边中的另一个顶点w int w = e.other(v); //因为是无向图，所以边e需要同时出现在两个顶点的邻接表中 adj[v].enqueue(e); adj[w].enqueue(e); //边的数量+1 E++; } //获取和顶点v关联的所有边 public Queue<Edge> adj(int v) { return adj[v]; } //获取加权无向图的所有边 public Queue<Edge> edges() { //创建一个队列，存储所有的边 Queue<Edge> allEdge = new Queue<>(); //遍历顶点，拿到每个顶点的邻接表 for (int v = 0; v < this.V; v++) { //遍历邻接表，拿到邻接表中的每条边 for (Edge e : adj(v)) { /* 因为无向图中，每条边对象Edge都会在两个顶点的邻接表中各出现一次，为了不重复获取，暂定一条规则：除了当前顶点v，再获取边e中的另外一个顶点w，如果v<w则添加，这样可以保证同一条边只会被统计一次 */ if (e.other(v) < v) { allEdge.enqueue(e); } } } return allEdge; } }
四、最小生成树
之前学习的加权图，我们发现它的边关联了一个权重，那么我们就可以根据这个权重解决最小成本问题，但如何才能找到最小成本对应的顶点和边呢？最小生成树相关算法可以解决。
4.1 最小生成树定义及相关约定
定义：
图的生成树是它的一棵含有其所有顶点的无环连通子图，一副加权无向图的最小生成树它的一棵权值(树中所有边的权重之和)最小的生成树
约定：
只考虑连通图。最小生成树的定义说明它只能存在于连通图中，如果图不是连通的，那么分别计算每个连通图子图的最小生成树，合并到一起称为最小生成森林。
所有边的权重都各不相同。如果不同的边权重可以相同，那么一副图的最小生成树就可能不唯一了，虽然我们的算法可以处理这种情况，但为了好理解，我们约定所有边的权重都各不相同。
4.2 最小生成树原理
4.2.1 树的性质
1.用一条边接树中的任意两个顶点都会产生一个新的环；
2.从树中删除任意一条边，将会得到两棵独立的树；
4.2.2 切分定理
要从一副连通图中找出该图的最小生成树，需要通过切分定理完成。
切分：
将图的所有顶点按照某些规则分为两个非空且没有交集的集合。
横切边：
连接两个属于不同集合的顶点的边称之为横切边。
例如我们将图中的顶点切分为两个集合，灰色顶点属于一个集合，白色顶点属于另外一个集合，那么效果如下：
切分定理：
在一副加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图中的最小生成树
注意:一次切分产生的多个横切边中，权重最小的边不一定是所有横切边中唯一属于图的最小生成树的边。
4.3 贪心算法
贪心算法是计算图的最小生成树的基础算法，它的基本原理就是切分定理，使用切分定理找到最小生成树的一条边，不断的重复直到找到最小生成树的所有边。如果图有V个顶点，那么需要找到V-1条边，就可以表示该图的最小生成树。
4.4 Prim 算法
我们学习第一种计算最小生成树的方法叫Prim算法，它的每一步都会为一棵生成中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加
入到树中。
Prim算法的切分规则：
把最小生成树中的顶点看做是一个集合，把不在最小生成树中的顶点看做是另外一个集合。
