6、普里姆算法
6.1、应用场景(修路问题)
看一个应用场景和问题：
有胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在需要修路把7个村庄连通
各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里
问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
正确的思路，就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少
6.2、最小生成树
修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称MST。
给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，这叫最小生成树
N个顶点，一定有N-1条边
包含全部顶点
N-1条边都在图中
求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法
6.3、普里姆算法介绍
普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图
普利姆的算法如下:
设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合
若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited[u]=1
若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边（ui,vj）加入集合D中，标记visited[vj]=1
重复上述步骤，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边
提示: 单独看步骤很难理解，我们通过实例和代码来讲解，比较好理解
6.4、代码思路
举例来说明，就用下面这张图，起始顶点起始无所谓，因为顶点有 7 个，边数最少为 6 条边，最后得到的 6 条边中，其路径长度都是所有边中路径长度最短的
第一步：选取顶点 A ，并标记顶点 A 已被访问，求取最短路径
A – > B ：路径长度为 5
A – > C ：路径长度为 7
A – > G ：路径长度为 2
选取最短路径 ，其长度为 2
标记顶点 G 已被访问过
第二步：同样也是求取最短路径
A – > B ：路径长度为 5
A – > C ：路径长度为 7
A – > G ：G 已经被访问过，不考虑
G – > B ：路径长度为 3
G – > E ：路径长度为 4
G – > F ：路径长度为 6
选取最短路径 ，其长度为 3
标记顶点 B 已被访问过
第三步：同样也是求取最短路径
A – > B ：B 已经被访问过，不考虑
A – > C ：路径长度为 7
A – > G ：G 已经被访问过，不考虑
G – > B ：B 已经被访问过，不考虑
G – > E ：路径长度为 4
G – > F ：路径长度为 6
B --> A ：A 已经被访问过，不考虑
B --> D ：路径长度为 9
选取最短路径 ，其长度为 4
标记顶点 E 已被访问过
第 n 步：以此类推
什么时候停止？n 个顶点最少需要 n - 1 条边
- 我感觉我可以优化上面的逻辑和下面的代码，改日吧
6.5、代码实现
6.5.1、图的定义
- 使用邻接矩阵法，定义一张图
class MGraph { int verxs; // 表示图的节点个数 char[] data;// 存放结点数据 int[][] weight; // 存放边，就是我们的邻接矩阵 public MGraph(int verxs) { this.verxs = verxs; data = new char[verxs]; weight = new int[verxs][verxs]; } //创建图的邻接矩阵 /** * * @param graph 图对象 * @param verxs 图对应的顶点个数 * @param data 图的各个顶点的值 * @param weight 图的邻接矩阵 */ public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) { int i, j; for (i = 0; i < verxs; i++) {// 顶点 graph.data[i] = data[i]; for (j = 0; j < verxs; j++) { graph.weight[i][j] = weight[i][j]; } } } // 显示图的邻接矩阵 public void showGraph(MGraph graph) { for (int[] link : graph.weight) { System.out.println(Arrays.toString(link)); } } }
6.5.2、普林姆算法
- 编写普林姆算法
//创建最小生成树->村庄的图 class MinTree { //编写prim算法，得到最小生成树 /** * * @param graph 图 * @param v 表示从图的第几个顶点开始生成，'A'->0 'B'->1... */ public void prim(MGraph graph, int v) { // visited[] 标记结点(顶点)是否被访问过 int visited[] = new int[graph.verxs]; // 把当前这个结点标记为已访问 visited[v] = 1; // h1 和 h2 记录两个顶点的下标 int h1 = -1; int h2 = -1; int minWeight = 10000; // 将 minWeight 初始成一个大数，后面在遍历过程中，会被替换 for (int k = 1; k < graph.verxs; k++) {// 因为有 graph.verxs顶点，普利姆算法结束后，有 graph.verxs-1边 // 这个是确定每一次生成的子图 ，和哪个结点的距离最近 for (int i = 0; i < graph.verxs; i++) {// i结点表示被访问过的结点 for (int j = 0; j < graph.verxs; j++) {// j结点表示还没有访问过的结点 if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) { // 替换minWeight(寻找已经访问过的结点和未访问过的结点间的权值最小的边) minWeight = graph.weight[i][j]; h1 = i; h2 = j; } } } // 找到一条边是最小 System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight); // 将当前这个结点标记为已经访问 visited[h2] = 1; // minWeight 重新设置为最大值 10000 minWeight = 10000; } } }
6.5.3、代码测试
- 代码
public static void main(String[] args) { //测试看看图是否创建ok char[] data = new char[]{'A','B','C','D','E','F','G'}; int verxs = data.length; //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通 int [][]weight=new int[][]{ {10000,5,7,10000,10000,10000,2}, {5,10000,10000,9,10000,10000,3}, {7,10000,10000,10000,8,10000,10000}, {10000,9,10000,10000,10000,4,10000}, {10000,10000,8,10000,10000,5,4}, {10000,10000,10000,4,5,10000,6}, {2,3,10000,10000,4,6,10000} }; //创建MGraph对象 MGraph graph = new MGraph(verxs); //创建一个MinTree对象 MinTree minTree = new MinTree(); graph.createGraph(graph, verxs, data, weight); //输出 graph.showGraph(graph); //测试普利姆算法 minTree.prim(graph, 0); }
- 程序运行结果
[10000, 5, 7, 10000, 10000, 10000, 2] [5, 10000, 10000, 9, 10000, 10000, 3] [7, 10000, 10000, 10000, 8, 10000, 10000] [10000, 9, 10000, 10000, 10000, 4, 10000] [10000, 10000, 8, 10000, 10000, 5, 4] [10000, 10000, 10000, 4, 5, 10000, 6] [2, 3, 10000, 10000, 4, 6, 10000] 边<A,G> 权值:2 边<G,B> 权值:3 边<G,E> 权值:4 边<E,F> 权值:5 边<F,D> 权值:4 边<A,C> 权值:7
6.6、普利姆算法全部代码
public class PrimAlgorithm { public static void main(String[] args) { //测试看看图是否创建ok char[] data = new char[]{'A','B','C','D','E','F','G'}; int verxs = data.length; //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通 int [][]weight=new int[][]{ {10000,5,7,10000,10000,10000,2}, {5,10000,10000,9,10000,10000,3}, {7,10000,10000,10000,8,10000,10000}, {10000,9,10000,10000,10000,4,10000}, {10000,10000,8,10000,10000,5,4}, {10000,10000,10000,4,5,10000,6}, {2,3,10000,10000,4,6,10000} }; //创建MGraph对象 MGraph graph = new MGraph(verxs); //创建一个MinTree对象 MinTree minTree = new MinTree(); graph.createGraph(graph, verxs, data, weight); //输出 graph.showGraph(graph); //测试普利姆算法 minTree.prim(graph, 0);// } } //创建最小生成树->村庄的图 class MinTree { //编写prim算法，得到最小生成树 /** * * @param graph 图 * @param v 表示从图的第几个顶点开始生成，'A'->0 'B'->1... */ public void prim(MGraph graph, int v) { // visited[] 标记结点(顶点)是否被访问过 int visited[] = new int[graph.verxs]; // 把当前这个结点标记为已访问 visited[v] = 1; // h1 和 h2 记录两个顶点的下标 int h1 = -1; int h2 = -1; int minWeight = 10000; // 将 minWeight 初始成一个大数，后面在遍历过程中，会被替换 for (int k = 1; k < graph.verxs; k++) {// 因为有 graph.verxs顶点，普利姆算法结束后，有 graph.verxs-1边 // 这个是确定每一次生成的子图 ，和哪个结点的距离最近 for (int i = 0; i < graph.verxs; i++) {// i结点表示被访问过的结点 for (int j = 0; j < graph.verxs; j++) {// j结点表示还没有访问过的结点 if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) { // 替换minWeight(寻找已经访问过的结点和未访问过的结点间的权值最小的边) minWeight = graph.weight[i][j]; h1 = i; h2 = j; } } } // 找到一条边是最小 System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight); // 将当前这个结点标记为已经访问 visited[h2] = 1; // minWeight 重新设置为最大值 10000 minWeight = 10000; } } } class MGraph { int verxs; // 表示图的节点个数 char[] data;// 存放结点数据 int[][] weight; // 存放边，就是我们的邻接矩阵 public MGraph(int verxs) { this.verxs = verxs; data = new char[verxs]; weight = new int[verxs][verxs]; } //创建图的邻接矩阵 /** * * @param graph 图对象 * @param verxs 图对应的顶点个数 * @param data 图的各个顶点的值 * @param weight 图的邻接矩阵 */ public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) { int i, j; for (i = 0; i < verxs; i++) {// 顶点 graph.data[i] = data[i]; for (j = 0; j < verxs; j++) { graph.weight[i][j] = weight[i][j]; } } } // 显示图的邻接矩阵 public void showGraph(MGraph graph) { for (int[] link : graph.weight) { System.out.println(Arrays.toString(link)); } } }
7、克鲁斯卡尔算法
7.1、应用场景(公交站问题)
- 看一个应用场景和问题：
- 某城市新增7个站点(A, B, C, D, E, F, G) ，现在需要修路把7个站点连通
- 各个站点的距离用边线表示(权) ，比如 A – B 距离 12公里
- 问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?
7.2、克鲁斯卡尔算法介绍
克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路
具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止
7.3、代码思路
7.3.1、最小生成树
- 在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树
- 例如，对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。
7.3.2、克鲁斯卡尔算法图解
以上图G4为例，来对克鲁斯卡尔进行演示(假设，用数组R保存最小生成树结果)
第1步：将边加入R中。 边的权值最小，因此将它加入到最小生成树结果R中。
第2步：将边加入R中。 上一步操作之后，边的权值最小，因此将它加入到最小生成树结果R中。
第3步：将边加入R中。 上一步操作之后，边的权值最小，因此将它加入到最小生成树结果R中。
第4步：将边加入R中。 上一步操作之后，边的权值最小，但会和已有的边构成回路；因此，跳过边。同理，跳过边。将边加入到最小生成树结果R中。
第5步：将边加入R中。 上一步操作之后，边的权值最小，因此将它加入到最小生成树结果R中。
第6步：将边加入R中。 上一步操作之后，边的权值最小，但会和已有的边构成回路；因此，跳过边。同理，跳过边。将边加入到最小生成树结果R中。
此时，最小生成树构造完成！它包括的边依次是： 。
- 总结：
- 将所有边按照权值排序，从小到大依次加入森林中
- 前提条件：森林中不产生回路，因为产生回路，这条路就相当于是多余的，就算它权值再小也没卵用
7.4、克鲁斯卡尔算法分析
根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：
问题一：对图的所有边按照权值大小进行排序？采用排序算法进行排序即可。
问题二：将边添加到最小生成树中时，怎么样判断是否形成了回路？处理方式是：
记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"
然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路
想想为什么能这样判断是否形成了回路？下面举例说明
在将 加入到最小生成树R中之后，这几条边的顶点就都有了终点
C的终点是F
D的终点是F
E的终点是F
F的终点是F
关于终点的说明：
就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是与它连通的最大顶点。
因此，接下来，虽然是权值最小的边。但是C和E的终点都是F，即它们的终点相同，因此，将加入最小生成树的话，会形成回路。
这就是判断回路的方式。也就是说，我们加入的边的两个顶点不能都指向同一个终点，否则将构成回路
为啥添加边时，该边的两个顶点的终点重合，他们两就指向同一个构成回路？两个顶点的终点重合，就说明这两个顶点都能寻找到一条路径，跑到终点处，再为这两个顶点添加一条边，就是画蛇添足，只会增加总路径的长度
7.5、代码实现
7.5.1、边的定义
- 定义 EdgeData 类，用于表示一条边
//创建一个类EData ，它的对象实例就表示一条边 class EdgeData { char start; // 边的一个点 char end; // 边的另外一个点 int weight; // 边的权值 // 构造器 public EdgeData(char start, char end, int weight) { this.start = start; this.end = end; this.weight = weight; } // 重写toString, 便于输出边信息 @Override public String toString() { return "EData [<" + start + ", " + end + ">= " + weight + "]"; } }
7.5.2、克鲁斯卡尔算法
sortEdges() 方法：按照边的路径长度，对边进行排序
getPosition() 方法：根据顶点的名称返回其索引值
getEdges() 方法：根据邻接矩阵返回边的数组（EdgeData[]）
getEnd() 方法：返回索引为 i 的顶点的终点，具体做法如下：
ends[i] 拿到索引为 i 的节点的邻接点
令 i = ends[i] ，再通过 ends[i] 拿到其邻接点
直至 ends[i] == 0 时，说明索引为 i 的节点（注意 i 一直在变化）就是终点
kruskal() 方法：利用克鲁斯卡尔算法生成最小生成树：
首选按照边的路径长度，对边进行排序
遍历每条边的顶点，计算两个顶点的终点
如果顶点的终点不重合，则记录当前当前边两个顶点共同的终点
否则，该路径构成回路，啥也不做
再来看看精髓之处，如何记录顶点的终点？ends[endPointOfPoint1] = endPointOfPoint2;
就以上面的例子来说明，现在有 7 个顶点，ends 数组长度为 7 ，用于记录顶点的索引
第一次遍历时 = 2 ，其路径最短 ，记录 E（索引为 4） 的终点为 F（索引为 5 ） ，即 ends[4] = 5
第二次遍历时 = 3 ，其路径最短 ，记录 C（索引为 2） 的终点为 D（索引为 3 ） ，即 ends[2] = 3
第三次遍历时 = 3 ，其路径最短 ，记录 D（索引为 3） 的终点为 E（索引为 4 ） ，即 ends[3] = 4
其实，这有点链表的意思，我们通过 C 能找到 E
C --> D ：顶点 C 的索引为 2 ，令 i = 2 ，i = ends[i] = 3 ，即通过顶点 C 找到了顶点 D（索引为 3 ）
D --> E ：顶点 D 的索引为 3 ，令 i = 3 ，i = ends[i] = 4 ，即通过顶点 D 找到了顶点 E（索引为 4 ）
数组中元素值为零是什么意思？表示该顶点没有邻接点，即孤零零的一个，每个孤立点的终点我们认为就是他自己
class KruskalCase{ private int edgeNum; //边的个数 private char[] vertexs; //顶点数组 private int[][] matrix; //邻接矩阵 //使用 INF 表示两个顶点不能连通 private static final int INF = Integer.MAX_VALUE; // 构造器 public KruskalCase(char[] vertexs, int[][] matrix) { // 初始化顶点数和边的个数 int vlen = vertexs.length; // 初始化顶点, 复制拷贝的方式 this.vertexs = new char[vlen]; for (int i = 0; i < vertexs.length; i++) { this.vertexs[i] = vertexs[i]; } // 初始化边, 使用的是复制拷贝的方式 this.matrix = new int[vlen][vlen]; for (int i = 0; i < vlen; i++) { for (int j = 0; j < vlen; j++) { this.matrix[i][j] = matrix[i][j]; } } // 统计边的条数 for (int i = 0; i < vlen; i++) { for (int j = i + 1; j < vlen; j++) { if (this.matrix[i][j] != INF) { edgeNum++; } } } } //打印邻接矩阵 public void print() { System.out.println("邻接矩阵为: \n"); for (int i = 0; i < vertexs.length; i++) { for (int j = 0; j < vertexs.length; j++) { System.out.printf("%12d", matrix[i][j]); } System.out.println();// 换行 } } /** * 功能：对边进行排序处理, 冒泡排序 * @param edges 边的集合 */ private void sortEdges(EdgeData[] edges) { for (int i = 0; i < edges.length - 1; i++) { for (int j = 0; j < edges.length - 1 - i; j++) { if (edges[j].weight > edges[j + 1].weight) {// 交换 EdgeData tmp = edges[j]; edges[j] = edges[j + 1]; edges[j + 1] = tmp; } } } } /** * * @param ch 顶点的值，比如'A','B' * @return 返回ch顶点对应的下标，如果找不到，返回-1 */ private int getPosition(char ch) { for (int i = 0; i < vertexs.length; i++) { if (vertexs[i] == ch) {// 找到 return i; } } // 找不到,返回-1 return -1; } /** * 功能: 获取图中边，放到EData[] 数组中，后面我们需要遍历该数组 * 是通过matrix 邻接矩阵来获取 * EData[] 形式 [['A','B', 12], ['B','F',7], .....] * @return */ private EdgeData[] getEdges() { int index = 0; EdgeData[] edges = new EdgeData[edgeNum]; for (int i = 0; i < vertexs.length; i++) { for (int j = i + 1; j < vertexs.length; j++) { if (matrix[i][j] != INF) { edges[index++] = new EdgeData(vertexs[i], vertexs[j], matrix[i][j]); } } } return edges; } /** * 功能: 获取下标为i的顶点的终点, 用于后面判断两个顶点的终点是否相同 * @param ends ： 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成 * @param i : 表示传入的顶点对应的下标 * @return 返回的就是 下标为i的这个顶点对应的终点的下标, 一会回头还有来理解 */ private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0] while (ends[i] != 0) { i = ends[i]; } return i; } public void kruskal() { int index = 0; // 表示最后结果数组的索引 int[] ends = new int[vertexs.length]; // 用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点 // 创建结果数组, 保存最后的最小生成树 EdgeData[] rets = new EdgeData[edgeNum]; // 获取图中 所有的边的集合 ， 一共有12边 EdgeData[] edges = getEdges(); System.out.println("排序前，图的边的集合=" + Arrays.toString(edges) + " 共" + edges.length); // 12 // 按照边的权值大小进行排序(从小到大) sortEdges(edges); System.out.println("排序后，图的边的集合=" + Arrays.toString(edges) + " 共" + edges.length); // 12 // 遍历edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入 rets, 否则不能加入 for (int i = 0; i < edgeNum; i++) { // 获取到第i条边的第一个顶点(起点) int p1 = getPosition(edges[i].start); // p1 = 4 // 获取到第i条边的第2个顶点 int p2 = getPosition(edges[i].end); // p2 = 5 // 获取p1这个顶点在已有最小生成树中的终点 int m = getEnd(ends, p1); // m = 4 // 获取p2这个顶点在已有最小生成树中的终点 int n = getEnd(ends, p2); // n = 5 // 是否构成回路 if (m != n) { // 没有构成回路 ends[m] = n; // 设置m 在"已有最小生成树"中的终点 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0] rets[index++] = edges[i]; // 有一条边加入到rets数组 } } // <E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。 // 统计并打印 "最小生成树", 输出 rets System.out.println("最小生成树为"); for (int i = 0; i < index; i++) { System.out.println(rets[i]); } } }
7.5.3、测试代码
- 代码
//使用 INF 表示两个顶点不能连通 private static final int INF = Integer.MAX_VALUE; public static void main(String[] args) { char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; //克鲁斯卡尔算法的邻接矩阵 int matrix[][] = { /*A*//*B*//*C*//*D*//*E*//*F*//*G*/ /*A*/ { 0, 12, INF, INF, INF, 16, 14}, /*B*/ { 12, 0, 10, INF, INF, 7, INF}, /*C*/ { INF, 10, 0, 3, 5, 6, INF}, /*D*/ { INF, INF, 3, 0, 4, INF, INF}, /*E*/ { INF, INF, 5, 4, 0, 2, 8}, /*F*/ { 16, 7, 6, INF, 2, 0, 9}, /*G*/ { 14, INF, INF, INF, 8, 9, 0}}; //大家可以在去测试其它的邻接矩阵，结果都可以得到最小生成树. //创建KruskalCase 对象实例 KruskalCase kruskalCase = new KruskalCase(vertexs, matrix); //输出构建的 kruskalCase.print(); kruskalCase.kruskal(); }
- 程序运行结果
邻接矩阵为: 0 12 2147483647 2147483647 2147483647 16 14 12 0 10 2147483647 2147483647 7 2147483647 2147483647 10 0 3 5 6 2147483647 2147483647 2147483647 3 0 4 2147483647 2147483647 2147483647 2147483647 5 4 0 2 8 16 7 6 2147483647 2 0 9 14 2147483647 2147483647 2147483647 8 9 0 排序前，图的边的集合=[EData [<A, B>= 12], EData [<A, F>= 16], EData [<A, G>= 14], EData [<B, C>= 10], EData [<B, F>= 7], EData [<C, D>= 3], EData [<C, E>= 5], EData [<C, F>= 6], EData [<D, E>= 4], EData [<E, F>= 2], EData [<E, G>= 8], EData [<F, G>= 9]] 共12 排序后，图的边的集合=[EData [<E, F>= 2], EData [<C, D>= 3], EData [<D, E>= 4], EData [<C, E>= 5], EData [<C, F>= 6], EData [<B, F>= 7], EData [<E, G>= 8], EData [<F, G>= 9], EData [<B, C>= 10], EData [<A, B>= 12], EData [<A, G>= 14], EData [<A, F>= 16]] 共12 最小生成树为 EData [<E, F>= 2] EData [<C, D>= 3] EData [<D, E>= 4] EData [<B, F>= 7] EData [<E, G>= 8] EData [<A, B>= 12]
7.6、克鲁斯卡尔算法全部代码
public class KruskalCaseDemo { //使用 INF 表示两个顶点不能连通 private static final int INF = Integer.MAX_VALUE; public static void main(String[] args) { char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; //克鲁斯卡尔算法的邻接矩阵 int matrix[][] = { /*A*//*B*//*C*//*D*//*E*//*F*//*G*/ /*A*/ { 0, 12, INF, INF, INF, 16, 14}, /*B*/ { 12, 0, 10, INF, INF, 7, INF}, /*C*/ { INF, 10, 0, 3, 5, 6, INF}, /*D*/ { INF, INF, 3, 0, 4, INF, INF}, /*E*/ { INF, INF, 5, 4, 0, 2, 8}, /*F*/ { 16, 7, 6, INF, 2, 0, 9}, /*G*/ { 14, INF, INF, INF, 8, 9, 0}}; //大家可以在去测试其它的邻接矩阵，结果都可以得到最小生成树. //创建KruskalCase 对象实例 KruskalCase kruskalCase = new KruskalCase(vertexs, matrix); //输出构建的 kruskalCase.print(); kruskalCase.kruskal(); } } class KruskalCase{ private int edgeNum; //边的个数 private char[] vertexs; //顶点数组 private int[][] matrix; //邻接矩阵 //使用 INF 表示两个顶点不能连通 private static final int INF = Integer.MAX_VALUE; // 构造器 public KruskalCase(char[] vertexs, int[][] matrix) { // 初始化顶点数和边的个数 int vlen = vertexs.length; // 初始化顶点, 复制拷贝的方式 this.vertexs = new char[vlen]; for (int i = 0; i < vertexs.length; i++) { this.vertexs[i] = vertexs[i]; } // 初始化边, 使用的是复制拷贝的方式 this.matrix = new int[vlen][vlen]; for (int i = 0; i < vlen; i++) { for (int j = 0; j < vlen; j++) { this.matrix[i][j] = matrix[i][j]; } } // 统计边的条数 for (int i = 0; i < vlen; i++) { for (int j = i + 1; j < vlen; j++) { if (this.matrix[i][j] != INF) { edgeNum++; } } } } //打印邻接矩阵 public void print() { System.out.println("邻接矩阵为: \n"); for (int i = 0; i < vertexs.length; i++) { for (int j = 0; j < vertexs.length; j++) { System.out.printf("%12d", matrix[i][j]); } System.out.println();// 换行 } } /** * 功能：对边进行排序处理, 冒泡排序 * @param edges 边的集合 */ private void sortEdges(EdgeData[] edges) { for (int i = 0; i < edges.length - 1; i++) { for (int j = 0; j < edges.length - 1 - i; j++) { if (edges[j].weight > edges[j + 1].weight) {// 交换 EdgeData tmp = edges[j]; edges[j] = edges[j + 1]; edges[j + 1] = tmp; } } } } /** * * @param ch 顶点的值，比如'A','B' * @return 返回ch顶点对应的下标，如果找不到，返回-1 */ private int getPosition(char ch) { for (int i = 0; i < vertexs.length; i++) { if (vertexs[i] == ch) {// 找到 return i; } } // 找不到,返回-1 return -1; } /** * 功能: 获取图中边，放到EData[] 数组中，后面我们需要遍历该数组 * 是通过matrix 邻接矩阵来获取 * EData[] 形式 [['A','B', 12], ['B','F',7], .....] * @return */ private EdgeData[] getEdges() { int index = 0; EdgeData[] edges = new EdgeData[edgeNum]; for (int i = 0; i < vertexs.length; i++) { for (int j = i + 1; j < vertexs.length; j++) { if (matrix[i][j] != INF) { edges[index++] = new EdgeData(vertexs[i], vertexs[j], matrix[i][j]); } } } return edges; } /** * 功能: 获取下标为i的顶点的终点, 用于后面判断两个顶点的终点是否相同 * @param ends ： 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成 * @param i : 表示传入的顶点对应的下标 * @return 返回的就是 下标为i的这个顶点对应的终点的下标, 一会回头还有来理解 */ private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0] while (ends[i] != 0) { i = ends[i]; } return i; } public void kruskal() { int index = 0; // 表示最后结果数组的索引 int[] ends = new int[vertexs.length]; // 用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点 // 创建结果数组, 保存最后的最小生成树 EdgeData[] rets = new EdgeData[edgeNum]; // 获取图中 所有的边的集合 ， 一共有12边 EdgeData[] edges = getEdges(); System.out.println("排序前，图的边的集合=" + Arrays.toString(edges) + " 共" + edges.length); // 12 // 按照边的权值大小进行排序(从小到大) sortEdges(edges); System.out.println("排序后，图的边的集合=" + Arrays.toString(edges) + " 共" + edges.length); // 12 // 遍历edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入 rets, 否则不能加入 for (int i = 0; i < edgeNum; i++) { // 获取到第i条边的第一个顶点(起点) int point1 = getPosition(edges[i].start); // point1 = 4 // 获取到第i条边的第2个顶点 int point2 = getPosition(edges[i].end); // point2 = 5 // 获取p1这个顶点在已有最小生成树中的终点 int endPointOfPoint1 = getEnd(ends, point1); // endPointOfPoint1 = 4 // 获取p2这个顶点在已有最小生成树中的终点 int endPointOfPoint2 = getEnd(ends, point2); // endPointOfPoint2 = 5 // 是否构成回路 if (endPointOfPoint1 != endPointOfPoint2) { // 没有构成回路 ends[endPointOfPoint1] = endPointOfPoint2; // 设置m 在"已有最小生成树"中的终点 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0] rets[index++] = edges[i]; // 有一条边加入到rets数组 } } // <E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。 // 统计并打印 "最小生成树", 输出 rets System.out.println("最小生成树为"); for (int i = 0; i < index; i++) { System.out.println(rets[i]); } } } //创建一个类EData ，它的对象实例就表示一条边 class EdgeData { char start; // 边的一个点 char end; // 边的另外一个点 int weight; // 边的权值 // 构造器 public EdgeData(char start, char end, int weight) { this.start = start; this.end = end; this.weight = weight; } // 重写toString, 便于输出边信息 @Override public String toString() { return "EData [<" + start + ", " + end + ">= " + weight + "]"; } }
8、迪杰斯特拉算法
8.1、应用场景(最短路径问题)
看一个应用场景和问题：
战争时期，胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从G点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄
各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里
问：如何计算出G村庄到 其它各个村庄的最短距离?
如果从其它点出发到各个点的最短距离又是多少?
8.2、迪杰斯特拉算法介绍
- 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
8.3、迪杰斯特拉算法过程
两个重要的集合（辅助实现迪杰斯特拉算法）：
设置出发顶点为v，顶点集合V{v1,v2,vi…}，
v到V中各顶点的距离构成距离集合Dis，Dis{d1,d2,di…}，Dis集合记录着v到图中各顶点的距离(到自身可以看作0，v到vi距离对应为di)
算法流程
从Dis中选择值最小的di并移出Dis集合，同时移出V集合中对应的顶点vi，此时的v到vi即为最短路径
更新Dis集合，更新规则为：比较v到V集合中顶点的距离值，与v通过vi到V集合中顶点的距离值，保留值较小的一个(同时也应该更新顶点的前驱节点为vi，表明是通过vi到达的)
重复执行两步骤，直到最短路径顶点为目标顶点即可结束
8.4、迪杰斯特拉算法图解
- 在地杰斯特拉算法中，有三个非常重要的数组
class Visited_vertex{//已访问顶点集合 public int[] already_arr; //记录各个顶点是否访问过 1表示访问过,0未访问,会动态更新 public int[] dis;//记录出发顶点到其他所有顶点的距离,比如G为出发顶点，就会记录G到其它顶点的距离，会动态更新，求的最短距离就会存放到dis public int[] pre_visited;//每个下标对应的值为前一个顶点下标, 会动态更新 }
以下面这个图为例，该图一共有 { A, B, C, D, E ,F, G } 七个顶点，比如说需要从 G --> C ，G --> D 的最短路径
初始情况：
already_arr = { 0, 0, 0, 0, 0, 0, 0 } ，表示当前还未访问过任何顶点
dis = { N, N, N, N, N, N, N } ，N 表示出发顶点与目标顶点的距离无穷大，因为后面程序中需要选取最小值，所以初始时，将 dis 全部元素设置成无穷大，很合理
pre_visited = { 0, 0, 0, 0, 0, 0, 0 } ，初始值默认为 0 ，我感觉有歧义啊。。。我感觉初始值应该为 -1
以 G 为出发顶点
already_arr = { 0, 0, 0, 0, 0, 0, 1 } ，表示顶点 G 已被访问过
dis = { N, N, N, N, N, N, 0 } ，顶点 G 就是出发顶点，距离为 0
pre_visited = { 0, 0, 0, 0, 0, 0, 0 } ，出发顶点没有前一个顶点
以 G 点为初始顶点，尝试访问其邻接点 { A, B, E, F } ，并找出下一步路径最短的走法
already_arr = { 0, 0, 0, 0, 0, 0, 1 } ，现在是在尝试访问顶点 G 的邻接点，并不是真正在访问，所以不能将顶点 { A, B, E, F } 标记为已访问
dis = { 2, 3, N, N, 4, 6, 0 } ，出发顶点 G --> A 的距离最短，并且顶点 A 并没有被访问过，可以选取顶点 A作为下一次的初始顶点
pre_visited = { 6, 6, 0, 0, 6, 6, 0 } ，标记顶点 { A, B, E, F } 的前一个顶点为 G
此时在所有路径中，G --> A 路径最短，并且顶点 A 没有被访问过，所以 A 点为初始顶点，尝试访问其邻接点 { B, C, G } ，并找出下一步路径最短的走法
already_arr = { 1, 0, 0, 0, 0, 0, 1 } ，访问过顶点 A 之后，将其标记为已访问
分析 dis 数组的赋值流程：
由于 G 点已经被访问过了，所以不再访问 G 点
尝试走 G --> A --> B 这条路，距离为 2 + 5 = 7 ，但是之前有条路 G --> B 距离为 3 ，所以不做改变
尝试走 G --> A --> C 这条路，距离为 2 + 7 = 9 ，比之前的距离小，选择当前走法，标记出发点 G 到顶点 C 距离为 9 ，标记顶点 C 的前一个节点为顶点 A
综上分析： dis = { 2, 3, 9, N, 4, 6, 0 }
pre_visited = { 6, 6, 0, 0, 6, 6, 0 } ，标记顶点C 的前一个顶点为 A
此时在所有路径中，G --> B 路径最短，并且顶点 B 没有被访问过，所以 B 点为初始顶点，尝试访问其邻接点 { A, D, G } ，并找出下一步路径最短的走法
already_arr = { 1, 1, 0, 0, 0, 0, 1 } ，访问过顶点 B 之后，将其标记为已访问
分析 dis 数组的赋值流程：
由于 A 点已经被访问过了，所以不再访问 A 点
为什么不再访问顶点 A ？那万一 G --> B --> A 的距离小于 G --> A 的距离呢？
如果 length(G --> B --> A) < length(G --> A)，那肯定就说明 length(G --> B) < length(G --> A)
那肯定要先走顶点 B ，先走了顶点 A 即说明出发点到顶点 A 的距离是所有路径中最短的那条，所以无需再访问顶点 A
尝试走 G --> B --> D 这条路，距离为 3 + 9 = 12 ，目前来说，出发点距离顶点 D 的最短路径为 12，标记顶点 D 的前一个节点为顶点 B
由于 G 点已经被访问过了，所以不再访问 G 点
综上分析： dis = { 2, 3, 9, 12, 4, 6, 0 }
pre_visited = { 6, 6, 0, 1, 6, 6, 0 } ，标记顶点 D 的前一个节点为顶点 B
此时在所有路径中，G --> E 路径最短，并且顶点 E 没有被访问过，所以 E 点为初始顶点，尝试访问其邻接点 { C, F, G } ，并找出下一步路径最短的走法
already_arr = { 1, 1, 0, 0, 1, 0, 1 } ，访问过顶点 E 之后，将其标记为已访问
分析 dis 数组的赋值流程：
尝试走 G --> E --> C 这条路，距离为 4 + 8 = 12 ，但是之前有条路 G --> A --> C 距离为 8 ，所以不做改变
尝试走 G --> E --> F 这条路，距离为 4 + 5 = 9 ，但是之前有条路 G --> F 距离为 6 ，所以不做改变
由于 G 点已经被访问过了，所以不再访问 G 点
综上分析： dis = { 2, 3, 9, 12, 4, 6, 0 }
pre_visited = { 6, 6, 0, 1, 6, 6, 0 } ，本次未找到路径举例比上次短的，不做修改
此时在所有路径中，G --> F 路径最短，并且顶点 F 没有被访问过，所以 F 点为初始顶点，尝试访问其邻接点 { E, D, G } ，并找出下一步路径最短的走法
already_arr = { 1, 1, 0, 0, 1, 1, 1 } ，访问过顶点 E 之后，将其标记为已访问
分析 dis 数组的赋值流程：
尝试走 G --> F --> D 这条路，距离为 6 + 4 = 10 ，之前有条路 G --> B --> D 距离为 12 ，这次距离比上次短，选择当前走法，标记出发点 G 到顶点 D 距离为 10 ，标记顶点 D 的前一个节点为顶点 F
由于 E 点已经被访问过了，所以不再访问 E 点
由于 G 点已经被访问过了，所以不再访问 G 点
综上分析： dis = { 2, 3, 9, 10, 4, 6, 0 }
pre_visited = { 6, 6, 0, 5, 6, 6, 0 } ，标记顶点 D 的前一个节点为顶点 F
- 此时在所有路径中，G --> A --> C 路径最短，并且顶点 C 没有被访问过，所以 C 点为初始顶点，尝试访问其邻接点 { A, E } ，发现顶点 { A, E } 均被访问过，说明走到的图的最深处，将顶点 C 标记已访问即可，其他两个数组不作处理
- 此时在所有路径中，G --> F --> D 路径最短，并且顶点 D 没有被访问过，所以 D 点为初始顶点，尝试访问其邻接点 { B, F } ，发现顶点 { B, F } 均被访问过，说明走到的图的最深处，将顶点 F 标记已访问即可，其他两个数组不作处理
- 至此，图的广度优先遍历已经完成
- 假如说有 n 个顶点，来想想循环的结束条件是啥？想想前面的最小生成树，n 个节点最少 n - 1 条边才能将所有顶点连通，所以图的广度优先遍历，最多遍历 n - 1 次，就能将出发顶点和最远的顶点连通
- 我把图竖着画，是不是就要好理解一些，广度优先可以这样理解：以出发顶点为根节点，将图分成一层一层的结构（就像树那样），禁止产生回溯（一条路径不能走两遍），然后在每层中选取距离最短的路径，这样得到的路径就是最短路径
8.5、迪杰斯特拉算法实现
8.5.1、图的定义
VisitedVertex 类用于存储上面所说的三个重要数组：already_arr、pre_visited、dis
VisitedVertex 类中还提供了一些方法：
isVisited() 方法：判断该顶点是否被访问过
updateDis() 方法：更新出发顶点距离当前顶点的距离
updatePre() 方法：更新当前顶点的前一个节点
getDis() 方法：获取当前顶点与出发顶点之间的距离
findNextStartPoint() 方法：寻找下一个初始顶点（当前还未被访问过、并且与出发顶点距离最短的顶点）
showArrays() 方法：打印三个重要数组
// 已访问顶点集合 class VisitedVertex { // 记录各个顶点是否访问过 1表示访问过,0未访问,会动态更新 public int[] already_arr; // 每个下标对应的值为前一个顶点下标, 会动态更新 public int[] pre_visited; // 记录出发顶点到其他所有顶点的距离,比如G为出发顶点，就会记录G到其它顶点的距离，会动态更新，求的最短距离就会存放到dis public int[] dis; //构造器 /** * * @param length :表示顶点的个数 * @param index: 出发顶点对应的下标, 比如G顶点，下标就是6 */ public VisitedVertex(int length, int index) { this.already_arr = new int[length]; this.pre_visited = new int[length]; this.dis = new int[length]; // 初始化 dis数组 Arrays.fill(dis, 65535); this.dis[index] = 0;// 设置出发顶点的访问距离为0 this.already_arr[index] = 1; // 设置出发顶点被访问过 } /** * 功能: 判断index顶点是否被访问过 * @param index * @return 如果访问过，就返回true, 否则访问false */ public boolean isVisited(int index) { return already_arr[index] == 1; } /** * 功能: 更新出发顶点到index顶点的距离 * @param index * @param len */ public void updateDis(int index, int len) { dis[index] = len; } /** * 功能: 更新pre这个顶点的前驱顶点为index顶点 * @param pre * @param index */ public void updatePre(int pre, int index) { pre_visited[pre] = index; } /** * 功能:返回出发顶点到index顶点的距离 * @param index */ public int getDis(int index) { return dis[index]; } /** * 继续选择并返回新的访问顶点， 比如这里的G 完后，就是 A点作为新的访问顶点(注意不是出发顶点) * @return */ public int findNextStartPoint() { int min = 65535, index = 0; for (int i = 0; i < already_arr.length; i++) { if (already_arr[i] == 0 && dis[i] < min) { min = dis[i]; index = i; } } // 更新 index 顶点被访问过 already_arr[index] = 1; return index; } //显示最后的结果 //即将三个数组的情况输出 public void showArrays() { System.out.println("核心数组的值如下："); // 输出already_arr for (int i : already_arr) { System.out.print(i + " "); } System.out.println(); // 输出dis for (int i : dis) { System.out.print(i + " "); } System.out.println(); // 输出pre_visited for (int i : pre_visited) { System.out.print(i + " "); } System.out.println(); // 为了好看最后的最短距离，我们处理 char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' }; int count = 0; for (int i : dis) { if (i != 65535) { System.out.print(vertex[count] + "(" + i + ") "); } else { System.out.print("N "); } count++; } System.out.println(); System.out.println(); } }
8.5.2、迪杰斯特拉算法
- 迪杰斯特拉算法的流程：
- 计算初始顶点的邻接点与出发顶点的最短距离，记录在 dis 数组中，并标记当前初始顶点已经被访问
- 寻找下一个与出发顶点距离最近，并且没有访问过的顶点，作为下一次的初始定点
- 如此返回
- 上述操作执行 vertex.length - 1 次，就能保证求得最短路径
class Graph { private char[] vertex; // 顶点数组 private int[][] matrix; // 邻接矩阵 private VisitedVertex vv; // 已经访问的顶点的集合 // 构造器 public Graph(char[] vertex, int[][] matrix) { this.vertex = vertex; this.matrix = matrix; } // 显示结果 public void showDijkstra() { vv.showArrays(); } // 显示图 public void showGraph() { for (int[] link : matrix) { for (int i : link) { System.out.printf("%8d", i); } System.out.println(); } } //迪杰斯特拉算法实现 /** * * @param index 表示出发顶点对应的下标 */ public void dsj(int index) { vv = new VisitedVertex(vertex.length, index); update(index);// 更新index顶点到周围顶点的距离和前驱顶点 vv.showArrays(); for (int j = 1; j < vertex.length; j++) { index = vv.findNextStartPoint();// 选择并返回新的访问顶点 update(index); // 更新index顶点到周围顶点的距离和前驱顶点 vv.showArrays(); } } // 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点, private void update(int index) { int len = 0; // 根据遍历我们的邻接矩阵的 matrix[index]行 for (int j = 0; j < matrix[index].length; j++) { // len 含义是 : 出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和 len = vv.getDis(index) + matrix[index][j]; // 如果j顶点没有被访问过，并且 len 小于出发顶点到j顶点的距离，就需要更新 if (!vv.isVisited(j) && len < vv.getDis(j)) { vv.updatePre(j, index); // 更新j顶点的前驱为index顶点 vv.updateDis(j, len); // 更新出发顶点到j顶点的距离 } } } }
8.5.3、代码测试
- 代码
public static void main(String[] args) { char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' }; // 邻接矩阵 int[][] matrix = new int[vertex.length][vertex.length]; final int N = 65535;// 表示不可以连接 matrix[0] = new int[] { N, 5, 7, N, N, N, 2 }; matrix[1] = new int[] { 5, N, N, 9, N, N, 3 }; matrix[2] = new int[] { 7, N, N, N, 8, N, N }; matrix[3] = new int[] { N, 9, N, N, N, 4, N }; matrix[4] = new int[] { N, N, 8, N, N, 5, 4 }; matrix[5] = new int[] { N, N, N, 4, 5, N, 6 }; matrix[6] = new int[] { 2, 3, N, N, 4, 6, N }; // 创建 Graph对象 Graph graph = new Graph(vertex, matrix); // 测试, 看看图的邻接矩阵是否ok graph.showGraph(); // 测试迪杰斯特拉算法 graph.dsj(6);// G }
- 程序运行结果
65535 5 7 65535 65535 65535 2 5 65535 65535 9 65535 65535 3 7 65535 65535 65535 8 65535 65535 65535 9 65535 65535 65535 4 65535 65535 65535 8 65535 65535 5 4 65535 65535 65535 4 5 65535 6 2 3 65535 65535 4 6 65535 核心数组的值如下： 0 0 0 0 0 0 1 2 3 65535 65535 4 6 0 6 6 0 0 6 6 0 A(2) B(3) N N E(4) F(6) G(0) 核心数组的值如下： 1 0 0 0 0 0 1 2 3 9 65535 4 6 0 6 6 0 0 6 6 0 A(2) B(3) C(9) N E(4) F(6) G(0) 核心数组的值如下： 1 1 0 0 0 0 1 2 3 9 12 4 6 0 6 6 0 1 6 6 0 A(2) B(3) C(9) D(12) E(4) F(6) G(0) 核心数组的值如下： 1 1 0 0 1 0 1 2 3 9 12 4 6 0 6 6 0 1 6 6 0 A(2) B(3) C(9) D(12) E(4) F(6) G(0) 核心数组的值如下： 1 1 0 0 1 1 1 2 3 9 10 4 6 0 6 6 0 5 6 6 0 A(2) B(3) C(9) D(10) E(4) F(6) G(0) 核心数组的值如下： 1 1 1 0 1 1 1 2 3 9 10 4 6 0 6 6 0 5 6 6 0 A(2) B(3) C(9) D(10) E(4) F(6) G(0) 核心数组的值如下： 1 1 1 1 1 1 1 2 3 9 10 4 6 0 6 6 0 5 6 6 0 A(2) B(3) C(9) D(10) E(4) F(6) G(0)
8.6、迪杰斯特拉算法全部代码
public class DijkstraAlgorithm { public static void main(String[] args) { char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' }; // 邻接矩阵 int[][] matrix = new int[vertex.length][vertex.length]; final int N = 65535;// 表示不可以连接 matrix[0] = new int[] { N, 5, 7, N, N, N, 2 }; matrix[1] = new int[] { 5, N, N, 9, N, N, 3 }; matrix[2] = new int[] { 7, N, N, N, 8, N, N }; matrix[3] = new int[] { N, 9, N, N, N, 4, N }; matrix[4] = new int[] { N, N, 8, N, N, 5, 4 }; matrix[5] = new int[] { N, N, N, 4, 5, N, 6 }; matrix[6] = new int[] { 2, 3, N, N, 4, 6, N }; // 创建 Graph对象 Graph graph = new Graph(vertex, matrix); // 测试, 看看图的邻接矩阵是否ok graph.showGraph(); // 测试迪杰斯特拉算法 graph.dsj(6);// G } } class Graph { private char[] vertex; // 顶点数组 private int[][] matrix; // 邻接矩阵 private VisitedVertex vv; // 已经访问的顶点的集合 // 构造器 public Graph(char[] vertex, int[][] matrix) { this.vertex = vertex; this.matrix = matrix; } // 显示结果 public void showDijkstra() { vv.showArrays(); } // 显示图 public void showGraph() { for (int[] link : matrix) { for (int i : link) { System.out.printf("%8d", i); } System.out.println(); } } //迪杰斯特拉算法实现 /** * * @param index 表示出发顶点对应的下标 */ public void dsj(int index) { vv = new VisitedVertex(vertex.length, index); update(index);// 更新index顶点到周围顶点的距离和前驱顶点 vv.showArrays(); for (int j = 1; j < vertex.length; j++) { index = vv.findNextStartPoint();// 选择并返回新的访问顶点 update(index); // 更新index顶点到周围顶点的距离和前驱顶点 vv.showArrays(); } } // 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点, private void update(int index) { int len = 0; // 根据遍历我们的邻接矩阵的 matrix[index]行 for (int j = 0; j < matrix[index].length; j++) { // len 含义是 : 出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和 len = vv.getDis(index) + matrix[index][j]; // 如果j顶点没有被访问过，并且 len 小于出发顶点到j顶点的距离，就需要更新 if (!vv.isVisited(j) && len < vv.getDis(j)) { vv.updatePre(j, index); // 更新j顶点的前驱为index顶点 vv.updateDis(j, len); // 更新出发顶点到j顶点的距离 } } } } // 已访问顶点集合 class VisitedVertex { // 记录各个顶点是否访问过 1表示访问过,0未访问,会动态更新 public int[] already_arr; // 每个下标对应的值为前一个顶点下标, 会动态更新 public int[] pre_visited; // 记录出发顶点到其他所有顶点的距离,比如G为出发顶点，就会记录G到其它顶点的距离，会动态更新，求的最短距离就会存放到dis public int[] dis; //构造器 /** * * @param length :表示顶点的个数 * @param index: 出发顶点对应的下标, 比如G顶点，下标就是6 */ public VisitedVertex(int length, int index) { this.already_arr = new int[length]; this.pre_visited = new int[length]; this.dis = new int[length]; // 初始化 dis数组 Arrays.fill(dis, 65535); this.dis[index] = 0;// 设置出发顶点的访问距离为0 this.already_arr[index] = 1; // 设置出发顶点被访问过 } /** * 功能: 判断index顶点是否被访问过 * @param index * @return 如果访问过，就返回true, 否则访问false */ public boolean isVisited(int index) { return already_arr[index] == 1; } /** * 功能: 更新出发顶点到index顶点的距离 * @param index * @param len */ public void updateDis(int index, int len) { dis[index] = len; } /** * 功能: 更新pre这个顶点的前驱顶点为index顶点 * @param pre * @param index */ public void updatePre(int pre, int index) { pre_visited[pre] = index; } /** * 功能:返回出发顶点到index顶点的距离 * @param index */ public int getDis(int index) { return dis[index]; } /** * 继续选择并返回新的访问顶点， 比如这里的G 完后，就是 A点作为新的访问顶点(注意不是出发顶点) * @return */ public int findNextStartPoint() { int min = 65535, index = 0; for (int i = 0; i < already_arr.length; i++) { if (already_arr[i] == 0 && dis[i] < min) { min = dis[i]; index = i; } } // 更新 index 顶点被访问过 already_arr[index] = 1; return index; } //显示最后的结果 //即将三个数组的情况输出 public void showArrays() { System.out.println("核心数组的值如下："); // 输出already_arr for (int i : already_arr) { System.out.print(i + " "); } System.out.println(); // 输出dis for (int i : dis) { System.out.print(i + " "); } System.out.println(); // 输出pre_visited for (int i : pre_visited) { System.out.print(i + " "); } System.out.println(); // 为了好看最后的最短距离，我们处理 char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' }; int count = 0; for (int i : dis) { if (i != 65535) { System.out.print(vertex[count] + "(" + i + ") "); } else { System.out.print("N "); } count++; } System.out.println(); System.out.println(); } }
9、弗洛伊德算法
9.1、应用场景(最短路径问题)
- 胜利乡有7个村庄(A, B, C, D, E, F, G)
- 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里
- 问：如何计算出各村庄到其它各村庄的最短距离?
9.2、弗洛伊德算法介绍
和Dijkstra算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名
弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径
迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径。
弗洛伊德算法 VS 迪杰斯特拉算法：
迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点的最短路径；
弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。
9.3、弗洛伊德算法分析
设置顶点vi到顶点vk的最短路径已知为Lik，顶点vk到vj的最短路径已知为Lkj，顶点vi到vj的路径为Lij，则vi到vj的最短路径为：min((Lik+Lkj),Lij)，vk的取值为图中所有顶点，则可获得vi到vj的最短路径
至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj，也是以同样的方式获得
9.4、弗洛伊德算法图解
弗洛伊德算法中有两个核心的二维数组：
dis ：二维数组，记录顶点 i 到顶点 j 的距离： dis[i][j] 或 dis[j][i]
pre ：二维数组，记录顶点 i 和顶点 j 的前驱顶点：pre[i][j] 或 pre[j][i]
初始状态下，图的邻接矩阵如下和前驱顶点
第一轮循环中，以 A 作为中间顶点，将把 A 作为中间顶点的所有情况进行遍历，更新距离表和前驱关系
C --> A --> G ：路径长度为 9 ，顶点 B 和 G 的前驱结点为 A
C --> A --> B ：路径长度为 12 ，顶点 C 和 B 的前驱结点为 A
G --> A --> B ：路径长度为 7 ，顶点 G 和 B 的前驱结点为 A
第二轮循环中，以 B 作为中间顶点，将把 B 作为中间顶点的所有情况进行遍历，更新距离表和前驱关系
以此类推 … ，更换中间顶点，循环执行操作，直到所有顶点都作为中间顶点更新后，计算结束
为什么这样就能求出图中各个顶点到其他顶点的最短路径？这样来想，我们求出了每个顶点作为其他顶点的中间顶点的最短路径，那此时距离表中的路径值就是各个顶点到其他顶点的最短路径
9.5、弗洛伊德算法编码思路
- 由上述分析可知，需要三层 for 循环，所以弗洛伊德算法的时间复杂度为 O(n3)
for 顶点 A To 顶点 G { // 更换中间顶点 for 顶点 A To 顶点 G { // 更换起始顶点 for 顶点 A To 顶点 G { // 更换结束顶点 if(距离比上次更短){ //起始顶点到结束顶点距离比上次更短 更新距离表 更新前驱顶点表 } } } }
9.6、弗洛伊德算法代码实现
9.6.1、编写弗洛伊德算法
- 编写弗洛伊德算法
// 创建图 class Graph { private char[] vertex; // 存放顶点的数组 private int[][] dis; // 保存，从各个顶点出发到其它顶点的距离，最后的结果，也是保留在该数组 private int[][] pre;// 保存到达目标顶点的前驱顶点 // 构造器 /** * * @param length 大小 * @param matrix 邻接矩阵 * @param vertex 顶点数组 */ public Graph(int length, int[][] matrix, char[] vertex) { this.vertex = vertex; this.dis = matrix; this.pre = new int[length][length]; // 对pre数组初始化, 注意存放的是前驱顶点的下标 for (int i = 0; i < length; i++) { Arrays.fill(pre[i], i); } } // 弗洛伊德算法, 比较容易理解，而且容易实现 public void floyd() { int len = 0; // 变量保存距离 // 对中间顶点遍历， k 就是中间顶点的下标 ，[A, B, C, D, E, F, G] 走一遍 for (int k = 0; k < dis.length; k++) { // 从i顶点开始出发，[A, B, C, D, E, F, G] 走一遍 for (int i = 0; i < dis.length; i++) { // 到达j顶点，[A, B, C, D, E, F, G] 走一遍 for (int j = 0; j < dis.length; j++) { len = dis[i][k] + dis[k][j];// => 求出从i 顶点出发，经过 k中间顶点，到达 j 顶点距离 if (len < dis[i][j]) {// 如果len小于 dis[i][j] dis[i][j] = len;// 更新距离 pre[i][j] = pre[k][j];// 更新前驱顶点 } } } } } // 显示pre数组和dis数组 public void show() { for (int k = 0; k < dis.length; k++) { // 先将pre数组输出的一行 for (int i = 0; i < dis.length; i++) { System.out.print(vertex[pre[k][i]] + " "); } System.out.println(); // 输出dis数组的一行数据 for (int i = 0; i < dis.length; i++) { System.out.print("(" + vertex[k] + "到" + vertex[i] + "的最短路径是" + dis[k][i] + ") "); } System.out.println(); System.out.println(); } } }
9.6.2、测试代码
- 代码
public static void main(String[] args) { // 测试看看图是否创建成功 char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' }; // 创建邻接矩阵 int[][] matrix = new int[vertex.length][vertex.length]; final int N = 65535; matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 }; matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 }; matrix[2] = new int[] { 7, N, 0, N, 8, N, N }; matrix[3] = new int[] { N, 9, N, 0, N, 4, N }; matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 }; matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 }; matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 }; // 创建 Graph 对象 Graph graph = new Graph(vertex.length, matrix, vertex); // 调用弗洛伊德算法 graph.floyd(); graph.show(); }
- 程序运行结果
A A A F G G A (A到A的最短路径是0) (A到B的最短路径是5) (A到C的最短路径是7) (A到D的最短路径是12) (A到E的最短路径是6) (A到F的最短路径是8) (A到G的最短路径是2) B B A B G G B (B到A的最短路径是5) (B到B的最短路径是0) (B到C的最短路径是12) (B到D的最短路径是9) (B到E的最短路径是7) (B到F的最短路径是9) (B到G的最短路径是3) C A C F C E A (C到A的最短路径是7) (C到B的最短路径是12) (C到C的最短路径是0) (C到D的最短路径是17) (C到E的最短路径是8) (C到F的最短路径是13) (C到G的最短路径是9) G D E D F D F (D到A的最短路径是12) (D到B的最短路径是9) (D到C的最短路径是17) (D到D的最短路径是0) (D到E的最短路径是9) (D到F的最短路径是4) (D到G的最短路径是10) G G E F E E E (E到A的最短路径是6) (E到B的最短路径是7) (E到C的最短路径是8) (E到D的最短路径是9) (E到E的最短路径是0) (E到F的最短路径是5) (E到G的最短路径是4) G G E F F F F (F到A的最短路径是8) (F到B的最短路径是9) (F到C的最短路径是13) (F到D的最短路径是4) (F到E的最短路径是5) (F到F的最短路径是0) (F到G的最短路径是6) G G A F G G G (G到A的最短路径是2) (G到B的最短路径是3) (G到C的最短路径是9) (G到D的最短路径是10) (G到E的最短路径是4) (G到F的最短路径是6) (G到G的最短路径是0)
10、马踏棋盘算法
10.1、马踏棋盘游戏
马踏棋盘算法也被称为骑士周游问题
将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格
游戏演示: http://www.4399.com/flash/146267_2.htm
10.2、马踏棋盘代码思路
马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。为啥是图的深度优先搜索？
如果使用回溯（就是深度优先搜索）来解决，假如马儿踏了53个点，如图：走到了第53个，坐标(1, 0)，发现已经走到尽头，没办法，那就只能回退了，查看其他的路径，就在棋盘上不停的回溯……
可以使用前面的游戏来验证算法是否正确。
编码思路
创建棋盘 chessBoard，是一个二维数组
将当前位置设置为已经访问，然后根据当前位置，计算马儿还能走哪些位置，并放入到一个集合中(ArrayList)，下一步可选位置最多有8个位置， 每走一步，就使用 step+1
遍历ArrayList中存放的所有位置，看看哪个可以走通，如果走通，就继续，走不通，就回溯
判断马儿是否完成了任务，使用 step 和应该走的步数比较 ， 如果没有达到数量，则表示没有完成任务，将整个棋盘置 0
注意：马儿不同的走法（策略），会得到不同的结果，效率也会有影响(优化)
10.3、马踏棋盘代码实现
如下是马踏棋盘算法代码实现，在递归和回溯的过程中，如何判断马儿是否已经完成了任务？如下两个条件满足其一即可：
已经走够了步数
完成标志位 finished == true
如果回溯过程中，发现马儿并没有完成任务，则说明此次递归过程失败，应该棋盘该位置清零，并且标记当前位置并未被访问过
public class HorseChessboard { private static int X; // 棋盘的列数 private static int Y; // 棋盘的行数 // 创建一个数组，标记棋盘的各个位置是否被访问过 private static boolean visited[]; // 使用一个属性，标记是否棋盘的所有位置都被访问 private static boolean finished; // 如果为true,表示成功 public static void main(String[] args) { System.out.println("骑士周游算法，开始运行~~"); // 测试骑士周游算法是否正确 X = 8; Y = 8; int row = 1; // 马儿初始位置的行，从1开始编号 int column = 1; // 马儿初始位置的列，从1开始编号 // 创建棋盘 int[][] chessboard = new int[X][Y]; visited = new boolean[X * Y];// 初始值都是false // 测试一下耗时 long start = System.currentTimeMillis(); traversalChessboard(chessboard, row - 1, column - 1, 1); long end = System.currentTimeMillis(); System.out.println("共耗时: " + (end - start) + " 毫秒"); // 输出棋盘的最后情况 for (int[] rows : chessboard) { for (int step : rows) { System.out.print(step + "\t"); } System.out.println(); } } /** * 功能： 根据当前位置(Point对象)，计算马儿还能走哪些位置(Point)，并放入到一个集合中(ArrayList), 最多有8个位置 * @param curPoint * @return */ public static ArrayList<Point> next(Point curPoint) { // 创建一个ArrayList ArrayList<Point> ps = new ArrayList<Point>(); // 创建一个Point Point p1 = new Point(); // 表示马儿可以走5这个位置 if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) { ps.add(new Point(p1)); } // 判断马儿可以走6这个位置 if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) { ps.add(new Point(p1)); } // 判断马儿可以走7这个位置 if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) { ps.add(new Point(p1)); } // 判断马儿可以走0这个位置 if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) { ps.add(new Point(p1)); } // 判断马儿可以走1这个位置 if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) { ps.add(new Point(p1)); } // 判断马儿可以走2这个位置 if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) { ps.add(new Point(p1)); } // 判断马儿可以走3这个位置 if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) { ps.add(new Point(p1)); } // 判断马儿可以走4这个位置 if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) { ps.add(new Point(p1)); } return ps; } /** * 完成骑士周游问题的算法 * @param chessboard 棋盘 * @param row 马儿当前的位置的行 从0开始 * @param column 马儿当前的位置的列 从0开始 * @param step 是第几步 ,初始位置就是第1步 */ public static void traversalChessboard(int[][] chessboard, int row, int column, int step) { chessboard[row][column] = step; //row = 4 X = 8 column = 4 = 4 * 8 + 4 = 36 visited[row * X + column] = true; //标记该位置已经访问 //获取当前位置可以走的下一个位置的集合 ArrayList<Point> ps = next(new Point(column, row)); //遍历 ps while(!ps.isEmpty()) { Point p = ps.remove(0);//取出下一个可以走的位置 //判断该点是否已经访问过 if(!visited[p.y * X + p.x]) {//说明还没有访问过 traversalChessboard(chessboard, p.y, p.x, step + 1); } } //判断马儿是否完成了任务，使用 step 和应该走的步数比较 ， //如果没有达到数量，则表示没有完成任务，将棋盘该位置设置为0 //说明: step < X * Y 成立的情况有两种 //1. 棋盘到目前位置,仍然没有走完 //2. 棋盘处于一个回溯过程 if(step < X * Y && !finished ) { chessboard[row][column] = 0; visited[row * X + column] = false; } else { finished = true; } } }
- 程序运行结果
骑士周游算法，开始运行~~ 共耗时: 27099 毫秒 1 8 11 16 3 18 13 64 10 27 2 7 12 15 4 19 53 24 9 28 17 6 63 14 26 39 52 23 62 29 20 5 43 54 25 38 51 22 33 30 40 57 42 61 32 35 48 21 55 44 59 50 37 46 31 34 58 41 56 45 60 49 36 47
10.4、马踏棋盘代码优化
上面的算法那由于回溯过程过多，算法用时长，我们使用贪心算法（greedyalgorithm）进行优化。
马儿的下一步可能有很多种选择，我们应该怎么选择其下一步？
选择下一步的下一步走法尽可能少的，哈哈，我都给自己说晕了，这样尽可能减少递归的回溯，可明显提高算法速度
ArrayList ps = next(new Point(column, row)); ps 是当前步骤的下一步走法的集合，我们需要对 ps 中所有的 Point 的下一步的所有集合的数目，进行非递减排序，就 ok 了
public class HorseChessboard { private static int X; // 棋盘的列数 private static int Y; // 棋盘的行数 // 创建一个数组，标记棋盘的各个位置是否被访问过 private static boolean visited[]; // 使用一个属性，标记是否棋盘的所有位置都被访问 private static boolean finished; // 如果为true,表示成功 public static void main(String[] args) { System.out.println("骑士周游算法，开始运行~~"); // 测试骑士周游算法是否正确 X = 8; Y = 8; int row = 1; // 马儿初始位置的行，从1开始编号 int column = 1; // 马儿初始位置的列，从1开始编号 // 创建棋盘 int[][] chessboard = new int[X][Y]; visited = new boolean[X * Y];// 初始值都是false // 测试一下耗时 long start = System.currentTimeMillis(); traversalChessboard(chessboard, row - 1, column - 1, 1); long end = System.currentTimeMillis(); System.out.println("共耗时: " + (end - start) + " 毫秒"); // 输出棋盘的最后情况 for (int[] rows : chessboard) { for (int step : rows) { System.out.print(step + "\t"); } System.out.println(); } } /** * 功能： 根据当前位置(Point对象)，计算马儿还能走哪些位置(Point)，并放入到一个集合中(ArrayList), 最多有8个位置 * @param curPoint * @return */ public static ArrayList<Point> next(Point curPoint) { // 创建一个ArrayList ArrayList<Point> ps = new ArrayList<Point>(); // 创建一个Point Point p1 = new Point(); // 表示马儿可以走5这个位置 if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) { ps.add(new Point(p1)); } // 判断马儿可以走6这个位置 if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) { ps.add(new Point(p1)); } // 判断马儿可以走7这个位置 if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) { ps.add(new Point(p1)); } // 判断马儿可以走0这个位置 if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) { ps.add(new Point(p1)); } // 判断马儿可以走1这个位置 if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) { ps.add(new Point(p1)); } // 判断马儿可以走2这个位置 if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) { ps.add(new Point(p1)); } // 判断马儿可以走3这个位置 if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) { ps.add(new Point(p1)); } // 判断马儿可以走4这个位置 if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) { ps.add(new Point(p1)); } return ps; } /** * 完成骑士周游问题的算法 * @param chessboard 棋盘 * @param row 马儿当前的位置的行 从0开始 * @param column 马儿当前的位置的列 从0开始 * @param step 是第几步 ,初始位置就是第1步 */ public static void traversalChessboard(int[][] chessboard, int row, int column, int step) { chessboard[row][column] = step; //row = 4 X = 8 column = 4 = 4 * 8 + 4 = 36 visited[row * X + column] = true; //标记该位置已经访问 //获取当前位置可以走的下一个位置的集合 ArrayList<Point> ps = next(new Point(column, row)); //对ps进行排序,排序的规则就是对ps的所有的Point对象的下一步可走位置的数目，进行非递减排序 sort(ps); //遍历 ps while(!ps.isEmpty()) { Point p = ps.remove(0);//取出下一个可以走的位置 //判断该点是否已经访问过 if(!visited[p.y * X + p.x]) {//说明还没有访问过 traversalChessboard(chessboard, p.y, p.x, step + 1); } } //判断马儿是否完成了任务，使用 step 和应该走的步数比较 ， //如果没有达到数量，则表示没有完成任务，将棋盘该位置设置为0 //说明: step < X * Y 成立的情况有两种 //1. 棋盘到目前位置,仍然没有走完 //2. 棋盘处于一个回溯过程 if(step < X * Y && !finished ) { chessboard[row][column] = 0; visited[row * X + column] = false; } else { finished = true; } } //根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数 public static void sort(ArrayList<Point> ps) { ps.sort(new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { //获取到o1的下一步的所有位置个数 int count1 = next(o1).size(); //获取到o2的下一步的所有位置个数 int count2 = next(o2).size(); return count1 - count2; } }); } }
- 程序运行结果
骑士周游算法，开始运行~~ 共耗时: 22 毫秒 1 16 37 32 3 18 47 22 38 31 2 17 48 21 4 19 15 36 49 54 33 64 23 46 30 39 60 35 50 53 20 5 61 14 55 52 63 34 45 24 40 29 62 59 56 51 6 9 13 58 27 42 11 8 25 44 28 41 12 57 26 43 10 7
