常用十大算法

这里的讲解图主要使用的是尚硅谷韩顺平老师的图，请周知。

二分查找（非递归）

分治算法

动态规划算法

KMP算法

贪心算法

普利姆（Prim）算法

克鲁斯卡尔（Kruskal）算法

迪杰斯特拉（Dijkstra）算法

弗洛伊德（Floyd）算法

骑士周游算法

总结

二分查找（非递归）

二分查找（非递归）算法：前面我们涉及的是递归实现二分查找算法。如今实现的是非递归的方式。同样，二分查找只适用于有序数列。二分查找的运行时间为对数时间O（log2n），即查找到需要的目标位置最多只需要log2n步。

实现思路：

我们需要借助两个指针left和right，left指向第一个数据；right指向最后一个数据。
通过一个循环while(left<=right)，含义为当两个指针不相对僭越时，说明数据仍未被遍历完。
将中间值arr[mid],mid=(left+right)/2与要查找的数据进行比较

3.1如果相等，直接返回，结束查找

3.2如果arr[mid]>data，则说明要查找的数据在此中间值的左边，将right指针向左移动，right=mid-1;然后重复3步骤

3.3如果arr[mid]<data，则说明要查找的数据在此中间值的右边，将left指针向右移动，

left=mid+1;然后重复3步骤

4.当循环结束，该查找方法未结束，说明没有查找到对应的值，直接返回-1。

代码：

package com.liu.algorithm;/*** @author liuweixin* @create 2021-09-20 16:13*/
//二分查找（非递归）
public class BinarySearch {public static void main(String[] args) {int [] arr = new int[]{1,3,8,10,11,67,100};int search = binarySearch(arr, 101);System.out.println(search);}/*** 非递归式实现二分查找** @param arr  要查找的数组* @param data 要查找的数据* @return 如果找到，返回该数据的下标；否则返回-1*/public static int binarySearch(int[] arr, int data) {//创建两个指针，分别指向第一个数据与最后一个数据int left = 0;int right = arr.length - 1;while (left<=right){//当两个指针不相对僭越时，说明数据仍未被遍历完int mid = (left+right)/2;if(arr[mid]==data){//如果中间值刚好就是要查找的值//直接返回return mid;}else if(arr[mid]<data){//要查找的数据在该中间值的右边left=mid+1;}else {//要查找的数据在该中间值的左边right=mid-1;}}//如果循环结束，该方法没有终结，说明没有找到。return -1;}
}

分治算法

分治算法：分治算法的主要思想是将一个复杂而庞大的问题分解成若干个小的容易解决的子问题，进而进行治，而将治后的结果进行汇总合并，就得到了该复杂庞大问题的结果。这个思想在之前的归并排序中就曾出现过。

分治算法可以解决的一些经典问题

二分搜索
大整数乘法
棋盘覆盖
归并排序
快速排序
线性时间选择
最接近点对问题
循环赛日程表
汉诺塔

分治算法的基本步骤：

分治法在每一层递归上都有三个步骤：

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
解决：若子问题规模较小而容易被解决则直接解，否则递归地解每个子问题
合并：将各个子问题的解合并为原问题的解。

这里我们以汉诺塔的实际求解来了解分治算法

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

汉诺塔思路求解：

如果有一个盘，A->C

如果我们有n>=2情况，我们总是可以看作是两个盘 1.最下边的盘 2.上面的盘

先把最上面的盘 A->B
把最下边的盘A->C
把B塔的所有盘从B->C

代码附上：

package com.liu.algorithm;/*** @author liuweixin* @create 2021-09-20 21:38*/
//分治算法--汉诺塔问题
public class Hanluotower {public static void main(String[] args) {hanluoTower(4,'A','B','C');}/*** 汉诺塔的移动的方法* 使用分治算法* @param num  盘的个数* @param a   第一个塔a* @param b   需要借助的塔b* @param c   第三个塔c*/public static void hanluoTower(int num,char a,char b,char c){//如果只有一个盘if(num==1){System.out.println("第1个盘从"+a+"->"+c);}else {//如果我们有n>=2情况，我们总可以看作是两个盘//1.先把最上面的所有盘A->B，移动过程中会使用到chanluoTower(num-1,a,c,b);//2.把最下边的盘A->CSystem.out.println("第"+num+"个盘从"+a+"->"+c);//3.把B盘的所有盘从B->C，移动过程中使用到a塔hanluoTower(num-1,b,a,c);}}
}

汉诺塔问题，虽然代码少，但是里面变化还是很多的，在我细细debug时，发现其中传参的变化让我感叹万分，tql！大家也可以仔细debug看看

动态规划算法

动态规划算法（Dynamic Programming）：

动态规划算法的核心是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法，与分治算法类似。但区别是适用于用动态规划求解的问题，经分解得到子问题往往不是相互独立的（即下一个子阶段的求解是建立在上一个子结点的解的基础上，进行进一步的求解）。动态规划可以通过填表的方式来逐步推进，得到最优解。

我们借助于一个背包问题来了解动态规划算法：

韩老师的图解还是很经典的：

思路分析：

利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们就有了下面的结果：

(1) v[i][0]=v[0][j]=0; //表示填入表第一行和第一列是0

(2) 当 w[i]> j 时：v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略

(3) 当j>=w[i]时：v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}

//当准备加入的新增的商品的容量小于等于当前背包的容量

//装入的方式:

v[i-1][j]：就是上一个单元格的装入的最大值

v[i] :表示当前商品的价值

v[i-1][j-w[i]]：装入i-1商品，到剩余空间j-w[i]的最大值

当j>=w[i]时：v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}

