数据结构与算法——基础篇（六）

2021-11-11 本文已影响0人卡斯特梅的雨伞

常用10种算法

1、二分查找算法(非递归)——要求有序

二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找
二分查找法的运行时间为对数时间O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n步，假设从[0,99]的队列(100个数，即n=100)中寻到目标数30，则需要查找步数为㏒₂100 , 即最多需要查找7次( 2^6 < 100 < 2^7)

代码示例

数组 {1,3, 8, 10, 11, 67, 100}, 编程实现二分查找， 要求使用非递归的方式完成

public class BinarySearchNonRecursion {
    public static void main(String[] args) {
        int[] arr = {1, 3, 8, 10, 11, 67, 100};
        System.out.println(binarySearchNonRecursion(arr, 12));
    }

    public static int binarySearchNonRecursion(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        int mid = (left + right) / 2;
        //注意这里继续查找条件是: <=,因为会有left == right刚好找到的时候
        while (left <= right) {
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                //向左找
                right = mid - 1;
                mid = (left + right) / 2;
            } else {
                //向右找
                left = mid + 1;
                mid = (left + right) / 2;
            }
        }
        return -1;
    }

}

2、分治算法——Divide-and-Conquer

介绍

分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
分治算法可以求解的一些经典问题

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

基本步骤

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

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

分治(Divide-and-Conquer(P))算法设计模式

分治.png

汉诺塔

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

64片黄金圆盘需要移动2^64-1=18446744073709551615次。

假如每秒钟一次，共需多长时间呢？移完这些金片需要5845.54亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

思路分析

如果是有一个盘， A->C
如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘（除最下面的一个盘外的所有盘看成一个整体）

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

代码示例

/**
 * 第1个盘从A移动到C
 * 第2个盘从A移动到B
 * 第1个盘从C移动到B
 * 第3个盘从A移动到C
 * 第1个盘从B移动到A
 * 第2个盘从B移动到C
 * 第1个盘从A移动到C
 */
public class HanoiTower {
    public static void main(String[] args) {
        hanoiTower(3,"A","B","C");
    }

   /**
     * 汉诺塔
     * @param num 移动盘数
     * @param a A柱
     * @param b B柱(相当于temp,移动时借助的柱子)
     * @param c C柱
     */
    public static void hanoiTower(int num, String a, String b, String c) {
        if (num == 1) {
            System.out.println("第" + num + "个盘从" + a + "移动到" + c);
        } else {
            //先把 最上面的盘 A->B,借助C
            hanoiTower(num - 1, a, c, b);
            //把最下边的盘 A->C
            System.out.println("第" + num + "个盘从" + a + "移动到" + c);
            //把B塔的所有盘 从 B->C ，借助A
            hanoiTower(num - 1, b, a, c);
        }
    }
}

3、动态规划算法——Dynamic Programming——DP

介绍

动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。

动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )

动态规划可以通过填表的方式来逐步推进，得到最优解。

那下面的01背包用填表的方式举例：

	背包重量1磅时	背包重量2磅时	背包重量3磅时	背包重量4磅时
可选物品：G	1500	1500	1500	1500
可选物品：G，S	1500	1500	1500	3000
可选物品：G，S, L	1500	1500	2000	2000+1500

解释：这里的动态规划体现在，背包的重量从1到4变化时，伴随着可选物品的增加的变化。

当可选物品只有G时，则无论背包重量的变化是多少都只有1500。

然后当可选物品有G,S时，我们会每次都拿新加入是S判断其重量是否满足背包的重量，不满足就拿上一行即只有可选物品G时的值直接填充到该表格。当背包重量到4满足S时，我们就会优先加入S物品判断其价值是否超过上一行同样重量的价值，超过就保留。

最后到可选物品有G,S,L时，我们会每次都拿新加入是L判断其重量是否满足背包的重量,不满足就拿上一行的价值填充该表格，当背包重量来到4时，我们优先那L的重量是否满足背包重量，用4-2（L）的重量得到剩余重量，再拿上一行在剩余重量2时的价值与S价值相加得到3500,大于上一行可选物品G,S的价值3000，因此最大价值为3500。

也就是说我们关注点在新加入物品时与其上一行剩余重量的最大价值合计这两点上。

