4.4.1 Prim 算法API设计
4.4.2 Prim算法的实现原理
Prim算法始终将图中的顶点切分成两个集合，最小生成树顶点和非最小生成树顶点，通过不断的重复做某些操作，可以逐渐将非最小生成树中的顶点加入到最小生成树中，直到所有的顶点都加入到最小生成树中。
我们在设计API的时候，使用最小索引优先队列存放树中顶点与非树中顶点的有效横切边，那么它是如何表示的呢？我们可以让最小索引优先队列的索引值表示图的顶点，让最小索引优先队列中的值表示从其他某个顶点到当前顶点的边权重。
初始化状态，先默认 0是最小生成树中的唯一顶点，其他的顶点都不在最小生成树中，此时横切边就是顶点0的邻接表中0-2,0-4,0-6,0-7这四条边，我们只需要将索引优先队列的2、4、6、7索引处分别存储这些边的权重值就可以表示了。
现在只需要从这四条横切边中找出权重最小的边，然后把对应的顶点加进来即可。所以找到 0-7这条横切边的权重最小，因此把0-7这条边添加进来，此时0和7属于最小生成树的顶点，其他的不属于，现在顶点7的邻接表中的边也成为了横切边，这时需要做两个操作：
1、0-7这条边已经不是横切边了，需要让它失效：
只需要调用最小索引优先队列的delMin()方法即可完成；
2、2和4顶点各有两条连接指向最小生成树，需要只保留一条：
4-7的权重小于0-4的权重，所以保留4-7，调用索引优先队列的change(4,0.37)即可，0-2的权重小于2-7的权重，所以保留0-2，不需要做额外操作。
我们不断重复上面的动作，就可以把所有的顶点添加到最小生成树中。
4.4.3 代码
public class PrimMST { //索引代表顶点，值表示当前顶点和最小生成树之间的最短边 private Edge[] edgeTo; //索引代表顶点，值表示当前顶点和最小生成树之间的最短边的权重 private double[] distTo; //索引代表顶点，如果当前顶点已经在树中，则值为true，否则为false private boolean[] marked; //存放树中顶点与非树中顶点之间的有效横切边 private IndexMinPriorityQueue<Double> pq; //根据一副加权无向图，创建最小生成树计算对象 public PrimMST(EdgeWeightedGraph G) { //创建一个和图的顶点数一样大小的Edge数组，表示边 this.edgeTo = new Edge[G.V()]; //创建一个和图的顶点数一样大小的double数组，表示权重，并且初始化数组中的内容为无穷大，无穷大即表示不存在这样的边 this.distTo = new double[G.V()]; for (int i = 0; i < distTo.length; i++) { distTo[i] = Double.POSITIVE_INFINITY; } //创建一个和图的顶点数一样大小的boolean数组，表示当前顶点是否已经在 树中 this.marked = new boolean[G.V()]; //创建一个和图的顶点数一样大小的索引优先队列，存储有效横切边 this.pq = new IndexMinPriorityQueue<>(G.V()); //默认让顶点0进入树中，但0顶点目前没有与树中其他的顶点相连接，因此初始化distTo[0]=0.0 distTo[0] = 0.0; //使用顶点0和权重0初始化pq pq.insert(0, 0.0); //遍历有效边队列 while (!pq.isEmpty()) { //找到权重最小的横切边对应的顶点，加入到最小生成树中 visit(G, pq.delMin()); } } //将顶点v添加到最小生成树中，并且更新数据 private void visit(EdgeWeightedGraph G, int v) { //把顶点v添加到树中 marked[v] = true; //遍历顶点v的邻接表,得到每一条边Edge e, for (Edge e : G.adj(v)) { //边e的一个顶点是v，找到另外一个顶点w； int w = e.other(v); //检测是否已经在树中，如果在，则继续下一次循环，如果不在，则需要修正当前顶点w距离最小生成树的最小边edgeTo[w]以及它的权重distTo[w]，还有有效横切边也需要修正 if (marked[w]) { continue; } //如果v-w边e的权重比目前distTo[w]权重小，则需要修正数据 if (e.weight() < distTo[w]) { //把顶点w距离最小生成树的边修改为e edgeTo[w] = e; //把顶点w距离最小生成树的边的权重修改为e.weight() distTo[w] = e.weight(); //如果pq中存储的有效横切边已经包含了w顶点，则需要修正最小索引优先队列w索引关联的权重值 if (pq.contains(w)) { pq.changeItem(w, e.weight()); } else { //如果pq中存储的有效横切边不包含w顶点，则需要向最小索引优先队列中添加v-w和其权重值 pq.insert(w, e.weight()); } } } } //获取最小生成树的所有边 public Queue<Edge> edges() { //创建队列 Queue<Edge> edges = new Queue<>(); //遍历edgeTo数组，找到每一条边，添加到队列中 for (int i = 0; i < marked.length; i++) { if (edgeTo[i]!=null){ edges.enqueue(edgeTo[i]); } } return edges; } } //测试代码 public class PrimTest { public static void main(String[] args) throws Exception { //创建输入流 BufferedReader reader = new BufferedReader(new InputStreamReader(PrimTest.class.getClassLoader().getResourceAsStream("min_create_tree_test.txt"))); //读取顶点数目，初始化EdgeWeightedGraph图 int number = Integer.parseInt(reader.readLine()); EdgeWeightedGraph G = new EdgeWeightedGraph(number); //读取边的数目 int edgeNumber = Integer.parseInt(reader.readLine()); //循环读取每一条边，并调用addEdge方法 for (int i = 0; i < edgeNumber; i++) { String line = reader.readLine(); int v = Integer.parseInt(line.split(" ")[0]); int w = Integer.parseInt(line.split(" ")[1]); double weight = Double.parseDouble(line.split(" ")[2]); G.addEdge(new Edge(v, w, weight)); } //构建PrimMST对象 PrimMST mst = new PrimMST(G); //获取最小生成树的边 Queue<Edge> edges = mst.edges(); //打印输出 for (Edge edge : edges) { if (edge!=null){ System.out.println(edge.either() + "-" + edge.other(edge.either()) + "::" +edge.weight()); } } } }
4.5 kruskal 算法
kruskal算法是计算一副加权无向图的最小生成树的另外一种算法，它的主要思想是按照边的权重(从小到大)处理它们，将边加入最小生成树中，加入的边不会与已经加入最小生成树的边构成环，直到树中含有V-1条边为止。
kruskal算法和prim算法的区别：
Prim算法是一条边一条边的构造最小生成树，每一步都为一棵树添加一条边。kruskal算法构造最小生成树的时候也是一条边一条边地构造，但它的切分规则是不一样的。它每一次寻找的边会连接一片森林中的两棵树。如果一副加权无向图由V个顶点组成，初始化情况下每个顶点都构成一棵独立的树，则V个顶点对应V棵树，组成一片森林，kruskal算法每一次处理都会将两棵树合并为一棵树，直到整个森林中只剩一棵树为止。
4.5.1 kruskal 算法API设计
4.5.2 kruskal算法的实现原理
在设计API的时候，使用了一个MinPriorityQueue pq存储图中所有的边，每次使用pq.delMin()取出权重最小的边，并得到该边关联的两个顶点v和w，通过uf.connect(v,w)判断v和w是否已经连通，如果连通，则证明这两个顶点在同一棵树中，那么就不能再把这条边添加到最小生成树中，因为在一棵树的任意两个顶点上添加一条边，都会形成环，而最小生成树不能有环的存在，如果不连通，则通过uf.connect(v,w)把顶点v所在的树和顶点w所在的树合并成一棵树，并把这条边加入到mst队列中，这样如果把所有的边处理完，最终mst中存储的就是最小生树的所有边。
4.5.3 代码
public class KruskalMST { //保存最小生成树的所有边 private Queue<Edge> mst; //索引代表顶点，使用uf.connect(v,w)可以判断顶点v和顶点w是否在同一颗树中，使用uf.union(v,w)可以把顶点v所在的树和顶点w所在的树合并 private UF_Tree_Weighted uf; //存储图中所有的边，使用最小优先队列，对边按照权重进行排序 private MinPriorityQueue<Edge> pq; //根据一副加权无向图，创建最小生成树计算对象 public KruskalMST(EdgeWeightedGraph G) { //初始化mst队列 this.mst = new Queue<Edge>(); //初始化并查集对象uf,容量和图的顶点数相同 this.uf = new UF_Tree_Weighted(G.V()); //初始化最小优先队列pq，容量比图的边的数量大1，并把图中所有的边放入 pq中 this.pq = new MinPriorityQueue<>(G.E()+1); for (Edge edge : G.edges()) { pq.insert(edge); } //如果优先队列pq不为空，也就是还有边未处理，并且mst中的边还不到V-1条，继续遍历 while (!pq.isEmpty() && mst.size() < G.V() - 1) { //取出pq中权重最小的边e Edge e = pq.delMin(); //获取边e的两个顶点v和w int v = e.either(); int w = e.other(v); /* 通过uf.connect(v,w)判断v和w是否已经连通， 如果连通: 则证明这两个顶点在同一棵树中，那么就不能再把这条边添加到最小生成树中，因为在一棵树的任意两个顶点上添加一条边，都会形成环，而最小生成树不能有环的存在; 如果不连通: 则通过uf.connect(v,w)把顶点v所在的树和顶点w所在的树合并成一棵树,并把这条边加入到mst队列中 */ if (uf.connected(v,w)){ continue; } uf.union(v,w); mst.enqueue(e); } } //获取最小生成树的所有边 public Queue<Edge> edges() { return mst; } } //测试代码 public class KruskalTest { public static void main(String[] args) throws Exception { //创建输入流 BufferedReader reader = new BufferedReader(new InputStreamReader(KruskalTest.class.getClassLoader().getResourceAsStream("min_create_tree_test.txt"))); //读取顶点数目，初始化EdgeWeightedGraph图 int number = Integer.parseInt(reader.readLine()); EdgeWeightedGraph G = new EdgeWeightedGraph(number); //读取边的数目 int edgeNumber = Integer.parseInt(reader.readLine()); //循环读取每一条边，并调用addEdge方法 for (int i = 0; i < edgeNumber; i++) { String line = reader.readLine(); int v = Integer.parseInt(line.split(" ")[0]); int w = Integer.parseInt(line.split(" ")[1]); double weight = Double.parseDouble(line.split(" ")[2]); G.addEdge(new Edge(v, w, weight)); } //构建PrimMST对象 KruskalMST mst = new KruskalMST(G); //获取最小生成树的边 Queue<Edge> edges = mst.edges(); //打印输出 for (Edge edge : edges) { if (edge!=null){ System.out.println(edge.either() + "-" + edge.other(edge.either()) + "::" +edge.weight()); } } } }
五、加权有向图
之前学习的加权无向图中，边是没有方向的，并且同一条边会同时出现在该边的两个顶点的邻接表中，为了能够处理含有方向性的图的问题，我们需要实现以下加权有向图。
5.1 加权有向图边的表示
API设计：
代码：
public class DirectedEdge { private final int v;//起点 private final int w;//终点 private final double weight;//当前边的权重 //通过顶点v和w，以及权重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 from(){ return v; } //获取有向边的终点 public int to(){ return w; } }
5.2 加权有向图的实现
之前我们已经完成了有向图，在有向图的基础上，我们只需要把边的表示切换成DirectedEdge对象即可。
API设计：
代码：
public class EdgeWeightedDigraph { //顶点总数 private final int V; //边的总数 private int E; //邻接表 private Queue<DirectedEdge>[] adj; //创建一个含有V个顶点的空加权有向图 public EdgeWeightedDigraph(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<DirectedEdge>(); } } //获取图中顶点的数量 public int V() { return V; } //获取图中边的数量 public int E() { return E; } //向加权有向图中添加一条边e public void addEdge(DirectedEdge e) { //获取有向边的起点 int v = e.from(); //因为是有向图，所以边e只需要出现在起点v的邻接表中 adj[v].enqueue(e); //边的数量+1 E++; } //获取由顶点v指出的所有的边 public Queue<DirectedEdge> adj(int v) { return adj[v]; } //获取加权有向图的所有边 public Queue<DirectedEdge> edges() { //创建一个队列，存储所有的边 Queue<DirectedEdge> allEdge = new Queue<>(); //遍历顶点，拿到每个顶点的邻接表 for (int v = 0; v < this.V; v++) { //遍历邻接表，拿到邻接表中的每条边存储到队列中 for (DirectedEdge e : adj(v)) { allEdge.enqueue(e); } } return allEdge; } }
六、最短路径
有了加权有向图之后，我们立刻就能联想到实际生活中的使用场景，例如在一副地图中，找到顶点a与地点b之间的路径，这条路径可以是距离最短，也可以是时间最短，也可以是费用最小等，如果我们把 距离 /时间/费用 看做是成本，那么就需要找到地点a和地点b之间成本最小的路径，也就是我们接下来要解决的最短路径问题。
6.1 最短路径定义及性质
定义：
在一副加权有向图中，从顶点s到顶点t的最短路径是所有从顶点s到顶点t的路径中总权重最小的那条路径。
性质：
1.路径具有方向性；
2.权重不一定等价于距离。权重可以是距离、时间、花费等内容，权重最小指的是成本最低
3.只考虑连通图。一副图中并不是所有的顶点都是可达的，如果s和t不可达，那么它们之间也就不存在最短路径，为了简化问题，这里只考虑连通图。
4.最短路径不一定是唯一的。从一个顶点到达另外一个顶点的权重最小的路径可能会有很多条，这里只需要找出一条即可。
最短路径树：
给定一副加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一副子图，它包含顶点s以及从s可达的所有顶点。这棵有向树的根结点为s，树的每条路径都是有向图中的一条最短路径。
6.2 最短路径树API设计
计算最短路径树的经典算法是dijstra算法，为了实现它，先设计如下API：
6.3 松弛技术
松弛这个词来源于生活：一条橡皮筋沿着两个顶点的某条路径紧紧展开，如果这两个顶点之间的路径不止一条，还有存在更短的路径，那么把皮筋转移到更短的路径上，皮筋就可以放松了。
松弛这种简单的原理刚好可以用来计算最短路径树。
在我们的API中，需要用到两个成员变量edgeTo和distTo，分别存储边和权重。一开始给定一幅图G和顶点s，我们只知道图的边以及这些边的权重，其他的一无所知，此时初始化顶点s到顶点s的最短路径的总权重disto[s]=0；顶
点s到其他顶点的总权重默认为无穷大，随着算法的执行，不断的使用松弛技术处理图的边和顶点，并按一定的条件更新edgeTo和distTo中的数据，最终就可以得到最短路劲树。
边的松弛：
放松边v->w意味着检查从s到w的最短路径是否先从s到v，然后再从v到w？
如果是，则v-w这条边需要加入到最短路径树中，更新edgeTo和distTo中的内容：
edgeTo[w]=表示v->w这条边的DirectedEdge对象，distTo[w]=distTo[v]+v->w这条边的权重；如果不是，则忽略v->w这条边。
顶点的松弛：
顶点的松弛是基于边的松弛完成的，只需要把某个顶点指出的所有边松弛，那么该顶点就松弛完毕。例如要松弛顶点v，只需要遍历v的邻接表，把每一条边都松弛，那么顶点v就松弛了。
如果把起点设置为顶点0，那么找出起点0到顶点6的最短路径0->2->7>3->6的过程如下:
6.4 Dijstra 算法实现
Disjstra算法的实现和Prim算法很类似，构造最短路径树的每一步都是向这棵树中添加一条新的边，而这条新的边是有效横切边pq队列中的权重最小的边。
public class DijkstraSP { //索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边 private DirectedEdge[] edgeTo; //索引代表顶点，值从顶点s到当前顶点的最短路径的总权重 private double[] distTo; //存放树中顶点与非树中顶点之间的有效横切边 private IndexMinPriorityQueue<Double> pq; //根据一副加权有向图G和顶点s，创建一个计算顶点为s的最短路径树对象 public DijkstraSP(EdgeWeightedDigraph G, int s){ //创建一个和图的顶点数一样大小的DirectedEdge数组，表示边 this.edgeTo = new DirectedEdge[G.V()]; //创建一个和图的顶点数一样大小的double数组，表示权重，并且初始化数组中的内容为无穷大，无穷大即表示不存在这样的边 this.distTo = new double[G.V()]; for (int i = 0; i < distTo.length; i++) { distTo[i] = Double.POSITIVE_INFINITY; } //创建一个和图的顶点数一样大小的索引优先队列，存储有效横切边 this.pq = new IndexMinPriorityQueue<>(G.V()); //默认让顶点s进入树中，但s顶点目前没有与树中其他的顶点相连接，因此 初始化distTo[s]=0.0 distTo[s] = 0.0; //使用顶点s和权重0.0初始化pq pq.insert(s, 0.0); //遍历有效边队列 while (!pq.isEmpty()) { //松弛图G中的顶点 relax(G, pq.delMin()); } } //松弛图G中的顶点v private void relax(EdgeWeightedDigraph G, int v){ //松弛顶点v就是松弛顶点v邻接表中的每一条边，遍历邻接表 for (DirectedEdge e : G.adj(v)) { //获取边e的终点 int w = e.to(); //起点s到顶点w的权重是否大于起点s到顶点v的权重+边e的权重,如果大于，则修改s->w的路径：edgeTo[w]=e,并修改distTo[v] = distTo[v]+e.weitht(),如果不大于，则忽略 if (distTo(w)>distTo(v)+e.weight()){ distTo[w]=distTo[v]+e.weight(); edgeTo[w]=e; //如果顶点w已经存在于优先队列pq中，则重置顶点w的权重 if (pq.contains(w)){ pq.changeItem(w,distTo(w)); }else{ //如果顶点w没有出现在优先队列pq中，则把顶点w及其权重加入到pq中 pq.insert(w,distTo(w)); } } } } //获取从顶点s到顶点v的最短路径的总权重 public double distTo(int v){ return distTo[v]; } //判断从顶点s到顶点v是否可达 public boolean hasPathTo(int v){ return distTo[v]<Double.POSITIVE_INFINITY; } //查询从起点s到顶点v的最短路径中所有的边 public Queue<DirectedEdge> pathTo(int v){ //如果顶点s到v不可达，则返回null if (!hasPathTo(v)){ return null; } //创建队列Queue保存最短路径的边 Queue<DirectedEdge> edges = new Queue<>(); //从顶点v开始，逆向寻找，一直找到顶点s为止，而起点s为最短路劲树的根结点，所以 edgeTo[s]=null; DirectedEdge e=null; while(true){ e = edgeTo[v]; if (e==null){ break; } edges.enqueue(e); v = e.from(); } return edges; } } //测试代码 public class DijkstraSpTest { public static void main(String[] args) throws Exception { //创建输入流 BufferedReader reader = new BufferedReader(new InputStreamReader(DijkstraSpTest.class.getClassLoader().getResourceAsStream("min_route_test.txt"))); //读取顶点数目，初始化EdgeWeightedDigraph图 int number = Integer.parseInt(reader.readLine()); EdgeWeightedDigraph G = new EdgeWeightedDigraph(number); //读取边的数目 int edgeNumber = Integer.parseInt(reader.readLine()); //循环读取每一条边，并调用addEdge方法 for (int i = 0; i < edgeNumber; i++) { String line = reader.readLine(); int v = Integer.parseInt(line.split(" ")[0]); int w = Integer.parseInt(line.split(" ")[1]); double weight = Double.parseDouble(line.split(" ")[2]); G.addEdge(new DirectedEdge(v, w, weight)); } //根据图G和顶点0，构建DijkstraSP对象 DijkstraSP dsp = new DijkstraSP(G, 0); //获取起点0到顶点6的最短路径 Queue<DirectedEdge> edges = dsp.pathTo(6); //打印输出 for (DirectedEdge edge : edges) { System.out.println(edge.from() + "->" + edge.to() + "::" + edge.weight()); } } }
七、数据结构与算法学习快速电梯