代码：

package com.liu.algorithm;/*** @author liuweixin* @create 2021-09-21 20:46*/
//动态规划算法->背包问题
public class KnapsackProblem {public static void main(String[] args) {int[] weight = new int[]{1, 4, 3};int[] value = new int[]{1500, 3000, 2000};int capacity = 4;//背包容量dynamic(capacity, weight, value);}/*** 通过动态规划算法解决背包问题* 输出在背包容量范围内的最大价值** @param capacity 背包的容量* @param weight   物品重量的数组* @param value    物品价值的数组*/public static void dynamic(int capacity, int[] weight, int[] value) {//创建物品最大价值与背包容量之间的关系，第一行与第一列置零，所以+1int[][] arr = new int[weight.length + 1][capacity + 1];//先将第一行与第一列置零for (int i = 0; i < arr.length; i++) {arr[i][0] = 0;}for (int i = 0; i < arr[0].length; i++) {arr[0][i] = 0;}int[][] path = new int[weight.length + 1][capacity + 1];//为了记录放入商品的情况for (int i = 1; i < arr.length; i++) {//对arr的行进行遍历for (int j = 1; j < arr[i].length; j++) {//对arr的列进行遍历if (weight[i - 1] > j) {//如果该商品的容量大于背包容量arr[i][j] = arr[i - 1][j];//直接使用上一个单元格的装入策略} else {//如果该商品的容量小于背包容量//arr[i][j] = Math.max(arr[i - 1][j], value[i - 1] + arr[i - 1][j - weight[i - 1]]);//为了记录商品放到背包的情况，我们不能直接使用上面的公式，需要借助if-else来实现if (arr[i - 1][j] < (value[i - 1] + arr[i - 1][j - weight[i - 1]])) {arr[i][j] = value[i - 1] + arr[i - 1][j - weight[i - 1]];//并把情况记录到path中//只要我们不是采取了上一行的数据，而是采用了新的数据，则说明此时加入了新商品，所以我们需要对其标记path[i][j] = 1;} else {arr[i][j] = arr[i - 1][j];}}}}//遍历价值数组for (int[] temp : arr) {for (int data : temp) {System.out.print(data + " ");}System.out.println();}//将物品情况输出//这里从最后开始输出的原因是，在最后，价值是最大的，我们只要输出最大的那个价值对应的商品即可int i = path.length - 1;//行的最大下标int j = path[0].length - 1;//列的最大下标while (i > 0 && j > 0) {//从path的最后开始找if (path[i][j] == 1) {System.out.println("第" + i + "个商品放到背包");j -= weight[i - 1];//此时已经找到最大价值的商品，如果不止一件，我们就减少该件的重量，去寻找下一件，所以j要减去当前件的重量}i--;//向前寻找}}
}

KMP算法

KMP算法

这里我就借助尚硅谷韩老师的例子，顺便帮尚硅谷打一波小广告。

问题引入：

1)有一个字符串str1="硅硅谷尚硅谷你尚硅尚硅谷你尚硅谷你尚硅你好"，和一个子串 str2="尚硅谷你尚硅你"

2)现在要判断str1是否含有str2,如果存在，就返回第一次出现的位置，如果没有，则返回-1

对该问题，我们第一想法是采取暴力匹配的方式去解决；

如果用暴力匹配的思路，并假设现在 str1 匹配到 i 位置，子串 str2 匹配到 j 位置，则有:

1) 如果当前字符匹配成功（即str1[i] == str2[j]），则 i++，j++，继续匹配下一个字符

2) 如果失配（即 str1[i]! = str2[j]），令 i = i - (j - 1)，j = 0。相当于每次匹配失败时，i回溯，j被置为0。

暴力匹配算法的实现：

我们借助两个循环，一个循环则是循环str1字符串，另一个循环则循环str2字符串。
i为循环str1字符串的指针，j为循环str2字符串的指针。
当str1[i]==str2[j]时，两个指针同时迈进。
当str1[i]!=str2[j]时，说明此时已不匹配，需要将指针回溯。此时j需要回溯到0，而i则

需要回溯到刚开始遍历的i的后一位，即与j同步的长度的后一位，即i=i-j+1。然后继续进行下一位的匹配。