背包问题

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkle和Hellman提出的。

01背包：01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。
完全背包：每种物品有无限件可用，也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……取[V/c]件等很多种。

无限背包可以转化为01背包。

思路分析

利用动态规划来解决。每次遍历到的第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]]}

代码示例

背包问题：有一个背包，容量为4磅，现有如下物品：

物品	重量	价格
吉他(G)	1	1500
音响(S)	4	3000
电脑(L)	3	2000

要求达到的目标为装入的背包的总价值最大，并且重量不超出
要求装入的物品不能重复。

//动态规划算法——背包问题——01背包
public class KnapsackProblem {
    /**
     * 当背包重量为4时，最大价值情况下，打印都要哪些物品放入背包：
     * 第3个物品放入了背包
     * 第1个物品放入了背包
     * 打印背包的最优价值：
     * [0, 0, 0, 0, 0]
     * [0, 1500, 1500, 1500, 1500]
     * [0, 1500, 1500, 1500, 3000]
     * [0, 1500, 1500, 2000, 3500]
     */
    public static void main(String[] args) {
        //物品的重量
        int[] goodsWeights = {1, 4, 3};
        //物品的价值
        int[] goodsValues = {1500, 3000, 2000};
        //背包容量
        int knapsackCapcity = 4;
        knapsackProblem(goodsWeights,goodsValues,knapsackCapcity);
    }

    public static void knapsackProblem(int[] goodsWeights, int[] goodsValues, int knapsackCapcity) {
        //物品的个数
        int goodsNums = goodsWeights.length;
        //用于存放当有多少个物品对应背包有多大容量时，背包中装入的物品所能达到的最大价值是多少
        //v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值
        //加1是为了避开数组是0开始，让我们能从第1个商品第1磅开始
        int[][] maxValue = new int[goodsNums + 1][knapsackCapcity + 1];
        //记录放入商品的情况
        int[][] path = new int[goodsNums + 1][knapsackCapcity + 1];
        //初始化第一行、第一列为0
        //将第一列值为0 ,因为我们第一个for循环是每一行的数组，
        for (int i = 0; i < maxValue.length; i++) {
            maxValue[i][0] = 0;
            //这里注意如果二维数组的行列不是相同长度的话不能这样设置，否则会导致设置值有问题
            // maxValue[0][i] = 1;
        }
        //将第一行值为0
        for (int i = 0; i < maxValue[0].length; i++) {
            maxValue[0][i] = 0;
        }
        for (int i = 1; i < maxValue.length; i++) {
            for (int j = 1; j < maxValue[i].length; j++) {
                //goodsWeights[i - 1]是因为我们是从1开始的，而我们的重量数组是从0开始的
                 //v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值
                //如果商品重量比容量为j的背包大，那就不需要比较直接拿上一个物品的比较结果即可
                if (goodsWeights[i - 1] > j) {
                    maxValue[i][j] = maxValue[i - 1][j];
                } else {
//                    maxValue[i][j] = Math.max(maxValue[i - 1][j], goodsValues[i - 1] + maxValue[i - 1][j - goodsWeights[i - 1]]);
                    if (goodsValues[i - 1] + maxValue[i - 1][j - goodsWeights[i - 1]] > maxValue[i - 1][j]) {
                        maxValue[i][j] = goodsValues[i - 1] + maxValue[i - 1][j - goodsWeights[i - 1]];
                        //标记物品被装入背包
                        path[i][j] = 1;
                    } else {
                        maxValue[i][j] = maxValue[i - 1][j];
                    }
                }
            }
        }
        System.out.printf("当背包重量为%d时，最大价值情况下，打印都要哪些物品放入背包：\n",knapsackCapcity);
        int x = path.length - 1;
        //注意这里拿的是行的值
        int y = path[0].length - 1;
        while (x > 0 && y > 0) {
            if (path[x][y] == 1) {
                System.out.printf("第%s个物品放入了背包\n", x);
                //减去当前放入背包的商品的重量，去上面查找
                y = y - goodsWeights[x - 1];
            }
            x--;
        }
        System.out.println("打印背包的最优价值：");
        Arrays.stream(maxValue).forEach(ints -> System.out.println(Arrays.toString(ints)));
    }
}

