• 数据结构和算法

    目录

    数据结构：

    实际案例问题：

    判断子字符串在母字符串中第一次出现的位置：

    暴力算法：

    kmp算法：

    汉诺塔问题：

    分治算法

    八皇后问题：

    回溯算法

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

    贪心算法

    约瑟夫环问题：

    最短路径问题：

    背包问题

    动态规划

    排序算法：

    查找算法：

    树结构：

    图结构

    稀疏数组：

    程序员常用的十大算法：

    二分查找算法：

    分治算法：

    动态规划算法：

    KMP算法：

    贪心算法：

    普里姆算法：

    克鲁斯卡尔算法：

    迪杰斯特拉算法：

    弗洛伊德算法：

    马踏棋盘算法：

    数据结构：

    数据结构和算法——数据结构-CSDN博客

    实际案例问题：

    判断子串在母串中第一次出现的位置

    暴力算法

    1. public class ViolenceMatch {
    2.     public static void main(String[] args) {
    3.         String str1 = "AABBCCABCABACBC";
    4.         String str2 = "ABC";
    5.         int index = violenceMatch(str1, str2);
    6.     }
    7.  
    8.     public static int violenceMatch(String str1, String str2) {
    9.         char[] s1 = str1.toCharArray();
    10.         char[] s2 = str2.toCharArray();
    11.         int s1Len = s1.length;
    12.         int s2Len = s2.length;
    13.         int i = 0;
    14.         int j = 0;
    15.         while (i < s1Len && j < s2Len) {
    16.             if (s1[i] == s2[j]) {
    17.                 // 匹配成功
    18.                 i++;
    19.                 j++;
    20.             } else {
    21.                 i = i - (j - 1);
    22.                 j = 0;
    23.             }
    24.         }
    25.         if (j == s2Len) {
    26.             // 匹配成功
    27.             return i - j;
    28.         }
    29.         return -1;
    30.     }
    31. }

    KMP算法

    寻找前缀和后缀的共有元素（部分匹配值）；

    1、先得到子串的部分匹配表；

    1. public class KMPAlgorithm {
    2.     public static void main(String[] args) {
    3.         String str1 = "BBC ABCDAB ABCDABCDABDE";
    4.         String str2 = "ABCDABD";
    5.         int[] next = kmpNext(str2);
    6.         int res = kMPSearch(str1, str2, next);
    7.     }
    8.  
    9.     /**
    10.      * @param str1 母串
    11.      * @param str2 子串
    12.      * @param next 字串的部分匹配表
    13.      * @return
    14.      */
    15.     public static int kMPSearch(String str1, String str2, int[] next) {
    16.         for (int i = 0, j = 0; i < str1.length(); i++) {
    17.             // kmp算法核心
    18.             while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
    19.                 j = next[j - 1];
    20.             }
    21.             if (str1.charAt(i) == str2.charAt(j)) {
    22.                 j++;
    23.             }
    24.             if (j == str2.length()) { // 找到了
    25.                 return i - j + 1;
    26.             }
    27.         }
    28.         return -1;
    29.     }
    30.  
    31.     /**
    32.      * 获取字符串的部分匹配值
    33.      *
    34.      * @param dest
    35.      * @return
    36.      */
    37.     public static int[] kmpNext(String dest) {
    38.         // 创建一个next数组保存部分匹配值
    39.         int[] next = new int[dest.length()];
    40.         next[0] = 0; // 如果字符串的长度为1，部分匹配值就是0
    41.         for (int i = 1, j = 0; i < dest.length(); i++) {
    42.             while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
    43.                 j = next[j - 1];
    44.             }
    45.             // 条件满足时，部分匹配值加一
    46.             if (dest.charAt(i) == dest.charAt(j)) {
    47.                 j++;
    48.             }
    49.             next[i] = j;
    50.         }
    51.         return next;
    52.     }
    53. }

    汉诺塔问题

    用到了递归；

    分治算法

    1、如果只有一个盘，A->C；

    2、如果n>=2，我们总是可以看作是2个盘，最下面的盘和上面的盘；

    1）先把最上面的盘，A->B；

    2）再把最下面的盘，A->C；

    3）把B塔的所有盘，从B盘移动到C盘；

    1. /**
    2.  * 汉诺塔移动的方法
    3.  * 分治算法
    4.  *
    5.  * @param num 有几个盘需要移动
    6.  * @param a   第一个盘
    7.  * @param b
    8.  * @param c
    9.  */
    10. public static void hanoiTower(int num, char a, char b, char c) {
    11.     // 1、如果只有一个盘，A->C；
    12.     if (num == 1) {
    13.         System.out.println("第1个盘：" + a + "->" + c);
    14.     } else {
    15.         // 2、如果n>=2，我们总是可以看作是2个盘，最下面的盘和上面的盘；
    16.         // 1）先把最上面的所有盘，A->B；
    17.         hanoiTower(num - 1, a, c, b);
    18.         // 2）再把最下面的盘，A->C；
    19.         System.out.println("第"+num+"个盘：" + a + "->" + c);
    20.         // 3）把B塔的所有盘，从B盘移动到C盘；
    21.         hanoiTower(num - 1, b, a, c);
    22.     }
    23. }

    八皇后问题

    要求8x8个格子，不能同横、竖、斜；

    回溯算法

    马踏棋盘算法

    也叫骑士周游问题，要求马在任意一个位置，每个格子只能走一次，使马把8x8个格子全部走完；

    图的深度优化便利算法（DFS）

    贪心算法

    约瑟夫环问题

    也叫丢手帕问题；

    最短路径问题

    背包问题

    动态规划

    下一个阶段的求解是建立在上一个阶段的解的基础上的；

    01背包：背包内的物品不能重复；

    完全背包：可以重复；

    1）v[i][0] = v[0][j] = 0; // 表示填入表的第一行和和第一列的值是0；

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

    3）当w[i] <= j时，v[i][j] = max { v[i - 1][j], v[i - 1][j - w[i]] + v[i] } ;// 当准备加入的新增的商品的容量小于等于当前背包的容量；
    // 装入的方式应该是求一个最大值：
    v[i - 1][j] 上一个单元格装入的最大值；
    v[i] 当前商品的价值；

    w[i] 新增商品(下标为i的物品)的容量；

    j 当前背包的容量；

    v[i - 1][j - w[i]] 可以找到剩余空间(j-w[i])的能放的最大价值；

    动态排序代码：

    1. public class KnapsackProblem {
    2.     public static void main(String[] args) {
    3.         int[] w = {1, 4, 3}; // 物品的重量
    4.         int[] val = {1500, 3000, 2000}; // 物品的价值
    5.         int m = 4; // 背包的容量
    6.         int n = val.length; // 物品的个数
    7.         // v[i][j] 表示在前i个物品中，能装入容量为j的背包中的，最大价值
    8.         int[][] v = new int[n + 1][m + 1]; // 表
    9.         int[][] path = new int[n + 1][m + 1];// 记录存放的物品的情况
    10.         // 初始化第一行和第一列
    11.         for (int i = 0; i < v.length; i++) {
    12.             v[i][0] = 0; // 第一列设置为0
    13.         }
    14.         for (int j = 0; j < v[0].length; j++) {
    15.             v[0][j] = 0; // 第一行设置为0
    16.         }
    17.         // 开始动态规划
    18.         for (int i = 1; i < v.length; i++) { // 不处理第一行第一列
    19.             for (int j = 1; j < v[i].length; j++) {
    20.                 // 套用公式
    21.                 if (w[i - 1] > j) { // 因为i是从1开始的
    22.                     // 当准备加入的新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的值
    23.                     v[i][j] = v[i - 1][j];
    24.                 } else {
    25.                     // 当准备加入的新增的商品的容量小于等于当前背包的容量时
    26.                     // 记录存放的物品的情况
    27.                     if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
    28.                         v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
    29.                         // 把当前的情况记录到path
    30.                         path[i][j] = 1;
    31.                     } else {
    32.                         v[i][j] = v[i - 1][j];
    33.                     }
    34.                 }
    35.             }
    36.         }
    37.         // 遍历展示放入背包的最优解
    38.         int i = path.length - 1;
    39.         int j = path[0].length - 1;
    40.         while (i > 0 && j > 0) {
    41.             if (path[i][j] > 0) {
    42.                 System.out.printf("第%d个物品放入背包\n", i);
    43.                 j -= w[i - 1];
    44.             }
    45.             i--;
    46.         }
    47.     }
    48. }

    排序算法

    数据结构和算法——排序算法-CSDN博客

    查找算法

    数据结构和算法——查找算法-CSDN博客

    树结构

    数据结构和算法——树结构-CSDN博客

    图结构

    数据结构和算法——图结构-CSDN博客

    稀疏数组

    目的：压缩二维数组；

    当一个二维数组中大部分元素为0，或者都为同一个值时，可以用稀疏数组来保持该数组。

    把行和列和值的记录在一个小规模的数组中，从而缩小程序的规模；

    原始的二维数组
    稀疏数组

    普通数组与稀疏数组转换的代码： 

    1.     int row, col;
    2.     row = col = 11;
    3.     int[][] chessArr1 = new int[row][col];
    4.     chessArr1[1][1] = 1;
    5.     chessArr1[2][3] = 2;
    6.     chessArr1[4][5] = 2;
    7.     
    8.     int count = 0;
    9.     for (int i = 0; i < row; i++) {
    10.         for (int j = 0; j < col; j++) {
    11.             if (chessArr1[i][j] != 0) {
    12.                 count++;
    13.             }
    14.         }
    15.     }
    16.     int[][] parseArr = new int[count + 1][3];
    17.     parseArr[0][0] = row;
    18.     parseArr[0][1] = col;
    19.     parseArr[0][2] = count;
    20.     count = 1;
    21.     for (int i = 0; i < row; i++) {
    22.         for (int j = 0; j < col; j++) {
    23.             if (chessArr1[i][j] != 0) {
    24.                 parseArr[count][0] = i;
    25.                 parseArr[count][1] = j;
    26.                 parseArr[count][2] = chessArr1[i][j];
    27.                 count++;
    28.             }
    29.         }
    30.     }
    31.     
    32.     // write to io
    33.     String FILE = "D:\\Java\\parseArr.txt";
    34.     BufferedWriter bw = new BufferedWriter(new FileWriter(FILE));
    35.     for (int[] ints : parseArr) {
    36.         bw.write(Arrays.toString(ints));
    37.         bw.newLine();
    38.     }
    39.     bw.close();
    40.     
    41.     // read from io
    42.     BufferedReader br = new BufferedReader(new FileReader(FILE));
    43.     String tmpS = br.readLine();
    44.     String[] tmpSS = tmpS.substring(1, tmpS.length() - 1).split(",");
    45.     int[][] chessArr2 = new int[Integer.parseInt(tmpSS[0])][Integer.parseInt(tmpSS[1].trim())];
    46.     while (true) {
    47.         tmpS = br.readLine();
    48.         if (tmpS == null || tmpS.isEmpty()) break;
    49.         tmpSS = tmpS.substring(1, tmpS.length() - 1).split(",");
    50.         chessArr2[Integer.parseInt(tmpSS[0])][Integer.parseInt(tmpSS[1].trim())] = Integer.parseInt(tmpSS[2].trim());
    51.     }
    52.     br.close();

    程序员常用的十大算法：

    二分查找算法：

    分治算法：

    动态规划算法：

    KMP算法：

    字符串匹配；

    贪心算法

    贪心算法的结果不一定是最优解；

    每一次选择都是一次最优解；

    应用案例，集合覆盖问题

    1、遍历所有电台，找到一个覆盖了最多未覆盖地区的电台；

    2、将这些电台加入到如ArrayList等集合，想办法把该电台覆盖的地区在下次比较时去掉；

    3、重复第一步直到覆盖了全部的地区；

    1. import java.util.*;
    2.  
    3. public class GreedyAlgorithm {
    4.     public static void main(String[] args) {
    5.         // 贪心算法
    6.         // 创建广播电台
    7.         Map> broadCasts = new HashMap<>();
    8.         // 将各个电台放入到broadCasts
    9.         HashSet hashSet1 = new HashSet<>();
    10.         hashSet1.add("北京");
    11.         hashSet1.add("上海");
    12.         hashSet1.add("天津");
    13.         HashSet hashSet2 = new HashSet<>();
    14.         hashSet2.add("广州");
    15.         hashSet2.add("北京");
    16.         hashSet2.add("深圳");
    17.         HashSet hashSet3 = new HashSet<>();
    18.         hashSet3.add("成都");
    19.         hashSet3.add("上海");
    20.         hashSet3.add("杭州");
    21.         HashSet hashSet4 = new HashSet<>();
    22.         hashSet4.add("上海");
    23.         hashSet4.add("天津");
    24.         HashSet hashSet5 = new HashSet<>();
    25.         hashSet5.add("杭州");
    26.         hashSet5.add("大连");
    27.         broadCasts.put("k1", hashSet1);
    28.         broadCasts.put("k2", hashSet2);
    29.         broadCasts.put("k3", hashSet3);
    30.         broadCasts.put("k4", hashSet4);
    31.         broadCasts.put("k5", hashSet5);
    32.         // 存放所有的地区
    33.         HashSet allAreas = new HashSet<>();
    34.         allAreas.add("北京");
    35.         allAreas.add("上海");
    36.         allAreas.add("天津");
    37.         allAreas.add("广州");
    38.         allAreas.add("深圳");
    39.         allAreas.add("成都");
    40.         allAreas.add("杭州");
    41.         allAreas.add("大连");
    42.         // 存放选择的电台K集合
    43.         List selects = new ArrayList<>();
    44.         // 临时的集合，在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
    45.         HashSet tempSet = new HashSet<>();
    46.         // 保存在一次遍历过程中，能够覆盖最大未覆盖地区对应的电台的key
    47.         String maxKey = null;
    48.         // 如果maxKey不等于空，则会加入到selects
    49.         while (allAreas.size() != 0) { // 如果allAreas不为0，则还没有覆盖到所有地区
    50.             maxKey = null;
    51.             for (String key : broadCasts.keySet()) {
    52.                 tempSet.clear();
    53.                 // 当前电台能够覆盖的地区
    54.                 HashSet areas = broadCasts.get(key);
    55.                 tempSet.addAll(areas);
    56.                 // 求交集，赋值给tempSet
    57.                 tempSet.retainAll(allAreas);
    58.                 // 如果当前集合包含的未覆盖地区的数量，比maxKey指向的集合的未覆盖的地区还要多
    59.                 // 就需要重置maxKey
    60.                 // 每次都选择一个最优的K
    61.                 if (tempSet.size() > 0 && (maxKey == null || (tempSet.size() > broadCasts.get(maxKey).size()))) {
    62.                     maxKey = key;
    63.                 }
    64.             }
    65.             if (maxKey != null) {
    66.                 selects.add(maxKey);
    67.                 // 将maxKey指向的广播电台覆盖的地区从allAreas清除掉
    68.                 allAreas.removeAll(broadCasts.get(maxKey));
    69.             }
    70.         }
    71.     }
    72. }

    普里姆算法

    最小生成树MST问题，也叫最修路问题；

    1）给一个带权的无向连通图，如何选取一棵生成树，使树上所有的边上权的总和为最小；

    2）N个顶点，一定有N-1条边；

    3）最小生成树主要是普里姆算法和克鲁斯卡尔算法；

    1. public class PrimAlgorithm {
    2.     public static void main(String[] args) {
    3.         // 普利姆算法
    4.         // 用到了邻接矩阵
    5.         char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    6.         int verxs = data.length;
    7.         // 邻接矩阵,10000表示不联通
    8.         int[][] weight = {
    9.                 {10000, 5, 7, 10000, 10000, 10000, 2},
    10.                 {5, 10000, 10000, 9, 10000, 10000, 3},
    11.                 {7, 10000, 10000, 10000, 8, 10000, 10000},
    12.                 {10000, 9, 10000, 10000, 10000, 4, 10000},
    13.                 {10000, 10000, 8, 10000, 10000, 5, 4},
    14.                 {10000, 10000, 10000, 4, 5, 10000, 6},
    15.                 {2, 3, 10000, 10000, 4, 6, 10000}
    16.         };
    17.         MGraph graph = new MGraph(verxs);
    18.         MinTree minTree = new MinTree();
    19.         minTree.createGraph(graph, verxs, data, weight);
    20.         // 打印
    21.         minTree.showGraph(graph);
    22.         // 普利姆算法
    23.         minTree.prim(graph, 0);
    24.     }
    25. }
    26.  
    27. /**
    28.  * 创建最小生成树
    29.  */
    30. class MinTree {
    31.     /**
    32.      * 创建邻接矩阵
    33.      *
    34.      * @param graph  图对象
    35.      * @param verxs  图对应的顶点的个数
    36.      * @param data   图的各个顶点的值
    37.      * @param weight 图的邻接矩阵
    38.      */
    39.     public void createGraph(MGraph graph, int verxs, char[] data, int[][] weight) {
    40.         for (int i = 0; i < verxs; i++) {
    41.             graph.data[i] = data[i];
    42.             for (int j = 0; j < verxs; j++) {
    43.                 graph.weight[i][j] = weight[i][j];
    44.             }
    45.         }
    46.     }
    47.  
    48.     /**
    49.      * 显示图的邻接矩阵
    50.      */
    51.     public void showGraph(MGraph graph) {
    52.         for (int[] link : graph.weight) {
    53.             System.out.println(Arrays.toString(link));
    54.         }
    55.     }
    56.  
    57.     /**
    58.      * ;/
    59.      * 普利姆最小生成树算法
    60.      *
    61.      * @param graph 图
    62.      * @param v     图的第几个顶点开始生成 'A'->0 'B'->1
    63.      */
    64.     public void prim(MGraph graph, int v) {
    65.         // 标记节点是否被访问过
    66.         int[] visited = new int[graph.verxs];
    67.         // 把当前节点标记为已访问
    68.         visited[v] = 1;
    69.         // 用h1和h2记录两个顶点的下标
    70.         int h1 = -1;
    71.         int h2 = -1;
    72.         int minWeight = 10000;
    73.         // 因为又graph.verxs个顶点，所以算法结束后，有graph.verxs-1条边
    74.         for (int k = 1; k < graph.verxs; k++) {
    75.             // 确定每一次生成的子图，和哪个节点的距离最近
    76.             for (int i = 0; i < graph.verxs; i++) { // 遍历已经访问过的节点
    77.                 for (int j = 0; j < graph.verxs; j++) { // 遍历所有没有访问过的节点
    78.                     if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
    79.                         // 已访问
    80.                         minWeight = graph.weight[i][j];
    81.                         h1 = i;
    82.                         h2 = j;
    83.                     }
    84.                 }
    85.             }
    86.             System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);
    87.             // 标记已经访问
    88.             visited[h2] = 1;
    89.             minWeight = 10000;
    90.         }
    91.     }
    92. }
    93.  
    94. class MGraph {
    95.     /**
    96.      * 表示图的节点的个数
    97.      */
    98.     int verxs;
    99.     /**
    100.      * 存放节点的数据
    101.      */
    102.     char[] data;
    103.     /**
    104.      * 存放边，邻接矩阵
    105.      */
    106.     int[][] weight;
    107.  
    108.     public MGraph(int verxs) {
    109.         this.verxs = verxs;
    110.         data = new char[verxs];
    111.         weight = new int[verxs][verxs];
    112.     }
    113. }

    克鲁斯卡尔算法

    也是最小生成树算法；

    修路问题

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

    问题（1）对图的所有的边按照权值的大小进行排序；

    问题（2）将边添加到最小生成树中，判断是否形成了回路；

    1. public class KruskalCase {
    2.     /**
    3.      * 边的个数
    4.      */
    5.     int edgeNum;
    6.     /**
    7.      * 顶点的数组
    8.      */
    9.     char[] vertexs;
    10.     /**
    11.      * 邻接矩阵
    12.      */
    13.     int[][] matrix;
    14.     /**
    15.      * 最大值表示路不通
    16.      */
    17.     static final int INF = Integer.MAX_VALUE;
    18.  
    19.     public KruskalCase(char[] vertexs, int[][] matrix) {
    20.         // 初始化点和边的数量
    21.         int vlen = vertexs.length;
    22.         // 初始化顶点，复制
    23.         this.vertexs = new char[vlen];
    24.         for (int i = 0; i < vertexs.length; i++) {
    25.             this.vertexs[i] = vertexs[i];
    26.         }
    27.         // 初始化边，复制
    28.         this.matrix = new int[vlen][vlen];
    29.         for (int i = 0; i < vlen; i++) {
    30.             for (int j = 0; j < vlen; j++) {
    31.                 this.matrix[i][j] = matrix[i][j];
    32.             }
    33.         }
    34.         // 统计有多少条边
    35.         for (int i = 0; i < vlen; i++) {
    36.             for (int j = i + 1; j < vlen; j++) {
    37.                 if (matrix[i][j] != INF) {
    38.                     edgeNum++;
    39.                 }
    40.             }
    41.         }
    42.     }
    43.  
    44.     /**
    45.      * 打印邻接矩阵
    46.      */
    47.     public void print() {
    48.         System.out.println("邻接矩阵为：");
    49.         for (int i = 0; i < vertexs.length; i++) {
    50.             for (int j = 0; j < vertexs.length; j++) {
    51.                 System.out.printf("%10d\t", matrix[i][j]);
    52.             }
    53.             System.out.println(); // 换行
    54.         }
    55.     }
    56.  
    57.     /**
    58.      * 对边进行排序
    59.      *
    60.      * @param eData
    61.      */
    62.     private void sortEdges(EData[] eData) {
    63.         for (int i = 0; i < eData.length - 1; i++) {
    64.             for (int j = 0; j < eData.length - 1 - i; j++) {
    65.                 if (eData[j].weight > eData[j + 1].weight) {
    66.                     EData t = eData[j];
    67.                     eData[j] = eData[j + 1];
    68.                     eData[j + 1] = t;
    69.                 }
    70.             }
    71.         }
    72.     }
    73.  
    74.     /**
    75.      * @param ch 顶点的下标
    76.      * @return 顶点对应的下标
    77.      */
    78.     public int getPosition(char ch) {
    79.         for (int i = 0; i < vertexs.length; i++) {
    80.             if (vertexs[i] == ch) {
    81.                 return i;
    82.             }
    83.         }
    84.         return -1;
    85.     }
    86.  
    87.     /**
    88.      * 获取图中的边，放到EData[]数组中，后面我们需要遍历该数组
    89.      * 通过matrix邻接矩阵来获取
    90.      *
    91.      * @return
    92.      */
    93.     private EData[] getEdges() {
    94.         int index = 0;
    95.         EData[] edges = new EData[edgeNum];
    96.         for (int i = 0; i < vertexs.length; i++) {
    97.             for (int j = i + 1; j < vertexs.length; j++) {
    98.                 // 有多少条边
    99.                 if (matrix[i][j] != INF) {
    100.                     edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
    101.                 }
    102.             }
    103.         }
    104.         return edges;
    105.     }
    106.  
    107.     /**
    108.      * 获取下标为i的顶点的终点的下标，用于后面判断两个顶点的终点是否相同
    109.      *
    110.      * @param ends 数组对应了各个顶点对应的终点是哪个
    111.      * @param i    表示的传入的顶点对应的下标
    112.      * @return
    113.      */
    114.     private int getEnd(int[] ends, int i) {
    115.         while (ends[i] != 0) {
    116.             i = ends[i];
    117.         }
    118.         return i;
    119.     }
    120.  
    121.     public void kruskal() {
    122.         // 最后结果数组的索引
    123.         int index = 0;
    124.         // 用于保存已有最小生成树，中的每个顶点在最小生成树中的终点
    125.         int[] ends = new int[edgeNum];
    126.         // 保存最后的最小生成树
    127.         EData[] rets = new EData[edgeNum];
    128.         // 获取图中所有的边的集合，一共有12条边
    129.         EData[] edges = getEdges();
    130.         sortEdges(edges);
    131.         // 遍历edges数组，并且确认不回路
    132.         for (int i = 0; i < edges.length; i++) {
    133.             // 获取第i条边的起点
    134.             int p1 = getPosition(edges[i].start);
    135.             // 获取第i条边的终点
    136.             int p2 = getPosition(edges[i].end);
    137.             // 获取p1这个顶点在已有最小生成树中的终点，（重要）
    138.             int m = getEnd(ends, p1);
    139.             // 获取p2这个顶点在已有最小生成树中的终点
    140.             int n = getEnd(ends, p2);
    141.             // 没有构成回路
    142.             if (m != n) {
    143.                 // 设置m在最小生成树中的终点
    144.                 ends[m] = n;
    145.                 // 有一条边加入rets数组
    146.                 rets[index++] = edges[i];
    147.             }
    148.         }
    149.     }
    150.  
    151.     public static void main(String[] args) {
    152.         char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    153.         // 0,0 表示自己到自己的距离
    154.         int[][] matrix = {
    155.                 {0, 12, INF, INF, INF, 16, 14},
    156.                 {12, 0, 10, INF, INF, 7, INF},
    157.                 {INF, 10, 0, 3, 5, 6, INF},
    158.                 {INF, INF, 3, 0, 4, INF, INF},
    159.                 {INF, INF, 5, 4, 0, 2, 8},
    160.                 {16, 7, 6, INF, 2, 0, 9},
    161.                 {14, INF, INF, INF, 8, 9, 0}
    162.         };
    163.         KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
    164.         kruskalCase.print();
    165.         EData[] edges = kruskalCase.getEdges();
    166.         kruskalCase.sortEdges(edges);
    167.         kruskalCase.kruskal();
    168.     }
    169. }
    170.  
    171. /**
    172.  * 对象的实例表示一条边
    173.  * {'A','B',12}
    174.  */
    175. class EData {
    176.     /**
    177.      * 边的起点
    178.      */
    179.     char start;
    180.     /**
    181.      * 边的终点
    182.      */
    183.     char end;
    184.     /**
    185.      * 边的权值
    186.      */
    187.     int weight;
    188.  
    189.     public EData(char start, char end, int weight) {
    190.         this.start = start;
    191.         this.end = end;
    192.         this.weight = weight;
    193.     }
    194.  
    195.     @Override
    196.     public String toString() {
    197.         return "EData{" +
    198.                 "start=" + start +
    199.                 ", end=" + end +
    200.                 ", weight=" + weight +
    201.                 '}';
    202.     }
    203. }

    迪杰斯特拉算法

    最短路径算法，是图的广度遍历；

    求出一个顶点到其他顶点的距离；

    1. public class DijkstraAlgorithm {
    2. }
    3.  
    4. class Graph {
    5.     /**
    6.      * 顶点数组
    7.      */
    8.     char[] vertex;
    9.     /**
    10.      * 邻接矩阵
    11.      */
    12.     int[][] matrix;
    13.  
    14.     public Graph(char[] vertex, int[][] matrix) {
    15.         this.vertex = vertex;
    16.         this.matrix = matrix;
    17.     }
    18.  
    19.     /**
    20.      * 显示图
    21.      */
    22.     public void showGraph() {
    23.         for (int[] link : matrix) {
    24.             System.out.println(Arrays.toString(link));
    25.         }
    26.     }
    27.  
    28.     /**
    29.      * 已经访问的顶点的集合
    30.      */
    31.     VisitedVertex vv;
    32.  
    33.     /**
    34.      * 迪杰斯特拉算法
    35.      *
    36.      * @param index 出发点，已经访问的节点
    37.      */
    38.     public void dsj(int index) {
    39.         vv = new VisitedVertex(vertex.length, index);
    40.         // 更新index下标的顶点到周围的顶点的距离和前驱顶点
    41.         update(index);
    42.         for (int j = 1; j < vertex.length; j++) {
    43.             index = vv.updateArr();
    44.             update(index);
    45.         }
    46.     }
    47.  
    48.     /**
    49.      * 更新index下标顶点到周围的顶点的距离，和周围顶点的前驱顶点
    50.      *
    51.      * @param index
    52.      */
    53.     private void update(int index) {
    54.         int len = 0;
    55.         for (int j = 0; j < matrix[index].length; j++) {
    56.             // len：出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的 合
    57.             len = vv.getDis(index) + matrix[index][j];
    58.             if (!vv.in(j) && len < vv.getDis(j)) {
    59.                 vv.updatePre(j, index);
    60.                 vv.updateDis(j, len);
    61.             }
    62.         }
    63.     }
    64.  
    65.     public static void main(String[] args) {
    66.         char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    67.         int[][] matrix = new int[vertexs.length][vertexs.length];
    68.         final int N = 65535;
    69.         matrix[0] = new int[]{N, 5, 7, N, N, N, 2};
    70.         matrix[1] = new int[]{5, N, N, 9, N, N, 3};
    71.         matrix[2] = new int[]{7, N, N, N, 8, N, N};
    72.         matrix[3] = new int[]{N, 9, N, N, N, 4, N};
    73.         matrix[4] = new int[]{N, N, 8, N, N, 5, 4};
    74.         matrix[5] = new int[]{N, N, N, 4, 5, N, 6};
    75.         matrix[6] = new int[]{2, 3, N, N, 4, 6, N};
    76.         Graph graph = new Graph(vertexs, matrix);
    77.         graph.showGraph();
    78.         // 迪杰斯特拉算法，从G 6这个点到其他节点的距离
    79.         graph.dsj(2);
    80.     }
    81. }
    82.  
    83. /**
    84.  * 已访问的顶点的集合
    85.  */
    86. class VisitedVertex {
    87.     /**
    88.      * 1已访问 0未访问
    89.      */
    90.     int[] already_arr;
    91.     /**
    92.      * 每一个下标对应的值为前一个顶点，会动态更新
    93.      */
    94.     int[] pre_visited;
    95.     /**
    96.      * 记录出发顶点到其他所有顶点的最短距离，会动态更新
    97.      */
    98.     int[] dis;
    99.  
    100.     /**
    101.      * @param length 表示顶点的个数
    102.      * @param index  出发顶点
    103.      */
    104.     public VisitedVertex(int length, int index) {
    105.         this.already_arr = new int[length];
    106.         this.pre_visited = new int[length];
    107.         this.dis = new int[length];
    108.         // 初始化dis数组
    109.         Arrays.fill(dis, 65535);
    110.         // 设置出发顶点被访问过
    111.         this.already_arr[index] = 1;
    112.         // 设置出发顶点的访问距离为0
    113.         this.dis[index] = 0;
    114.     }
    115.  
    116.     /**
    117.      * 判断index下标对应的顶点是否被访问过
    118.      *
    119.      * @param index
    120.      * @return 如果访问过就返回true
    121.      */
    122.     public boolean in(int index) {
    123.         return already_arr[index] == 1;
    124.     }
    125.  
    126.     /**
    127.      * 更新出发顶点到index顶点的距离
    128.      *
    129.      * @param index
    130.      * @param len
    131.      */
    132.     public void updateDis(int index, int len) {
    133.         dis[index] = len;
    134.     }
    135.  
    136.     /**
    137.      * 更新顶点pre的前驱为index的顶点
    138.      *
    139.      * @param pre
    140.      * @param index
    141.      */
    142.     public void updatePre(int pre, int index) {
    143.         pre_visited[pre] = index;
    144.     }
    145.  
    146.     /**
    147.      * 返回出发顶点到index顶点的距离
    148.      *
    149.      * @param index
    150.      * @return
    151.      */
    152.     public int getDis(int index) {
    153.         return dis[index];
    154.     }
    155.  
    156.     /**
    157.      * 继续选择并返回新的未访问的访问顶点
    158.      *
    159.      * @return
    160.      */
    161.     public int updateArr() {
    162.         int min = 65535, index = 0;
    163.         for (int i = 0; i < already_arr.length; i++) {
    164.             // 没有被访问
    165.             if (already_arr[i] == 0 && dis[i] < min) {
    166.                 min = dis[i];
    167.                 index = i;
    168.             }
    169.         }
    170.         // 标记已访问
    171.         already_arr[index] = 1;
    172.         return index;
    173.     }
    174. }

    弗洛伊德算法

    也是求最小路径的算法；

    效率没有迪杰斯特拉算法快；

    计算每个顶点到其他各个顶点的最短路径；

    1. public class FloydAlgorithm {
    2.     public static void main(String[] args) {
    3.         char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    4.         final int N = 65535;
    5.         int[][] matrix = new int[vertexs.length][vertexs.length];
    6.         matrix[0] = new int[]{0, 5, 7, N, N, N, 2};
    7.         matrix[1] = new int[]{5, 0, N, 9, N, N, 2};
    8.         matrix[2] = new int[]{7, N, 0, N, 8, N, N};
    9.         matrix[3] = new int[]{N, 9, N, 0, N, 4, N};
    10.         matrix[4] = new int[]{N, N, 8, N, 0, 5, 4};
    11.         matrix[5] = new int[]{N, N, N, 4, 5, 0, 6};
    12.         matrix[6] = new int[]{2, 3, N, N, 4, 6, 0};
    13.         Graph graph = new Graph(vertexs.length, matrix, vertexs);
    14.         graph.floyd();
    15.         graph.show();
    16.     }
    17. }
    18.  
    19. /**
    20.  * 创建图
    21.  */
    22. class Graph {
    23.     /**
    24.      * 存放顶点的数组
    25.      */
    26.     char[] vertex;
    27.     /**
    28.      * 保存从各个顶点出发，到其他顶点的距离
    29.      */
    30.     int[][] dis;
    31.     /**
    32.      * 保存到达目标顶点的前驱顶点
    33.      */
    34.     int[][] pre;
    35.  
    36.     /**
    37.      * 构造方法
    38.      *
    39.      * @param length 多少个顶点
    40.      * @param matrix 邻接表
    41.      * @param vertex 顶点的数组
    42.      */
    43.     public Graph(int length, int[][] matrix, char[] vertex) {
    44.         this.vertex = vertex;
    45.         this.dis = matrix;
    46.         this.pre = new int[length][length];
    47.         for (int i = 0; i < length; i++) {
    48.             Arrays.fill(pre[i], i);
    49.         }
    50.     }
    51.  
    52.     /**
    53.      * 显示pre和dis数组
    54.      */
    55.     public void show() {
    56.         for (int k = 0; k < dis.length; k++) {
    57.             // 先将pre数组输出
    58.             for (int i = 0; i < dis.length; i++) {
    59.                 System.out.print(vertex[pre[k][i]] + " ");
    60.             }
    61.             System.out.println();
    62.             // 输出dis数组
    63.             for (int i = 0; i < dis.length; i++) {
    64.                 System.out.print("(" + vertex[k] + "到" + vertex[i] + "的最短路径是" + dis[k][i] + ") ");
    65.             }
    66.             System.out.println();
    67.             System.out.println();
    68.         }
    69.     }
    70.  
    71.     /**
    72.      * 弗洛伊德算法
    73.      */
    74.     public void floyd() {
    75.         // 变量的距离
    76.         int len = 0;
    77.         // 对中间顶点遍历，k就是中间顶点的下标
    78.         for (int k = 0; k < dis.length; k++) {
    79.             // 从i顶点开始出发['A','B']
    80.             for (int i = 0; i < dis.length; i++) { // 行
    81.                 for (int j = 0; j < dis.length; j++) {
    82.                     // 从顶点i出发，经过k中间节点，到达顶点j的距离
    83.                     len = dis[i][k] + dis[k][j];
    84.                     if (dis[i][j] > len) {
    85.                         dis[i][j] = len;
    86.                         // 前驱顶点
    87.                         pre[i][j] = pre[k][j];
    88.                     }
    89.                 }
    90.             }
    91.         }
    92.     }
    93. }

    马踏棋盘算法

    也叫骑士周游问题，回溯算法或贪心算法，是图的深度优先搜索的应用；

    1. public class HorseChessBoard {
    2.     /**
    3.      * 棋盘的列
    4.      */
    5.     static int X;
    6.     /**
    7.      * 棋盘的行
    8.      */
    9.     static int Y;
    10.  
    11.     /**
    12.      * 根据当前的位置，计算马还能走哪些位置
    13.      *
    14.      * @param curPoint
    15.      * @return
    16.      */
    17.     static ArrayList next(Point curPoint) {
    18.         ArrayList ps = new ArrayList<>();
    19.         Point p1 = new Point();
    20.         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
    21.             ps.add(new Point(p1));
    22.         }
    23.         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
    24.             ps.add(new Point(p1));
    25.         }
    26.         if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
    27.             ps.add(new Point(p1));
    28.         }
    29.         if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
    30.             ps.add(new Point(p1));
    31.         }
    32.         if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
    33.             ps.add(new Point(p1));
    34.         }
    35.         if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
    36.             ps.add(new Point(p1));
    37.         }
    38.         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
    39.             ps.add(new Point(p1));
    40.         }
    41.         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
    42.             ps.add(new Point(p1));
    43.         }
    44.         return ps;
    45.     }
    46.  
    47.     /**
    48.      * 根据当前这一步的所有下一步的选择位置，进行非递减排序
    49.      *
    50.      * @param ps
    51.      */
    52.     static void sort(ArrayList ps) {
    53.         ps.sort(new Comparator() {
    54.             @Override
    55.             public int compare(Point o1, Point o2) {
    56.                 int count1 = next(o1).size();
    57.                 int count2 = next(o2).size();
    58.                 return count1 - count2;
    59.             }
    60.         });
    61.     }
    62.  
    63.     /**
    64.      * 标记棋盘是否被访问过
    65.      */
    66.     static boolean visited[];
    67.     /**
    68.      * 标记棋盘的所有位置是否都被访问过了
    69.      */
    70.     static boolean finished;
    71.  
    72.     /**
    73.      * 完成骑士周游问题的算法
    74.      *
    75.      * @param chessBoard 棋盘
    76.      * @param row        马当前的位置，从0开始
    77.      * @param column     马当前的位置，从0开始
    78.      * @param step       第几步，从1开始
    79.      */
    80.     static void traversalChessboard(int[][] chessBoard, int row, int column, int step) {
    81.         chessBoard[row][column] = step;
    82.         // 标记已访问
    83.         visited[row * X + column] = true;
    84.         ArrayList ps = next(new Point(column, row));
    85.         // 非递减排序，贪心思想
    86.         sort(ps);
    87.         while (!ps.isEmpty()) {
    88.             // 取出一个可以走的位置
    89.             Point p = ps.remove(0);
    90.             // 该点未访问
    91.             if (!visited[p.y * X + p.x]) {
    92.                 traversalChessboard(chessBoard, p.y, p.x, step + 1);
    93.             }
    94.         }
    95.         // 1、棋盘还没有走完
    96.         // 2、棋盘走完了，但还在回溯
    97.         if (step < X * Y && !finished) {
    98.             chessBoard[row][column] = 0;
    99.             visited[row * X + column] = false;
    100.         } else {
    101.             finished = true;
    102.         }
    103.     }
    104.  
    105.     public static void main(String[] args) {
    106.         X = 8;
    107.         Y = 8;
    108.         int row = 1;
    109.         int column = 1;
    110.         int[][] chessBoard = new int[Y][X];
    111.         visited = new boolean[X * Y];
    112.         long startTime = System.currentTimeMillis();
    113.         traversalChessboard(chessBoard, row - 1, column - 1, 1);
    114.         long endTime = System.currentTimeMillis() - startTime;
    115.     }
    116. }

     

    参考视频：【尚硅谷】数据结构与算法（Java数据结构与算法）_哔哩哔哩_bilibili

  • 相关阅读:
    几行代码实现用Python输出表情包
    MobileNetV3
    Ps：锁定图层
    OneFlow学习笔记：从Python到C++调用过程分析
    jenkins搭建
    C++学习第十课--构造函数详解、explicit与初始化列表笔记
    前端面试第一周快速复盘，不标准的面试经验分享 （一）
    Toxel 与 PCPC II
    rabbitmq安装部署和常用命令
    uniapp的小程序中使用web-view进行相互传参，并监听web-view的返回键
  • 原文地址：https://blog.csdn.net/m0_58961367/article/details/133514195