缺点：

用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间。(不可行!)

所以我们这里就采取KMP算法来解决。

KMP是一个解决模式串在文本串是否出现过，如果出现过，返回最早出现位置的经典算法。KMP算法，即Knuth-Morris-Pratt字符串查找算法。KMP算法就是利用之前判断过的信息，通过一个nect数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间。

在讲解KMP算法的具体实施前，我们先介绍《部分匹配表》是如何实现的，该表在KMP算法的实施中占据关键性作用。

《部分匹配表》是通过一个字符串的前缀与后缀集合中一致的字串的个数，对应而列出来的一个表。

例如：“ABCDAD”

当只有A时，其前缀为空，后缀也为空，此时共有元素长度为0；

当AB时，前缀为A,后缀为B,此时共有长度为0；

当ABC时，前缀为A,AB,后缀为BC,C,此时共有长度为0；

当ABCD时，前缀为A,AB,ABC,后缀为BCD,CD,D,此时共有长度为0；

当ABCDA时，前缀为A,AB,ABC,ABCD,后缀为BCDA,CDA,DA,A,此时共有长度为1

当ABCDAD时，前缀为A,AB,ABC,ABCD,ABCDA,后缀为BCDAD,CDAD,DAD,AD,D,此时共有长度为0；

所以可以列出表：

搜索词	A	B	C	D	A	D
部分匹配值	0	0	0	0	1	0

有了部分匹配表的知识，我们就可以讲解KMP算法的思路：

关键点：

需要移动的位数=已匹配的字符数-对应的部分匹配值。J=next[j-1]

代码：

