哪里有专门做网站的/国外媒体报道
取自韩顺平数据结构与算法的总结
文章目录
- 二分查找算法的非递归实现
- 分治算法
- 动态规划算法
- KMP算法
- 贪心算法
- 普里姆算法
- 克鲁斯卡尔算法
- 迪杰斯特拉算法
- 弗洛伊德算法
- 马踏棋盘算法
二分查找算法的非递归实现
- 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找
- 二分查找法的运行时间为对数时间 O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n 步，假设从[0,99]的队列(100 个数，即 n=100)中寻到目标数 30，则需要查找步数为㏒₂100 , 即最多需要查找 7 次( 2^6 < 100 < 2 ^ 7)
public class BinarySearchNoRecursion {public static void main(String[] args) {//测试int[] arr = {1, 3, 8, 10, 11, 67, 100};int index = binarySearch(arr, -8);System.out.println("index = " + index);//}// 二分查找的非递归实现public static int binarySearch(int[] arr, int target){int left = 0;int right = arr.length - 1;int mid;while (left<=right){mid = (left + right) / 2;if (target == arr[mid]){return mid;}else if (target < arr[mid]){right = mid - 1; // 向左边}else {left = mid + 1; // 向右边}}return -1;}
}
分治算法
-
分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
-
分治算法可以求解的一些经典问题: 二分搜索 大整数乘法 棋盘覆盖 合并排序 快速排序 线性时间选择 最接近点对问题 循环赛日程表 汉诺塔
分治法在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
- 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
- 合并：将各个子问题的解合并为原问题的解。
汉诺塔问题思路分析:
-
如果是有一个盘， A->C
如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2.上面的盘 -
先把 最上面的盘 A->B
-
把最下边的盘 A->C
-
把 B 塔的所有盘 从 B->C
分治算法: 汉诺塔
public class Hanoitower {public static void main(String[] args) {hanoitower(64, 'A', 'B', 'C');}// 分治算法: 汉诺塔public static void hanoitower(int n, char a, char b, char c){if (n==1){// 剩一个盘时System.out.println("第1个盘: "+ a + " -> " + c);}else {// 将上面的n-1个盘从a盘借助c盘移动到b盘hanoitower(n-1, a, c, b);// 将最下面的第N个盘从a移动到cSystem.out.printf("第%d个盘: %c -> %c\n", n, a, c);// 将b上的n-1个盘从b借助a移动到chanoitower(n-1, b, a, c);}}
}
动态规划算法
背包问题
- 要求达到的目标为装入的背包的总价值最大，并且重量不超出
- 要求装入的物品不能重复
import java.util.Arrays;public class KnapsackProblem {public static void main(String[] args) {int[] w = {1, 4, 3}; // 物品的重量int[] v = {1500, 3000, 2000}; // 物品的价值int m = 4; // 背包的容量int n = w.length; // 物体的个数// 创建二维数组表示当前容量为j时, 添加第i个物品后背包所能容纳的最大总价值int[][] totalV = new int[n+1][m+1];// 记录背包放入的新物品int[][] newT = new int[n+1][m+1];// 将第一行(表示没有物品时)和第一列(表示背包容量为0时)填充零for (int i = 0; i < totalV.length; i++) {totalV[i][0] = 0;}for (int j = 0; j < totalV[0].length; j++) {totalV[0][j] = 0;}// 从容量为1, 即j=1时开始for (int j = 1; j <= m; j++) {// 从第一件商品开始for (int i = 1; i <= n; i++) {// 如果当前新加物品的容量超过背包的总容量// i-1时因为i是从1开始// ****注意: w[i-1]表示当前物品的重量, v[i-1]表示当前物品的价值if (w[i-1] > j){// 则背包能容纳的最大价值为上面未加此物品能容纳的最大价值totalV[i][j] = totalV[i-1][j];}else { // 如果当前新加物品的容量小于等于背包的总容量// 则背包能容纳的最大价值为:// (可以这样理解, 在"背包容量固定"的条件下, 如果要放入新的物品, 则需要将背包中之前的物品取出来)// 所以最大价值为, 在同一背包容量下,// 1. [没有新物品时的最大价值] 与 2. [取出之前放入的所有物品,将新物品放入后的价值// 然后再加(背包容量减去新物品占用的容量后剩余容量所能容纳的最大价值)的和] 这两项的最大值totalV[i][j] = Math.max(totalV[i-1][j], v[i-1] + totalV[i-1][j - w[i-1]]);// 记录背包放入的新物品if(totalV[i-1][j] < v[i-1] + totalV[i-1][j - w[i-1]]){newT[i][j] = 1;}}}}for (int[] arr: totalV){System.out.println(Arrays.toString(arr));}// 输出背包放入的物品for (int j = newT[0].length - 1; j > 0; j--) {for (int i = newT.length-1; i > 0; i--) {if(newT[i][j] == 1){System.out.println("放入第" + i + "件物品");// 容量 j - 取出物品的容量j -= w[i-1];}}}}
}
KMP算法
字符串暴力匹配
package kmp;public class ViolenceMatch {public static void main(String[] args) {// 测试暴力匹配算法String str1 = "Hello He wo Hello World pythoncc";String str2 = "Hello World";int index = violenceMatch(str1, str2);System.out.println("index = " + index);}// 暴力匹配// 在s1中匹配s2public static int violenceMatch(String s1, String s2){// 转成字符数组char[] cs1 = s1.toCharArray();char[] cs2 = s2.toCharArray();int i=0; // 指向s1int j=0; // 指向s2while (i<s1.length() && j<s2.length()){ // 保证匹配时不越界// 如果匹配则检查下一个字符if (cs1[i]==cs2[j]){i++;j++;}else { // 如果这个字符不匹配, 则i回到之前位置的下一个位置,继续进行匹配i = i - j + 1;j = 0;}}// 在匹配到s2, 则返回匹配的首部的索引if (j==s2.length()){return i - s2.length();}return -1;}
}
利用KMP算法
(看不懂就背) … emmnn 巴适
详细解释: https://blog.csdn.net/v_july_v/article/details/7041827
package kmp;// https://blog.csdn.net/v_july_v/article/details/7041827import java.util.Arrays;public class KMPAlgorithm {public static void main(String[] args) {// String s = "ababcddac";
// int[] next = getNextArr(s);
// System.out.println(Arrays.toString(next));String str1 = "BBC ABCDAB ABCDABCDABDE";String str2 = "ABCDABD";//String str2 = "BBC";int[] next = getNextArr(str2); //[0, 1, 2, 0]System.out.println("next = " + Arrays.toString(next));int index = kmp(str1, str2, next);System.out.println("index = " + index);}public static int kmp(String s1, String s2, int[] next){char[] c1 = s1.toCharArray();char[] c2 = s2.toCharArray();int j = 0; // 指向s2for (int i = 0; i < c1.length; i++) {while (j>0 && c1[i] != c2[j]){j = next[j-1];}if (c1[i]== c2[j]){j++;}if (j==c2.length){return i - j + 1;}}return -1;}public static int[] getNextArr(String s){char[] c = s.toCharArray();int[] next = new int[s.length()];next[0] = 0;int j = 0; // 前缀位置 及i所在位置子串的最大公共前后缀长度for (int i = 1; i < next.length; i++) {while (j>0 && c[i] != c[j]){ // ***KMP核心***j = next[j-1];}if (c[i] == c[j]){j++;next[i] = j;}}return next;}
}
贪心算法
- 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法
- 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;public class GreedyAlgorithm {public static void main(String[] args) {// 创建广播台, 放入到MapHashMap<String, HashSet<String>> broadcasts = new HashMap<>();// 将各个电台放入到broadcastsHashSet<String> hashSet1 = new HashSet<String>();hashSet1.add("北京");hashSet1.add("上海");hashSet1.add("天津");HashSet<String> hashSet2 = new HashSet<String>();hashSet2.add("广州");hashSet2.add("北京");hashSet2.add("深圳");HashSet<String> hashSet3 = new HashSet<String>();hashSet3.add("成都");hashSet3.add("上海");hashSet3.add("杭州");HashSet<String> hashSet4 = new HashSet<String>();hashSet4.add("上海");hashSet4.add("天津");HashSet<String> hashSet5 = new HashSet<String>();hashSet5.add("杭州");hashSet5.add("大连");// 加入mapbroadcasts.put("K1", hashSet1);broadcasts.put("K2", hashSet2);broadcasts.put("K3", hashSet3);broadcasts.put("K4", hashSet4);broadcasts.put("K5", hashSet5);// 存放所有地区HashSet<String> allAreas = new HashSet<>();allAreas.add("北京");allAreas.add("上海");allAreas.add("天津");allAreas.add("广州");allAreas.add("深圳");allAreas.add("成都");allAreas.add("杭州");allAreas.add("大连");// 存放选择的电台List<String> select = new ArrayList<>();// 存取对应的未覆盖地区的相交地区的个数HashMap<String, Integer> retNum = new HashMap<>();// 取交集用HashSet<String> temp = new HashSet<>();String maxKey = null;while (allAreas.size()!=0){ // 没有覆盖到所有地区maxKey = null;retNum.clear();for (String key: broadcasts.keySet()){temp.clear();// 将当前key对应电台能覆盖的地区加入temptemp.addAll(broadcasts.get(key));// 取交集temp.retainAll(allAreas);retNum.put(key, temp.size());if (maxKey == null){maxKey = key;}else if (temp.size() > retNum.get(maxKey)){maxKey = key;}}select.add(maxKey);allAreas.removeAll(broadcasts.get(maxKey));}System.out.println(select);}
}
最小生成树修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称 MST。给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
- N 个顶点，一定有 N-1 条边
- 包含全部顶点
- N-1 条边都在图中
普里姆算法
import java.util.Arrays;public class PrimAlgorithm {public static void main(String[] args) {// 测试char[] data = new char[]{'A','B','C','D','E','F','G'};int verxs = data.length;// 邻接矩阵的关系使用二维数组表示,10000表示两个点不联通int [][]weight = new int[][]{{10000,5,7,10000,10000,10000,2},{5,10000,10000,9,10000,10000,3},{7,10000,10000,10000,8,10000,10000},{10000,9,10000,10000,10000,4,10000},{10000,10000,8,10000,10000,5,4},{10000,10000,10000,4,5,10000,6},{2,3,10000,10000,4,6,10000}};// 创建MGraph对象MGraph graph = new MGraph(verxs);// 创建MinTree对象MinTree minTree = new MinTree();minTree.createGraph(graph, verxs, data, weight);// 输出minTree.showGraph(graph);// 测试普利姆算法minTree.prim(graph, 0);}}class MinTree{/*** 创建图的邻接矩阵* @param graph 图对象* @param verxs 图对应的顶点个数* @param data 图的各个顶点的值* @param weight 图的邻接矩阵*/public void createGraph(MGraph graph, int verxs, char data[], int[][] weight){int i, j;for(i = 0; i < verxs; i++){graph.data[i] = data[i];
// for (j = 0; j < verxs; j++) {
// graph.weight[i][j] = weight[i][j];
// }}graph.weight = weight;}// 显示图的邻接矩阵public void showGraph(MGraph graph){for (int[] link: graph.weight){System.out.println(Arrays.toString(link));}}/*** 编写prim算法, 得到的最小生成树* @param graph 图* @param v 表示从图的第几个顶点开始 'A'->0 'B'->1...*/public void prim(MGraph graph, int v){// 标记是否被访问过int[] visited = new int[graph.verxs];// 把当前这个节点标记为已访问visited[v] = 1;// h1 和 h2记录新找出的边的两个顶点的下标int h1 = -1;int h2 = -1;int minWeight; // 初始化大一点// 找 n-1 条边for (int k = 1; k < graph.verxs; k++) {minWeight = 10000; // 重新初始化// 确定生成子图, 找已经访问节点的边里面权值最小的for (int i = 0; i < graph.verxs; i++) { // 用于表示已经访问的节点for (int j = 0; j < graph.verxs; j++) { // 用于表示未访问过的节点// 找访问过的点和未访问的节点之间的边中权值最小的if (visited[i]==1&&visited[j]==0&&graph.weight[i][j]<minWeight){h1 = i; // 已访问节点h2 = j; // 未访问节点minWeight = graph.weight[i][j]; // 两点之间边的权值}}}// 将新找到的节点标记为已经访问visited[h2] = 1;System.out.printf("<%s, %s> => %s\n", graph.data[h1], graph.data[h2], minWeight);}}
}class MGraph{int verxs; // 节点数char[] data; // 存放节点数据int[][] weight; // 存放边信息(邻接矩阵)public MGraph(int verxs){this.verxs = verxs;data = new char[verxs];weight = new int[verxs][verxs];}
}
克鲁斯卡尔算法
关于终点的说明：
- 就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。
- 因此，接下来，虽然<C,E>是权值最小的边。但是 C 和 E 的终点都是 F，即它们的终点相同，因此，将<C,E>加入最小生成树的话，会形成回路。这就是判断回路的方式。也就是说，我们加入的边的两个顶点不能都指向同一个终点，否则将构成回路。
import java.util.Arrays;public class KruskalCase {public static void main(String[] args) {char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};// 邻接矩阵int matrix[][] = {/*A*//*B*//*C*//*D*//*E*//*F*//*G*//*A*/ { 0, 12, INF, INF, INF, 16, 14},/*B*/ { 12, 0, 10, INF, INF, 7, INF},/*C*/ { INF, 10, 0, 3, 5, 6, INF},/*D*/ { INF, INF, 3, 0, 4, INF, INF},/*E*/ { INF, INF, 5, 4, 0, 2, 8},/*F*/ { 16, 7, 6, INF, 2, 0, 9},/*G*/ { 14, INF, INF, INF, 8, 9, 0}};KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);kruskalCase.print();kruskalCase.kruskal();}private int edgeNum; // 边的个数private char[] vertexs; // 顶点数组private int[][] matrix; // 邻接矩阵// 使用INF表示两个顶点不能连通private static final int INF = Integer.MAX_VALUE;public KruskalCase(char[] vertexs, int[][] matrix){// 初始化顶点数和边的个数int vlen = vertexs.length;this.vertexs = vertexs;this.matrix = matrix;// 统计边的条数for (int i = 0; i < vlen; i++){// j = i+1 统计上半边对角三角形内的, 防止一条边统计两次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]; // 保存"已有最小生成树"中的每个顶点在最小生成树中的终点// 保存最后的最小生成树 n-1条边
// EData[] rets = new EData[edgeNum];EData[] rets = new EData[vertexs.length - 1];// 获取图中的所有边EData[] edges = getEdges();// 对边按照权值大小排序sortEdges(edges);// 将其中满足条件的n-1条边加入最小生成树中, 不能构成回路for (int i = 0; i < edgeNum; i++) {// 获取边始点的索引int p1 = getPosition(edges[i].start);// 获取边终点的索引int p2 = getPosition(edges[i].end);// 获取p1这个顶点在已有最小生成树中的终点int m = getEnd(ends, p1);// 获取p2这个顶点在已有最小生成树中的终点int n = getEnd(ends, p2);// 新加边的两个顶点的终点不同if (m!=n){// 将p1点对应的终点设置为p2点ends[m] = n;rets[index++] = edges[i];// n - 1条边够了if (index >= vertexs.length - 1){break;}}}System.out.println(Arrays.toString(rets));}// 打印邻接矩阵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();}}// 对边进行排序private void sortEdges(EData[] edges){EData tmp;int idx;for (int i = 0; i < edges.length - 1; i++) {idx = i;for (int j = i; j < edges.length; j++) {if (edges[j].weight < edges[idx].weight){idx = j;}}tmp = edges[i];edges[i] = edges[idx];edges[idx] = tmp;}}// 返回某顶点的索引private int getPosition(char ch){for (int i = 0; i < vertexs.length; i++) {if (vertexs[i] == ch){return i;}}// 没找到则返回-1return -1;}// 获取图中的边, 放到EData[] 数组中// EData[] 形式 [['A','B', 12], ['B','F',7], .....]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的顶点的终点, 用于判断两个顶点的终点是否相同private int getEnd(int[] ends, int i){while (ends[i]!=0){i = ends[i];}return i;}
}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;}public String toString() {return "EData [<" + start + ", " + end + "> = " + weight + "]";}
}
迪杰斯特拉算法
迪杰斯特拉(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 到达的)
- 重复执行两步骤，直到最短路径顶点为目标顶点即可结束
package dijkstra;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);graph.showGraph();// 测试迪杰斯特拉算法graph.dsj(6); // Ggraph.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));}}// 迪杰斯特拉算法实现public void dsj(int index){vv = new VisitedVertex(vertex.length, index);// 更新index顶点到周围顶点的距离和前驱顶点update(index);for (int j = 1; j < vertex.length; j++) {// 选择并返回新的访问顶点index = vv.updateArr();// 更新index顶点到周围顶点的距离和前驱顶点update(index);}}// 更新index下标顶点到周围顶点到触发节点的距离即其前驱节点private void update(int index){int len = 0;// 更新出发点到index周围点的最短距离for (int j = 0; j < matrix[index].length; j++) {len = vv.getDis(index) + matrix[index][j];// 如果j顶点没有被访问过, 并且len 小于出发点到j顶点的距离if (!vv.in(j) && len < vv.getDis(j)){// 更新前驱节点和最短距离vv.updatePre(j, index);vv.updateDis(j, len);}}}}// 已访问顶点的集合
class VisitedVertex{// 记录各个顶点是否访问过public int[] already_arr;// 每个前驱顶点的下标public int[] pre_visited;// 记录出发点到其他点的距离public int[] dis;/*** 构造器* @param length: 顶点个数* @param index: 出发顶点的下标*/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;// 设置出发顶点到自己的距离为0this.dis[index] = 0;}// 判断index对应的节点是否被访问过public boolean in(int index){return already_arr[index] == 1;}// 更新出发点到index对应顶点的距离public void updateDis(int index, int len){dis[index] = len;}// 更新index顶点的前驱顶点为pre对应的顶点public void updatePre(int index, int pre){pre_visited[index] = pre;}// 返回出发顶点到index顶点的距离public int getDis(int index){return dis[index];}// 继续选择并返回新的访问顶点public int updateArr(){int min = 65535;int 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(){// 输出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 = 0; i < dis.length; i++) {System.out.print((char)('A' + i) + "(" + dis[i] + ") ");}}
}
弗洛伊德算法
- 和 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，是以同样的方式获得
package floyd;import java.util.Arrays;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 = new Graph(vertex.length, matrix, vertex);graph.floyd();graph.show();}
}class Graph{private char[] vertex; // 存放顶点的数组private int[][] dis; // 存放各个顶点到其他顶点的距离private int[][] pre; // 保存到达目标顶点的前驱顶点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(){for (int k = 0; k < dis.length; k++) {for (int i = 0; i < dis.length; i++) {System.out.print((char)(pre[k][i] + 'A') + " ");}System.out.println();for (int i = 0; i < dis.length; i++) {System.out.print("(" + (char)('A' + k) + "到" + (char)(i + 'A') + "最短路径为" + dis[k][i] + ")");}System.out.println();System.out.println();}}// 弗洛伊德算法public void floyd(){int len = 0;// 从i节点经k节点到j节点// 对中间顶点进行遍历for (int k = 0; k < dis.length; k++) {// 遍历可能的出发点for (int i = 0; i < dis.length; i++) {// 遍历可能的终点for (int j = 0; j < dis.length; j++) {len = dis[i][k] + dis[k][j];if (len < dis[i][j]){dis[i][j] = len; // 更新距离pre[i][j] = k; // 更新前驱节点
// pre[i][j] = pre[k][j];
// pre[i][j] = vertex[k];}}}}}
}
马踏棋盘算法
马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。
package horse;import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;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;int column = 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();}}// 骑士周游问题算法public static void traversalChessboard(int[][] chessboard, int row, int column, int step){// 设置相应位置的步数chessboard[row][column] = step;visited[row][column] = true;// 获取能走的点ArrayList<Point> ps = next(new Point(row, column));// 排序的规则: 对ps的所有的Point对象的下一步能走的位置的数目, 进行非递减排序sort(ps);while (!ps.isEmpty()){Point p = ps.remove(0); // 取出每一个位置的点// 此点未访问过if (!visited[p.x][p.y]){traversalChessboard(chessboard, p.x, p.y, step + 1);}}if (step >= X * Y){finished = true;}else if (!finished){chessboard[row][column] = 0;visited[row][column] = false;}}// 根据当前位置, 计算还能走的位置public static ArrayList<Point> next(Point curPoint){// 创建一个点集合ArrayList<Point> ps = new ArrayList<>();Point p1 = new Point();if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0){ps.add(new Point(p1));}if((p1.x = curPoint.x - 1) >=0 && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1));}if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1));}if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1));}if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {ps.add(new Point(p1));}if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1));}if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1));}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>() {public int compare(Point p1, Point p2) {// 获取到p1的下一步的所有位置个数int count1 = next(p1).size();// 获取到p2的下一步的所有位置个数int count2 = next(p2).size();if (count1 < count2){return -1;}else if (count2 < count1){return 1;}else {return 0;}}});}
}