4、KMP算法

应用场景——字符串匹配问题

字符串匹配问题：：

有一个字符串 str1= ""我是一我是一只我是一只我是一只我是一只小蜜蜂，飞到花丛中""，和一个子串 str2="我是一只小蜜蜂"
现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1

暴力匹配算法

//暴力匹配
public class ViolentMatch {
    public static void main(String[] args) {
        String s1 ="我是一我是一只我是一只我是一只我是一只小蜜蜂，飞到花丛中";
        String s2 ="我是一只小蜜蜂";
        int i = violentMatch(s1, s2);
        if (i !=-1) {
            System.out.println("匹配下标为："+i);
        }else {
            System.out.println("匹配不到！");
        }
        //匹配下标为：15

    }

    public static int violentMatch(String s1, String s2) {
        char[] s1Arr = s1.toCharArray();
        char[] s2Arr = s2.toCharArray();
        int i = 0;
        int j = 0;
        while (i < s1Arr.length && j < s2Arr.length) {
            if (s1Arr[i] == s2Arr[j]) {
                i++;
                j++;
            } else {
                i = i - (j - 1);
                j = 0;
            }
        }
        if (j == s2Arr.length) {
            return i - j;
        } else {
            return -1;
        }
    }
}

KMP算法

思路分析

image.png

代码示例

public class KMPAlgorithm {

    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int[] next = kmpNext(str2); //next=[0, 0, 0, 0, 1, 2, 0]
        System.out.println("next=" + Arrays.toString(next));
        