package com.liu.algorithm;import com.sun.org.apache.bcel.internal.generic.NEW;/*** @author liuweixin* @create 2021-09-22 20:13*/
//KMP算法，即Knuth-Morris-Pratt字符串查找算法
public class KMP {public static void main(String[] args) {String str1 = "BBC ABCDAB ABCDABCDABDE";String str2 = "ABCDABD";KMP kmp = new KMP();int[] next = kmp.kmpNext(str2);int index = kmp.kmpSearch(str1, str2, next);System.out.println(index);}/*** kmp算法的实现** @param str1  文本串* @param str2  模式串* @param next 部分匹配表* @return  如果找到，返回第一个匹配的位置；如果没有找到，则返回-1。*/public static int kmpSearch(String str1, String str2, int[] next) {//遍历for (int i = 0, j = 0; i < str1.length(); i++) {//需要处理str1.charAt()!=str2.charAt(j),去调整j的大小while (j > 0 && str1.charAt(i) != str2.charAt(j)) {//即将模式串向后挪动j = next[j - 1];}if (str1.charAt(i) == str2.charAt(j)) {j++;}if (j == str2.length()) {//找到了return i - j + 1;}}return -1;}/*** 获取传入字符串的部分匹配值表** @param dest 传入字符串* @return 返回一个部分匹配值表*/public static int[] kmpNext(String dest) {//创建一个next数组保存部分匹配值int[] next = new int[dest.length()];next[0] = 0;//字符串的首个元素的匹配值为0for (int i = 1, j = 0; i < dest.length(); i++) {//当dest.charAt(i)!=dest.charAt(j)，我们需要从next[j-1]获取新的j//直到我们发现有dest.charAt(i)==dest.charAt(j)成立才退出//这是kmp算法的核心点while (j > 0 && dest.charAt(i) != dest.charAt(j)) {j = next[j - 1];}//当dest.charAt(i)==dest.charAt(j)满足时，部分匹配值就是+1if (dest.charAt(i) == dest.charAt(j)) {j++;}next[i] = j;}return next;}
}

贪心算法

贪心算法：

贪婪算法（贪心算法）是指在对问题进行求解时，在每一步选择中都采取最好或者最优（即最有利）的选择，从而希望能够导致结果是最好或者最有的算法。
贪心算法所得到的结果不一定是最优的结果（有时会是最优解），但是都是相对近似最优解的结果

贪心算法最佳应用—集合覆盖

思路：

我们通过选择每次覆盖最多地区的广播台，然后将其添加到我们记录广播台的ArrayList集合中即selects。
每次添加完广播台，我们需要在记录所有需要覆盖地区的集合allAreas中删除掉该广播台覆盖的地区，然后继续循环，执行1操作
allAreas中的地区全部删除掉，循环结束，此时所有地区已覆盖完毕。

代码：

package com.liu.algorithm;import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;/*** @author liuweixin* @create 2021-09-23 15:37*/
//贪心算法—集合覆盖问题
public class GreedyAlgorithm {public static void main(String[] args) {//先创建对应的广播台集合HashMap<String, HashSet<String>> broadcasts = new HashMap();//创建对应的广播HashSet<String> hashSet1 = new HashSet<>();hashSet1.add("北京");hashSet1.add("上海");hashSet1.add("天津");HashSet<String> hashSet2 = new HashSet<>();hashSet2.add("广州");hashSet2.add("北京");hashSet2.add("深圳");HashSet<String> hashSet3 = new HashSet<>();hashSet3.add("成都");hashSet3.add("上海");hashSet3.add("杭州");HashSet<String> hashSet4 = new HashSet<>();hashSet4.add("上海");hashSet4.add("天津");HashSet<String> hashSet5 = new HashSet<>();hashSet5.add("杭州");hashSet5.add("大连");broadcasts.put("k1", hashSet1);broadcasts.put("k2", hashSet2);broadcasts.put("k3", hashSet3);broadcasts.put("k4", hashSet4);broadcasts.put("k5", hashSet5);//创建一个集合，记录最终的广播台ArrayList<String> selects = new ArrayList<>();//创建一个集合，记录要覆盖的地区HashSet<String> allAreas = new HashSet<>();allAreas.add("北京");allAreas.add("上海");allAreas.add("天津");allAreas.add("广州");allAreas.add("深圳");allAreas.add("成都");allAreas.add("杭州");allAreas.add("大连");//创建一个最大覆盖的指针String maxSize;HashSet<String> temp = new HashSet<>();//借用一个临时的hashSet变量，用来存储交集while (allAreas.size() != 0) {//当要覆盖的区域还不等于0时，说明还没有选择完广播台，继续循环maxSize = null;for (String key : broadcasts.keySet()) {//遍历广播台的数据temp.clear();//将临时的变量置空temp.addAll(broadcasts.get(key));//将当前广播台覆盖的地区添加到临时变量中temp.retainAll(allAreas);//找到当前变量与总地区重合的地区数//这里体现贪心算法，每一步都选取最优的选择if (temp.size() > 0 && maxSize == null) {maxSize = key;} else if (temp.size() > 0 && maxSize != null) {HashSet<String> max = broadcasts.get(maxSize);//获取最大覆盖指针指向的广播台max.retainAll(allAreas);//获取其与总地区重合的地区数if (temp.size() > max.size()) {//如果当前遍历的广播台的包含数大于指针指向的包含数，则指针指向当前keymaxSize = key;}}}if (maxSize != null) {//当for循环结束，找到覆盖最多的广播台selects.add(maxSize);//并且在allAreas中删除maxSize所指向的地区allAreas.removeAll(broadcasts.get(maxSize));}}System.out.println(selects);}
}

普利姆（Prim）算法

普利姆算法：

问题引入—修路问题：

修路问题的本质就是最小生成树（MST）的问题。给定一个带权的无向连通图，如何选取一颗生成树，使得树上所有边上的权的总和为最小，这叫做最小生成树。

N个顶点，一定有N-1条边
包含全部顶点
N-1条边都在图中

求最小生成树一般是采用普利姆算法和克鲁斯卡尔算法

普利姆（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，uj）加入集合D中，标记visited[vj]=1
重复步骤2，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边

实现代码：

package com.liu.algorithm;/*** @author liuweixin* @create 2021-09-23 18:59*/
//普利姆算法
public class PrimAlgorithm {public static void main(String[] args) {char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};int[][] weight = new int[][]{{Integer.MAX_VALUE, 5, 7, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 2},{5, Integer.MAX_VALUE, Integer.MAX_VALUE, 9, Integer.MAX_VALUE, Integer.MAX_VALUE, 3},{7, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 8, Integer.MAX_VALUE, Integer.MAX_VALUE},{Integer.MAX_VALUE, 9, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 4, Integer.MAX_VALUE},{Integer.MAX_VALUE, Integer.MAX_VALUE, 8, Integer.MAX_VALUE, Integer.MAX_VALUE, 5, 4},{Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 4, 5, Integer.MAX_VALUE, 6},{2, 3, Integer.MAX_VALUE, Integer.MAX_VALUE, 4, 6, Integer.MAX_VALUE}};Graph graph = new Graph(data.length);Graph graph1 = creatGraph(graph, data, weight);prim(graph1,0);}/*** 对一个图对象赋值** @param graph  要赋值的图对象* @param data   图节点的数值* @param weight 图节点之间的权值*/public static Graph creatGraph(Graph graph, char[] data, int[][] weight) {for (int i = 0; i < data.length; i++) {graph.data[i] = data[i];//给图的节点赋值for (int j = 0; j < weight[i].length; j++) {graph.weight[i][j] = weight[i][j];//给图的节点之间的权值复制}}return graph;}/*** 普利姆算法的实现** @param graph 要搜寻最短路径的图* @param v     最短路径的起始点*/public static void prim(Graph graph, int v) {//先创建一个isVisited数组，用以表示是否已访问的数组，boolean[] isVisited = new boolean[graph.data.length];int index1 = -1;//记录第一个节点的下标int index2 = -1;//记录第二个节点的下标int min = Integer.MAX_VALUE;//借用该辅助值，记录下最小的权值//先把当前的节点标记为已访问isVisited[v] = true;for (int i = 1; i < graph.data.length; i++) {//大循环，循环边的个数，n个结点，有n-1条边for (int j = 0; j < graph.data.length; j++) {//寻找已访问的点for (int k = 0; k < graph.data.length; k++) {//寻找未访问的点if (isVisited[j] && !isVisited[k] && graph.weight[j][k] < min) {//当进入if判断，即说明此时找到了较小的权值min = graph.weight[j][k];//记录下该两个结点的坐标index1 = j;index2 = k;}}}//当第二个for循环结束，此时已找到未访问点的最小权值，即找到最小路径System.out.println(graph.data[index1] + "--->" + graph.data[index2] + "  路径长度为:" + min);//重置min值，并标记data[k]值已访问isVisited[index2] = true;min = Integer.MAX_VALUE;}}
}//创建图对象
class Graph {char[] data;//图的节点的值int[][] weight;//表示两个节点之间的距离，即权值int vertexs;//节点个数public Graph(int vertexs) {this.vertexs = vertexs;weight = new int[vertexs][vertexs];data = new char[vertexs];}
}

克鲁斯卡尔（Kruskal）算法

克鲁斯卡尔（kruskal）算法：

之前提到，求最小生成树我们一般可以采用两种算法，一种是普利姆算法，一种是克鲁斯卡尔算法。因此我们同样引入求最短路径的的问题来了解克鲁斯卡尔算法。

Kruskal算法介绍：

1)克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。

2)基本思想：按照权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路

3)具体做法：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止

Krukal算法的图解：

Kruskal算法分析：

判断是否构成回路：

代码：

package com.liu.algorithm;import java.util.Arrays;/*** @author liuweixin* @create 2021-09-23 19:59*/
//克鲁斯卡尔算法—最短路径公交问题
public class KruskalCaseAlgorithm {int[][] weight;//对应的顶点与顶点之间的权值char[] data;//顶点数据int edgeNum;//边的个数final static int INF = Integer.MAX_VALUE;//一个常数，用以表示两个顶点之间不连通//构造器初始化public KruskalCaseAlgorithm(int[][] weight, char[] data) {this.weight = weight;this.data = data;for (int i = 0; i < weight.length; i++) {for (int j = i + 1; j < weight[i].length; j++) {if (weight[i][j] != INF) {this.edgeNum++;}}}}public static void main(String[] args) {char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};int[][] weight = {{0, 12, INF, INF, INF, 16, 14},{12, 0, 10, INF, INF, 7, INF},{INF, 10, 0, 3, 5, 6, INF},{INF, INF, 3, 0, 4, INF, INF},{INF, INF, 5, 4, 0, 2, 8},{16, 7, 6, INF, 2, 0,9},{14, INF, INF, INF, 8, 9,0}};KruskalCaseAlgorithm kruskalCaseAlgorithm = new KruskalCaseAlgorithm(weight, vertexs);kruskalCaseAlgorithm.kruskal();}public void kruskal() {int index = 0;//记录最终结果数组的索引//创建一个终点数组int[] ends = new int[edgeNum];//创建一个数组记录最终的结果EData[] result = new EData[edgeNum];EData[] eDatas = getEData();//获取边的数据的集合//对边的数据的权重进行排序sortEData(0, eDatas.length - 1, eDatas);System.out.println("边的集合" + Arrays.toString(eDatas) + " 共有" + edgeNum + "条");//遍历eDatas数组，将边添加到最小生成树中，判断准备加入的边是否形成了回路，如果没有，就加入result，否则不能加入for (int i = 0; i < edgeNum; i++) {//获取到第i条边的第一个顶点与第二个顶点，即起点与终点int index1 = getPosition(eDatas[i].start);int index2 = getPosition(eDatas[i].end);//获取两个顶点的终点坐标int end1 = getEnd(ends, index1);int end2 = getEnd(ends, index2);//判断是否构成回路if (end1 != end2) {//没有构成回路ends[end1] = end2;//设置m 在"已有最小生成树中的终点"result[index++] = eDatas[i];//把边加入到result数组}}System.out.println();for (int i = 0; i < result.length; i++) {if(result[i]!=null){System.out.println(result[i]);}}}/*** 获取对应顶点的下标** @param data 要获取的顶点* @return 找到则返回下标，否则返回-1*/public int getPosition(char data) {for (int i = 0; i < this.data.length; i++) {if (this.data[i] == data) {return i;}}return -1;}/*** 初始化边的数组** @return 返回一个记录了边的数组*/public EData[] getEData() {int index = 0;//记录数组的下标EData[] eDatas = new EData[edgeNum];//创建一个记录边的数组for (int i = 0; i < weight.length; i++) {for (int j = i + 1; j < weight[i].length; j++) {if (weight[i][j] != INF) {//当权值不为INF时，说明此时两个点连通//给数组赋值eDatas[index++] = new EData(data[i], data[j], weight[i][j]);}}}return eDatas;}/*** 功能:获取下标为i的顶点的终点（），用于判断后面两个顶点的重点是否相同** @param ends 数组就是记录了各个顶点对应的终点是哪个，ends数组是在遍历过程中，逐渐形成* @param i    表示传入的顶点对应的下标* @return 返回的就是下标为i的这个顶点对应的终点的下标*/public int getEnd(int[] ends, int i) {while (ends[i] != 0) {//循环的目的是找到最终的终点i = ends[i];}return i;}/*** 对边的数组以权重大小进行排序* 我这里使用快速排序，具体不加注释** @param eData  要排序的数组* @param left1  数组其实位置的下标* @param right1 数组最后一个数据的下标*/public static void sortEData(int left1, int right1, EData[] eData) {int left = left1;int right = right1;int mid = eData[(left + right) / 2].weight;EData temp;while (left < right) {while (eData[left].weight < mid) {left++;}while (eData[right].weight > mid) {right--;}if (left >= right) {break;}temp = eData[left];eData[left] = eData[right];eData[right] = temp;if (eData[left].weight == mid) {right--;}if (eData[right].weight == mid) {left++;}}if (left == right) {left++;right--;}if (left1 < right) {sortEData(left1, right, eData);}if (right1 > left) {sortEData(left, right1, eData);}}
}//创建一个边对象
class EData {char start;//边的起点char end;//边的终点int weight;//边的权值public EData(char start, char end, int weight) {this.start = start;this.end = end;this.weight = weight;}@Overridepublic String toString() {return "EData{" +"start=" + start +", end=" + end +", weight=" + weight +'}';}
}