        int index = kmpSearch(str1, str2, next);
        System.out.println("index=" + index); // index=15
    }
    
    //写出我们的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(i) ！= str2.charAt(j), 去调整j的大小
            //KMP算法核心点
            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()) {//找到了 // j = 3 i 
                return i - j + 1;
            }
        }
        return  -1;
    }

    //获取到一个字符串(子串) 的部分匹配值表
    public static  int[] kmpNext(String dest) {
        //ABCDABD
        //创建一个next 数组保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
        for(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) 满足时，部分匹配值就是+1
            if(dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

5、贪心算法——寻找最优的结果

贪心算法的核心就是在每一步选择中都采取最优解，从而使得最后的结果接近最优解。所以重点就在把每一步的最优解找出来。

介绍

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

思路分析

穷举法实现——组合太多

如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有2ⁿ -1 个,假设每秒可以计算10个子集。

广播台数量n	子集总数2ⁿ	需要的时间
5	32	3.2秒
10	1024	102.4秒
32	4294967296	13.6年
100	1.26*100³º	4x10²³年

贪心2.png

贪心算法实现——接近最优解

使用贪婪算法，效率高:目前并没有算法可以快速计算得到准备的值，使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合:
遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系）
将这个电台加入到一个集合中(比如ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
重复第1步直到覆盖了全部的地区

贪心.png

代码示例

场景

贪心3.png

public class Greedy {
    //[K1, K2, K3, K5]
    public static void main(String[] args) {
        //初始化数据，创建电台对应的覆盖地区及总的地区集合
        HashMap<String, HashSet> hashMap = new HashMap<>();
        HashSet<String> hashSet = new HashSet<>();
        hashSet.add("北京");
        hashSet.add("上海");
        hashSet.add("天津");
        hashMap.put("K1", hashSet);
        HashSet<String> hashSet1 = new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("广州");
        hashSet1.add("深圳");
        hashMap.put("K2", hashSet1);
        HashSet<String> hashSet2 = new HashSet<>();
        hashSet2.add("成都");
        hashSet2.add("上海");
        hashSet2.add("杭州");
        hashMap.put("K3", hashSet2);
        HashSet<String> hashSet3 = new HashSet<>();
        hashSet3.add("上海");
        hashSet3.add("天津");
        hashMap.put("K4", hashSet3);
        HashSet<String> hashSet4 = new HashSet<>();
        hashSet4.add("杭州");
        hashSet4.add("大连");
        hashMap.put("K5", hashSet4);
        //所有地区
        HashSet<String> all = new HashSet<>();
        all.addAll(hashSet);
        all.addAll(hashSet1);
        all.addAll(hashSet2);
        all.addAll(hashSet3);
        all.addAll(hashSet4);
        HashSet<String> maxSet = new HashSet<>();
        //添加路径，贪心算法的选择路径（选择的电台）
        HashSet<String> path = new HashSet<>();
        //当覆盖地区不为0时表示还有地区没被覆盖
        while (all.size() > 0) {
            HashMap<String, Object> maxKey = new HashMap<>();
            maxKey.clear();
            maxSet.clear();
            for (String key : hashMap.keySet()) {
                HashSet<String> tempSet = hashMap.get(key);
                //与未被覆盖地区取交集，如果电台key为空或者其覆盖的地区小于遍历出来的这个电台则替换
                //目的是每次都要取得最佳的选择，这也是贪心算法的核心所在，虽然这样处理不一定是最优解，
                // 但肯定是无限接近最优解的一种方法
                tempSet.retainAll(all);
                if (tempSet.size() > 0 && (!maxKey.containsKey("maxKey") || (Integer) maxKey.get("maxKeySize") < tempSet.size())) {
                    maxKey.put("maxKey", key);
                    maxKey.put("maxKeySize", tempSet.size());
                    maxSet.addAll(tempSet);
                }
            }
            //存在选择电台则添加到选择的路径中
            if (maxKey.containsKey("maxKey")) {
                path.add((String) maxKey.get("maxKey"));
                //清除本次已覆盖的地区
                all.removeAll(maxSet);
            }
        }
        System.out.println(path);
    }
}

6、普里姆算法——Prim——MSP——修路问题——最小生成树——最短路径算法

在不构成回路的前提下，普里姆算法是从顶点出发去寻找顶点间的最短路径，而克鲁斯卡尔算法则是从最短边出发去思考问题，按照权值从小到大的顺序选择n-1条边。

最小生成树——MST——Minimum Cost Spanning Tree

求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法.

修路问题本质就是就是最小生成树问题，先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称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,vj）加入集合D中，标记visited[vj]=1
重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边

思路分析

参考下方的思路图，本质就是从某一个顶点出发，去找该顶点临近的最短路径的两个顶点的权值，权值最小的就是最短路径；然后再从这两个顶点出发，去寻找所能找到的与这两个顶点相邻的最短的路径，找到的权值最小的就是本轮的最短路径，并得到最短路径对应的顶点，以此类推，再从这三个顶点出发，去寻找还未关联的顶点中最短的那条路径是哪条对应的哪个顶点，直到连接所有的顶点，这时候假设有n个顶点，那么总的就将找到n-1条边，他们的加权值就是最短路径，也就是该最小生成树的权值。

这里要注意的是每次从这些已连通的顶点出发寻找最短路径时，不能构成回路，也就是另一端必须是未连接的顶点。

普里姆.png

代码示例

场景

普里姆2.png

//修路问题是多对多的图
public class Graph {
    //顶点的个数
    private int vertexNum;
    //顶点名称
    private String[] data;
    //边数据，邻接矩阵表示
    private int[][] weights;

    public int getVertexNum() {
        return vertexNum;
    }

    public void setVertexNum(int vertexNum) {
        this.vertexNum = vertexNum;
    }

    public String[] getData() {
        return data;
    }

    public void setData(String[] data) {
        this.data = data;
    }

    public int[][] getWeights() {
        return weights;
    }

    public void setWeights(int[][] weights) {
        this.weights = weights;
    }

    public Graph(int vertexNum) {
        this.vertexNum = vertexNum;
        this.data = new String[vertexNum];
        this.weights = new int[vertexNum][vertexNum];
    }
    //显示村庄的邻接矩阵
    public void showGraph(){
        for (int[] weight : weights) {
            System.out.println(Arrays.toString(weight));
        }
    }

    //初始化村庄图
    public static Graph initializeGraph(String[] data, int[][] weights) {
        Graph graph = new Graph(data.length);
        for (int i = 0; i < data.length; i++) {
            graph.data[i] = data[i];
            for (int j = 0; j < data.length; j++) {
                graph.weights[i][j] = weights[i][j];
            }
        }
        return graph;
    }
}

public class Prim {
    public static void main(String[] args) {
        String[] data = new String[]{"A", "B", "C", "D", "E", "F", "G"};
        //邻接矩阵的关系使用二维数组表示,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},};
        Graph graph = Graph.initializeGraph(data, weight);
        graph.showGraph();
        Prim.prim(graph,0);
    }

    /**
     * 普里姆算法求最小生成树，修路问题
     *
     * @param graph
     * @param v
     */
    public static void prim(Graph graph, int v) {
        //定义一个顶点已被访问标记数组
        int[] visited = new int[graph.getVertexNum()];
        //先把传进来的顶点v标记为已访问
        visited[v] = 1;
        //记录本轮两个最短连接的顶点的下标
        int v1 = -1;
        int v2 = -1;

        //因为n个顶点对应最短连接是n-1条边，因此只要遍历搜索n-1次去获取n-1条边即可
        for (int i = 1; i < graph.getVertexNum(); i++) {
            //初始化本轮最短路径的值以作比较
            int minWeight = 10000;
            for (int j = 0; j < graph.getVertexNum(); j++) {
                for (int k = 0; k < graph.getVertexNum(); k++) {
                    //visited[j] == 1 表示已访问的顶点 ， visited[k] == 0表 示还未被访问的顶点
                    //这里求的就是一轮遍历下来，已被访问的顶点到未被访问的顶点中距离最短的两个顶点的下标的位置及其权值
                    if (visited[j] == 1 && visited[k] == 0 && graph.getWeights()[j][k] < minWeight) {
                        //替换最短权值和顶点
                        v1 = j;
                        v2 = k;
                        minWeight = graph.getWeights()[j][k];
                    }
                }
            }
            //打印本轮最小
            System.out.println("边<" + graph.getData()[v1] + "," + graph.getData()[v2] + "> 权值:" + minWeight);
            //标记未被访问的最短距离顶点为已访问
            visited[v2] = 1;
        }
    }
    /**
     * [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
     */
}

7、克鲁斯卡尔算法——Kruskal——公交站问题——最小生成树——最短路径算法

介绍

克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。

思路分析

首先就是对所有边的权值进行大小排序，然后从小到大添加到最小生成树中，添加时判断是否形成了回路，如果形成回路则不能用，继续寻找下一条边，直到所有顶点都包含进去。

image.png

kruskal.png

kruskal2.png

kruskal3.png

代码示例

克鲁斯卡尔最佳实践-公交站问题
看一个公交站问题：
有北京有新增7个站点(A, B, C, D, E, F, G) ，现在需要修路把7个站点连通
各个站点的距离用边线表示(权) ，比如 A – B 距离 12公里
问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?

kruskal4.png

public class Kruskal {
    private int edgeNum; //边的个数
    private char[] vertexs; //顶点数组
    private int[][] matrix; //邻接矩阵
    //使用 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 对象实例
        Kruskal kruskalCase = new Kruskal(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 [<B, F>= 7]
     * EData [<E, G>= 8]
     * EData [<A, B>= 12]
     */

    //构造器
    public Kruskal(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 kruskal() {
        int index = 0; //表示最后结果数组的索引
        int[] ends = new int[edgeNum]; //用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点
        //创建结果数组, 保存最后的最小生成树
        EData[] rets = new EData[edgeNum];

        //获取图中 所有的边的集合 ， 一共有12边
        EData[] edges = getEdges();
        System.out.println("图的边的集合=" + Arrays.toString(edges) + " 共"+ edges.length); //12

        //按照边的权值大小进行排序(从小到大)
        sortEdges(edges);

        //遍历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]);
        }


    }

    //打印邻接矩阵
    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(EData[] 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) {//交换
                    EData 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 EData[] getEdges() {
        int index = 0;
        EData[] edges = new EData[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 EData(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 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;
    }

    //重写toString, 便于输出边信息
    @Override
    public String toString() {
        return "EData [<" + start + ", " + end + ">= " + weight + "]";
    }
}

8、迪杰斯特拉算法——最短路径算法——广度优先搜索思想

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

选取一个中间顶点，计算出该顶点到其他各个顶点中所有可能的距离，每次都取最短的距离的边对应的顶点，然后把该顶点标记为已选择。直到所有的顶点都遍历到，这时候就得到了最短路径。

迪杰斯特拉(Dijkstra)算法过程

设置出发顶点为 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 到达的)
重复执行两步骤，直到最短路径顶点为目标顶点即可结束

应用案例

image.png

代码示例

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
        graph.showDijkstra();
    }
    /**
     * [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]
     * ==========================
     * 1 1 1 1 1 1 1
     * 6 6 0 5 6 6 0
     * 2 3 9 10 4 6 0
     * A(2) B(3) C(9) D(10) E(4) F(6) G(0)
     *
     */

}

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到其它顶点的距离，会动态更新，求的最短距离就会存放到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.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_arr
        for(int i : already_arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        //输出pre_visited
        for(int i : pre_visited) {
            System.out.print(i + " ");
        }
        System.out.println();
        //输出dis
        for(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();
        
    }

}

9、弗洛伊德算法——Floyd——最短路径算法——各个顶点之间的最短路径

介绍

和 Dijkstra 算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名
弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径
迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径。
弗洛伊德算法 VS 迪杰斯特拉算法：迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点

的最短路径；弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。

算法图解分析

设置顶点 vi 到顶点 vk 的最短路径已知为 Lik，顶点 vk 到 vj 的最短路径已知为 Lkj，顶点 vi 到 vj 的路径为 Lij，

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

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

image.png

应用案例

image.png

代码示例

public class FloydAlgorithm {

    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) 
     */

}

// 创建图
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);
        }
    }

    // 显示pre数组和dis数组
    public void show() {

        //为了显示便于阅读，我们优化一下输出
        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        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();

        }

    }
    
    //弗洛伊德算法, 比较容易理解，而且容易实现
    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];//更新前驱顶点
                    }
                }
            }
        }
    }
}