迪杰斯特拉（Dijkstra）算法

迪杰斯特拉算法：

问题场景引入—最短路径问题：

区别：

这个与普利姆算法（prim）和克鲁斯卡尔算法（kruskal）求解的问题不同的是，该问题是求某个村庄到其他各个村庄之间的最短距离。而prim与kruskal求解的是边的权值和最小的问题。Dijkstra注重的是局部1对1，而prim和kruskal求的最小生成树注重的是整体。

迪杰斯特拉（Dijkstra）算法的介绍：

迪杰斯特拉（Dijkstra）算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展（广度优先搜索思想），直到扩展到终点为止。

Dijkstra算法实现的过程：

1)设置出发顶点为v，顶点集合V{v1,v2,vi...}，v 到V中各顶点的距离构成距离集合Dis，Dis{d1,d2,di...}，Dis 集合记录着v到图中各顶点的距离(到自身可以看作0，v到vi距离对应为di)

2)从Dis中选择值最小的di并移出Dis集合，同时移出 V 集合中对应的顶点 vi，此时的v到vi即为最短路径

3)更新Dis集合，更新规则为：比较v到V集合中顶点的距离值，与v通过vi到V集合中顶点的距离值，保留值较小的一个(同时也应该更新顶点的前驱节点为vi，表明是通过vi到达的)

4)重复执行两步骤，直到最短路径顶点为目标顶点即可结束

通俗地说：

我们以这个图为例：

首先假设我们设置的起始点为C：

Dijkstra算法的特点是广度优先遍历思想。我们以C为中心，我们先标记C为已访问，然后找到与其直连的点A、E，因为是直连的，所以两者都是最短的，此时把C到A、E的距离记录下来。
找到直连后，我们再找权值最短的边，即A，这里有一点贪心算法的意味，然后我们再以A作为搜索点，设置A为已访问，广度优先遍历，找到B、G，然后先把CG、CB的距离记录下来。
我们以A作为搜索点遍历完后，再找下一条权值小的边，即CE，找到E点；把E设置为已访问。
我们以E点作为搜索点，广度优先遍历，找到G、F，计算出CG、CF的长度，此时发现CEG>CAG，所以我们就以CAG的长度作为最短距离，同样把CF的长度记录下来。
然后再找下一个权值最短边，找到G点，重复上述操作…..
最终就能得到一个以C为起点的到各个顶点最短路径的结果。

代码：

package com.liu.algorithm;import java.util.Arrays;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);//测试, 看看图的邻接矩阵是否okgraph.showGraph();//测试迪杰斯特拉算法graph.dsj(2);//Cgraph.showDijkstra();}}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.show();}// 显示图public void showGraph() {for (int[] link : matrix) {System.out.println(Arrays.toString(link));}}//迪杰斯特拉算法实现/*** * @param index 表示出发顶点对应的下标*/public void dsj(int index) {vv = new VisitedVertex(vertex.length, index);update(index);//更新index顶点到周围顶点的距离和前驱顶点for(int j = 1; j <vertex.length; j++) {index = vv.updateArr();// 选择并返回新的访问顶点update(index); // 更新index顶点到周围顶点的距离和前驱顶点} }//更新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.in(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到其它顶点的距离，会动态更新，求的最短距离就会存放到dispublic 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.already_arr[index] = 1; //设置出发顶点被访问过this.dis[index] = 0;//设置出发顶点的访问距离为0}/*** 功能: 判断index顶点是否被访问过* @param index* @return 如果访问过，就返回true, 否则访问false*/public boolean in(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 updateArr() {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 show() {System.out.println("==========================");//输出already_arrfor(int i : already_arr) {System.out.print(i + " ");}System.out.println();//输出pre_visitedfor(int i : pre_visited) {System.out.print(i + " ");}System.out.println();//输出disfor(int i : dis) {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.println("N ");}count++;}System.out.println();}}

弗洛伊德（Floyd）算法

弗洛伊德（Floyd）算法：

Floyd算法介绍：

1)和 Dijkstra 算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名

2)弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径

3)迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径。

4) 弗洛伊德算法VS迪杰斯特拉算法：迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点的最短路径；弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。

Floyd算法分析：

1)设置顶点vi 到顶点vk的最短路径已知为Lik，顶点vk到vj的最短路径已知为Lkj，顶点vi到vj的路径为Lij，则vi 到vj的最短路径为：min((Lik+Lkj),Lij)，vk 的取值为图中所有顶点，则可获得vi 到vj的最短路径

2)至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj，是以同样的方式获得

Floyd算法图解：

通俗地讲：

就是我们找寻一个中间点（遍历所有的点作为中间点）

1）如上图，我们首先找到A作为中间点。

2）然后找到以A点为中间点的起始点和终点，我们可以找到C-A-G、G-A-B、C-A-B三条边，然后记录下CG、GB、BC之间的距离。

3）我们通过遍历找到下一个中间点B，同样以B为中间点找到起始点和终点，这里我们可以找到G-B-A,G-B-D,A-B-D，然后记录下GA、GD、AD之间的距离。

4）然后再找下一个中间点，重复上述操作……

注意:当我们以E作为中间点时，同样也会有C-E-G即表示CG两点之间距离的关系，这时候我们需要跟记录距离的数组中的数据相比，如果小于数组中的元素，就以C-E-G这条边的权值和替换数组中的数据，反之不操作。

代码：

package com.liu.algorithm;import java.util.Arrays;/*** @author liuweixin* @create 2021-09-25 10:16*/
//弗洛伊德算法——各个顶点到其他顶点得最短路径
public class Floyd {int[][]pre_visited;//前驱关系图Graph1 graph1;int[][]dis;static final int N = 65553;public Floyd(Graph1 graph1) {this.graph1=graph1;pre_visited=new int[graph1.vertexs.length][graph1.vertexs.length];//初始时，每个点的前驱顶点都是自己for (int i = 0; i < pre_visited.length; i++) {Arrays.fill(pre_visited[i],i);}dis=new int[graph1.vertexs.length][graph1.vertexs.length];for (int i = 0; i < dis.length; i++) {//先把邻接矩阵赋值给距离数组for (int j = 0; j < dis[i].length; j++) {dis[i][j]=graph1.distant[i][j];}}}public static void main(String[] args) {int[][] distant = {{0,5,7,N,N,N,2},{5,0,N,9,N,N,3},{7,N,0,N,8,N,N},{N,9,N,0,N,4,N},{N,N,8,N,0,5,4},{N,N,N,4,5,0,6},{2,3,N,N,4,6,0}};char[]vertexs={'A','B','C','D','E','F','G'};Graph1 graph1 = new Graph1(distant, vertexs);Floyd floyd = new Floyd(graph1);floyd.floyd();floyd.show();}public void floyd(){for (int i = 0; i < dis.length; i++) {//第一层循环，遍历中间顶点for (int j = 0; j < dis.length; j++) {//遍历起始顶点for (int k = 0; k < dis.length; k++) {//遍历终点if((dis[j][i]+dis[i][k])<dis[j][k]){//如果小于两者间的距离，则替换//更新距离dis[j][k]=dis[j][i]+dis[i][k];//前驱结点也需要变动pre_visited[j][k]=pre_visited[i][k];}}}}}//显示前驱结点数组和距离数组public void show(){char[]vertex = {'A','B','C','D','E','F','G'};for (int i = 0; i < dis.length; i++) {for (int j = 0; j < dis.length; j++) {System.out.print(vertex[pre_visited[i][j]]+" ");}System.out.println();for (int j = 0; j < dis.length; j++) {System.out.print("("+vertex[i]+"到"+vertex[j]+"的最短路径是"+dis[i][j]+")");}System.out.println();System.out.println();}}
}
//创建图对象
class Graph1{int[][]distant;//邻接矩阵char[]vertexs;//数据元素public Graph1(int[][] distant, char[] vertexs) {this.distant = distant;this.vertexs = vertexs;}
}

骑士周游算法

骑士周游算法（马踏棋盘算法）：

骑士周游算法介绍：

1)马踏棋盘算法也被称为骑士周游问题

2) 将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格