10、马踏棋盘算法——骑士周游问题——图的深度优先搜索DFS——递归回溯

马踏棋盘算法也被称为骑士周游问题
将马随机放在国际象棋的 8×8 棋盘 Board[0～7][0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求

每个方格只进入一次，走遍棋盘上全部 64 个方格。打印出每一格对应是第几步。

图解分析

image.png

代码示例

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();
        }
    }
    /**
     * 骑士周游算法，开始运行~~
     * 共耗时: 32 毫秒
     * 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
     */
    
    /**
     * 完成骑士周游问题的算法
     * @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;
        }
        
    }
    
    /**
     * 功能： 根据当前位置(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;
    }

    //根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数
    public static void sort(ArrayList<Point> ps) {
        ps.sort(new Comparator<Point>() {

            @Override
            public int compare(Point o1, Point o2) {
                // TODO Auto-generated method stub
                //获取到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;
                }
            }
            
        });
    }
}

参考文献

尚硅谷Java数据结构与java算法

[图形化数据结构](https://www.cs.usfca.edu/~galles/visualization/Algorithms

数据结构与算法——基础篇（六）

常用10种算法

1、二分查找算法(非递归)——要求有序

代码示例

2、分治算法——Divide-and-Conquer

介绍

基本步骤

分治(Divide-and-Conquer(P))算法设计模式

汉诺塔

思路分析

代码示例

3、动态规划算法——Dynamic Programming——DP

介绍

背包问题

思路分析

代码示例

4、KMP算法

应用场景——字符串匹配问题

暴力匹配算法

KMP算法

思路分析

代码示例

5、贪心算法——寻找最优的结果

介绍

思路分析

穷举法实现——组合太多

贪心算法实现——接近最优解

代码示例

6、普里姆算法——Prim——MSP——修路问题——最小生成树——最短路径算法

最小生成树——MST——Minimum Cost Spanning Tree

介绍

思路分析

代码示例

7、克鲁斯卡尔算法——Kruskal——公交站问题——最小生成树——最短路径算法

介绍

思路分析

代码示例

8、迪杰斯特拉算法——最短路径算法——广度优先搜索思想

迪杰斯特拉(Dijkstra)算法过程

应用案例

代码示例

9、弗洛伊德算法——Floyd——最短路径算法——各个顶点之间的最短路径

介绍

算法图解分析

应用案例

代码示例

10、马踏棋盘算法——骑士周游问题——图的深度优先搜索DFS——递归回溯

图解分析

代码示例

参考文献

猜你喜欢

热点阅读