马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。

骑士周游算法思路图解：

通俗地讲：

我们先定义一个起始点的坐标x，y
我们标记该点为已访问，棋盘上该点的值，即chess[y][x]的值赋为步数step，这样有便利我们在后面遍历棋盘，就能得到马走的方式。
然后我们求出该起始点坐标的能走的下一步的所有坐标，记录在ArrayList中，下面以list代替
然后我们对list中的所有点的坐标进行排序（排序的原则是该点下一步能走的数量），实现非递减排序，为什么要这样排序呢？因为这里我们采用贪心算法对其进行优化，我们先走那个下一步具有最多走法的那一步，这样的话对我们能更快走完整个棋盘有一定的效率提升。
然后我们对排完序的list中，取出第一位，其下一步能走的更多次数的那个坐标，然后判断该点是否未被访问过，如果未被访问过，就进入递归。
当马走无可走时，就需要回溯。
当step=棋盘方格数时，即此时马已经走完

代码：

package com.liu.algorithm;import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;/*** @author liuweixin* @create 2021-09-25 14:58*/
//骑士周游算法——马踏棋盘
public class HorseChess {static int X;//棋盘的列数static int Y;//棋盘的行数boolean[] visited;//判断该点是否已访问int [][]chess;//棋盘static boolean finished;//如果为true，则访问成功public static void main(String[] args) {HorseChess horseChess = new HorseChess(8, 8);int x=1;//起始列int y=1;//起始行horseChess.HorseChessAlgorithm(horseChess.chess,x-1,y-1,1);for(int[]rows:horseChess.chess){for(int step:rows){System.out.print(step+"\t");}System.out.println();}}public HorseChess(int x,int y ){X=x;Y=y;chess=new int[X][Y];visited = new boolean[X*Y];}/*** 骑士周游算法的实现* @param chess  棋盘* @param x   起始点的坐标X，即为列，从0开始* @param y   起始点的坐标Y，即为行，从0看i是* @param step  马走的步数，第几步，从1开始*/public void HorseChessAlgorithm(int[][]chess,int x,int y,int step){chess[y][x]=step;//先设置步数visited[y*X+x]=true;//把当前坐标设置为已访问ArrayList<Point> next = next(new Point(x, y));//获取该点的下一步的走法sort(next);//体现贪心算法，将其排序while(!next.isEmpty()){Point point = next.remove(0);//获取第一步走法if(!visited[point.y*X+point.x]){//如果该点未被访问过//则走该步，进行下一次的走法，即进入递归HorseChessAlgorithm(chess,point.x,point.y,step+1);}}//判断马儿是否完成了任务，使用step和应该走的步数比较//如果没有达到数量，则表示没有完成任务，将整个棋盘置0// 说明:step < X  * Y成立的情况有两种//1.棋盘到目前位置,仍然没有走完//2.棋盘处于一个回溯过程if(step<X*Y&&!finished){chess[y][x]=0;//将棋盘置零visited[y*X+x]=false;//设置该点未访问}else {//否则，已经完成了该棋盘的走法finished=true;}}/*** 对传入进来的点，判断其下一步有多少种走法** @param curPoint* @return*/public ArrayList<Point> next(Point curPoint) {ArrayList<Point> list = new ArrayList<Point>();Point point = new Point();//图上的5这个点可以走if ((point.x = curPoint.x - 2) >= 0 && (point.y = curPoint.y - 1) >= 0) {list.add(new Point(point));}//6if ((point.x = curPoint.x - 1) >= 0 && (point.y = curPoint.y - 2) >= 0) {list.add(new Point(point));}//7if ((point.x = curPoint.x + 1) < X && (point.y = curPoint.y - 2) >= 0) {list.add(new Point(point));}//0if ((point.x = curPoint.x + 2) < X && (point.y = curPoint.y - 1) >= 0) {list.add(new Point(point));}//1if ((point.x = curPoint.x + 2) < X && (point.y = curPoint.y + 1) < Y) {list.add(new Point(point));}//2if ((point.x = curPoint.x + 1) < X && (point.y = curPoint.y + 2) < Y) {list.add(new Point(point));}//3if ((point.x = curPoint.x - 1) >= 0 && (point.y = curPoint.y + 2) < Y) {list.add(new Point(point));}//4if ((point.x = curPoint.x - 2) >= 0 && (point.y = curPoint.y + 1) < Y) {list.add(new Point(point));}return list;}/*** 对该步骤的下一步进行排序* 体现贪心算法** @param list*/public void sort(ArrayList<Point> list) {//对Point实现comparator接口并重写方法list.sort(new Comparator<Point>() {@Overridepublic int compare(Point o1, Point o2) {//获取o1下一步的所有位置的个数int count1 = next(o1).size();//获取o2下一步的所有位置的个数int count2 = next(o2).size();if (count1 < count2) {return -1;} else if (count1 == count2) {return 0;} else {return 1;}}});}
}