一、二分查找非遞歸算法

1.介紹

（1） 二分查找法只適用于從有序的數列中進行查找，將數列排序后再進行查找。
（2） 二分查找法的運行時間為對數時間O(log以2為底n的對數)。

2.代碼

/*** 常用十種算法（一）——二分查找非遞歸*/ public class BinarySearchNoRecur {public static void main(String[] args) {int [] arr = {1,3,8,10,11,67,100};int index = binarySearch(arr,100);System.out.println(index);}/*** 二分查找非遞歸實現* @param arr 要查找的數組* @param target 要查找的數* @return 要查找的數的下標*/public static int binarySearch(int[] arr,int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = (left + right)/2;if (arr[mid] > target) {right = mid - 1;} else if (arr[mid] < target) {left = mid + 1;} else if (arr[mid] == target){return mid;}}return -1;} }

---

二、分治算法

1.介紹

（1） 字面上解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題。再把子問題分成更小的子問題，直到最后子問題可以簡單的直接求解，原問題的解即子問題解的合并。
（2） 分治算法的應用有：二分搜索，大整數乘法，棋盤覆蓋，合并排序，快速排序，線性時間選擇，最接近點對問題，循壞賽日程表，漢諾塔等。
（3） 遞歸是一種方法，而分治是一種算法。分治只是滿足了可以使用遞歸的條件，但是也可以使用其他方法來編寫。

2.漢諾塔

漢諾塔（Tower of Hanoi），又稱河內塔，是一個源于印度古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

3.漢諾塔代碼

public class Hanoitower {public static void main(String[] args) {hanoiTower(5,'A','B','C');}/*** 漢諾塔移動方法，使用分治算法,將盤子從A移到C* @param num 要移動上面的盤子總數* @param a A塔* @param b B塔* @param c C塔*/public static void hanoiTower(int num, char a,char b,char c) {if (num == 1) {System.out.println("第1個盤子從 " + a + "->" + c);} else {// 將n盤子上面n-1個盤子移動到B上hanoiTower(num - 1,a, c, b);// 把最下面的盤從A->CSystem.out.println("第" + num + "個盤子從 " + a + "->" + c);// 把B塔所有盤子移動到C塔上hanoiTower(num - 1,b, a, c);}}}

---

三、動態規劃（Dynamic Programming，DP）

1.介紹

通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。動態規劃常常適用于有重疊子問題和最優子結構性質的問題，動態規劃通過迭代法自底向上求。
例如：在求解斐波那契數列過程中 ，求解fibonacci(5)求解fibonacci(5)時,得求解fibonacci(4)和fibonacci(3).其中,求解fibonacci(4)時,需要求解fibonacci(3).
在分治法中,求解完fibonacci(4)后還得重新求解fibonacci(3),即使求解fibonacci(4)子問題的時候已經求解過,也就是說,求解了二次子問題fibonacci(3).

2.01背包問題

問題描述
① 要求達到的目的為裝入的背包的總價值最大，并且重量不超出。
② 要求裝入的物品不能重復。
思路
每次遍歷到的第i個物品，根據w[i]和v[i]來確定是否需要將物品放入到背包中。即對于給定的n個物品，設w[i]為重量，v[i]為價值。v[i][j]表示在前i個物品中能裝入容量為j的背包中的最大價值。則有以下結論：
（1） v[i][0] = v[0j] = 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]]}；

3.01背包問題代碼

/*** 常用十種算法（三）——動態規劃解決01背包*/ public class KnapsackProblem {public static void main(String[] args) {// 物品重量int[] w = {1,4,3};// 物品價值int[] val = {1500,3000,2000};// 背包容量int m = 4;// 物品個數int n = val.length;// v[i][j]表示前i個物品中能裝入容量為j的背包的最大價值int[][] v = new int[n+1][m+1];// path為了記錄商品放入的情況int[][] path = new int[n+1][m+1];// 初始化第一行和第一列for (int i = 0;i < n+1;i++) {v[i][0] = 0;}for(int i = 0;i < m+1;i++) {v[0][i] = 0;}for (int i = 1;i < v.length;i++) { // 不處理第一行for (int j = 1;j < v[0].length;j++) { // 不處理第一列if (w[i-1] > j) {v[i][j] = v[i-1][j];} else {if (v[i-1][j-w[i-1]] + val[i-1] > v[i-1][j]) {v[i][j] = v[i-1][j-w[i-1]] + val[i-1];path[i][j] = 1;} else {v[i][j] = v[i-1][j];}}}}// 打印v[i][j]for (int i =0; i < v.length;i++) {for (int j = 0; j < v[i].length;j++) {System.out.print(v[i][j] + " ");}System.out.println();}// 打印path[i][j]for (int i =0; i < path.length;i++) {for (int j = 0; j < path[i].length;j++) {System.out.print(path[i][j] + " ");}System.out.println();}// 輸出最后放入的是那些商品int i = path.length -1;int j = path[0].length-1;while (i > 0 && j > 0) {if (path[i][j] == 1) {System.out.println("放入了第" + i + "個物品");j = j - w[i -1];}i --;}} }

---

四、KMP算法

1.介紹

（1） KMP是一個解決模式串在文本串是否出現過，如果出現過，最早出現的位置的經典算法。
（2） Knuth-Morris-Pratt 字符串查找算法，簡稱KMP算法，常用于在一個文本字符串S內查找一個模式串P的出現位置，這個算法由3個人于1977年聯合發表，故取這3人的姓氏命名此算法。
（3） KMP算法通過一個next數組，保存模式串中前后最長公共子序列的長度，每次回溯時，通過next數組找到，前面匹配過的位置。
（4） 參考資料： https://www.cnblogs.com/zzuuoo666/p/9028287.html

2.應用場景——字符串匹配問題

有一個字符串 str1和一個子串str2，要判斷str1是否含有str2，如果存在，就返回第一次出現的位置，如果沒有，則返回-1。

3.字符串匹配——暴力匹配法

public static void main(String[] args) {String str1 = "abcdavabcsdasdas";String str2 = "abcm";System.out.println(violenceMatch(str1,str2));}public static int violenceMatch(String str1,String str2) {char[] s1 = str1.toCharArray();char[] s2 = str2.toCharArray();int str1Length = s1.length;int str2Length = s2.length;int i=0, j= 0;while(i < str1Length && j < str2Length) {if (s1[i] == s2[j]) {i++;j++;}else {i = i - j + 1;j = 0;}}if (j == str2Length) {return i - j;} else {return -1;}}

4.字符串匹配——KMP算法

// 字串的部分匹配表,通過比較前綴和后綴相等數public static int[] kmpNext(String dest) {int[] next = new int[dest.length()];next[0] = 0;// i是后綴，j是前綴for (int i = 1,j=0; i < dest.length();i++) {while (j > 0 && dest.charAt(i) != dest.charAt(j)) {j = next[j-1];}if (dest.charAt(i) == dest.charAt(j)) {j++;}next[i] = j;}return next;}/*** 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++) {while (j > 0 && str1.charAt(i) != str2.charAt(j)) {j = next[j - 1];}if (str1.charAt(i) == str2.charAt(j)) {j++;}if (j == str2.length()) {return i - j + 1;}}return -1;}

---

五、貪心算法

1.介紹

（1） 貪心算法是指在對問題進行求解時，在每一步選擇中都采取最好或最優的選擇，從而希望能導致結果是最好或者最優的算法。
（2） 貪婪算法所得到的結果不一定是最優的結果（有時候會是最優解），但是都是相對近似最優解的結果。

2.應用場景——集合覆蓋問題

假設存在下面需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區。如何選擇最少的廣播臺，讓所有的地區都可以接收到信號。

3.集合覆蓋問題思路

（1）遍歷所有的廣播電臺，找到一個最多未覆蓋的電臺（此電臺可能包含一些已覆蓋的地區）
（2）將這個電臺加入到一個集合中，把該電臺覆蓋的地區在下次比較時去掉
（3）重復1，2兩步直到覆蓋了全部地區

3.貪心算法解決集合覆蓋問題代碼

/*** 常用十種算法（五）——K貪婪算法解決集合覆蓋問題*/ public class GreedyAlgorithm {public static void main(String[] args) {// 創建電臺，放入Map中HashMap<String, HashSet<String>> broadcasts = new HashMap<>();HashSet<String> hashSet1 = new HashSet<>();hashSet1.add("北京");hashSet1.add("上海");hashSet1.add("天津");HashSet<String> hashSet2 = new HashSet<>();hashSet2.add("廣州");hashSet2.add("北京");hashSet2.add("深圳");HashSet<String> hashSet3 = new HashSet<>();hashSet3.add("成都");hashSet3.add("上海");hashSet3.add("杭州");HashSet<String> hashSet4 = new HashSet<>();hashSet4.add("上海");hashSet4.add("天津");HashSet<String> hashSet5 = new HashSet<>();hashSet5.add("杭州");hashSet5.add("大連");broadcasts.put("k1",hashSet1);broadcasts.put("k2",hashSet2);broadcasts.put("k3",hashSet3);broadcasts.put("k4",hashSet4);broadcasts.put("k5",hashSet5);// 存放未被覆蓋的區域，會慢慢減少HashSet<String> allAreas = new HashSet<>();allAreas.addAll(hashSet1);allAreas.addAll(hashSet2);allAreas.addAll(hashSet3);allAreas.addAll(hashSet4);allAreas.addAll(hashSet5);// 存放選擇的電臺集合ArrayList<String> selects = new ArrayList<>();// 遍歷過程中，電臺覆蓋的地區和allAreas的交集HashSet<String> tempSet = new HashSet<>();String maxKey = null;int maxSize = 0;while (allAreas.size() != 0) {maxKey = null;maxSize = 0;for (String key : broadcasts.keySet()) {tempSet.clear();HashSet<String> areas = broadcasts.get(key);tempSet.addAll(areas);tempSet.retainAll(allAreas);if (tempSet.size() > 0 &&(maxKey == null || tempSet.size() > maxSize)) {maxKey = key;maxSize = tempSet.size();}}if (maxKey != null) {selects.add(maxKey);allAreas.removeAll(broadcasts.get(maxKey));}}System.out.println(selects);} }

4.貪心算法和動態規劃的區別

（1） 貪心算法自頂向下求解，動態規劃自底向上求解。
貪心自頂向上，每次向下遍歷最優子樹即可，這樣的話就不需要知道一個節點所有子樹的情況，于是構不成一棵完整的樹。
動態規劃自底向上，最后得到一棵完整的樹，根的值即為最優值。
2 貪心最優解一定包含上一步的最優解，動態規劃最優解不一定包含上一步的最優解；

貪心：每一步只考慮當前的最優解，而不考慮之前的局部最優解。下一步也只會包含上一步的最優解，而不考慮產生的子問題的最優解。
dp：原問題的結果不一定是上一步的最優解，所以要得到所有子問題的解。

3 貪心不能保證全局最優，動態規劃（本質是窮舉法）能保證全局最優；

4 貪心復雜度較低，動態規劃復雜度較高；

---

六、普里姆算法（Prim）

1. 應用場景 ——修路問題

有7個村莊（A,B,C,D,E,F,G）現在需要修路把7個村莊連通。各個村莊的距離用邊線表示權，如果修路保證各個村莊都能連通，并且總里程最短。

2. 最小生成樹（Minimum Spanning Tree）

（1） 給定一個帶權的無向連通圖，選取一顆生成樹，使樹上所有邊上權的總和為最小，這叫最小生成樹。
（2） N個頂點，一定有N-1條邊。
（3） 求最小生成樹的算法主要是普里姆算法和克魯斯卡爾算法

3. Prim算法思路

（1） 設G=(V,E)是連通網，T=(U,D)是最小生成樹，V,U是頂點集合，E,D是邊的集合。
（2） 若從頂點u開始構造最小生成樹，則從集合V中取出頂點u放入集合U中，標記頂點u的visited[u] = 1。
（3） 若集合U中頂點ui與集合V中的頂點vj存在邊，則尋找這些邊中權值最小的邊，但不能構成回路，將頂點vj加入集合U中，將邊（ui，vj）加入集合D中，標記visited[vj] = 1。
（4） 重復步驟（2），直到U與V相等，此時D中有n-1條邊。

4.Prim算法代碼

/*** 常用十種算法（六）——Prim算法*/ public class PrimAlgorithm {public static void main(String[] args) {char[] data = new char[]{'A','B','C','D','E','F','G'};int verxs = data.length;int [][]weight = new int[][] {{-1,5,7,-1,-1,-1,2},{5,-1,-1,9,-1,-1,3},{7,-1,-1,-1,8,-1,-1},{-1,9,-1,-1,-1,4,-1},{-1,-1,8,-1,-1,5,4},{-1,-1,-1,4,5,-1,6},{2,3,-1,-1,4,6,-1},};MGraph mGraph = new MGraph(verxs);MinTree minTree = new MinTree();minTree.createGraph(mGraph,verxs,data,weight);mGraph.showGraph();minTree.prim(mGraph,1);} }// 最小生成樹 class MinTree {// 創建圖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];}}}/*** 編寫prim算法，得到最小生成樹* @param graph 圖* @param v 表示從圖的第幾個頂點開始生成*/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 = Integer.MAX_VALUE;for (int k = 1; k < graph.verxs; k ++) { //已訪問節點的個數，每次循環完已訪問節點個數都會多一個for (int i = 0; i < graph.verxs; i++) {if (visited[i] == 1) { // 遍歷已訪問節點for (int j = 0;j < graph.verxs; j++) {// 找到該已訪問節點和未訪問節點最短的連通邊if (visited[j] == 0 && graph.weight[i][j] != -1 && graph.weight[i][j] < minWeight) {minWeight = graph.weight[i][j];h1 = i;h2 = j;}}}}System.out.println("邊<" + graph.data[h1] + "," + graph.data[h2] + ">權值:" + minWeight);// 找到一條邊最小的，將當前節點標記為已經訪問visited[h2] = 1;minWeight = Integer.MAX_VALUE;}} }// 帶權無向圖 class MGraph {int verxs; // 表示圖的節點個數char[] data; // 存放節點數據int[][] weight; // 存放邊，就是鄰接矩陣public MGraph(int verxs) {this.verxs = verxs;data = new char[verxs];weight = new int[verxs][verxs];}public void showGraph() {for (int[] link : weight) {System.out.println(Arrays.toString(link));}} }

---

七、克魯斯卡爾算法（Kruskai）

1. 應用場景 ——公交站問題

某城市新增7個站點（A,B,C,D,E,F,G）,需要修路把7個站點連通。各個站點的距離用邊線表示權，問：如何修路保證各個站點都能連通，并且總的修建公路總里程最短？

2. 克魯斯卡爾算法解決公交站問題基本思路

按照權值從小到大的順序來選擇n-1條邊。并保證這n-1條邊不構成回路。
重點需要解決以下兩個問題：
問題一 對圖的所有邊按照權值大小進行排序
問題二 將邊添加到最小生成樹中時，怎么樣判斷是否形成回路

3. 克魯斯卡爾算法解決公交站問題代碼

/*** 常用十種算法（七）——Kruskal算法*/ public class KruskalAlgorithm {private int edgeNum;private char[] vertexs;private int[][] matrix;private static final int INF = Integer.MAX_VALUE;public static void main(String[] args) {char[] vertexs = new char[]{'A','B','C','D','E','F','G'};int [][]weight = new int[][] {{0,12,INF,INF,INF,16,14},{12,0,10,INF,INF,7,INF},{INF,10,0,3,5,6,INF},{INF,INF,3,0,4,INF,INF},{INF,INF,5,4,0,2,8},{16,7,6,INF,2,0,9},{14,INF,INF,INF,8,9,0},};KruskalAlgorithm kruskalAlgorithm = new KruskalAlgorithm(vertexs, weight);kruskalAlgorithm.showGraph();kruskalAlgorithm.kruskal();}public KruskalAlgorithm(char[] vertexs,int [][] matrix) {int vlen = vertexs.length;// 初始化頂點this.vertexs = new char[vlen];this.matrix = new int[vlen][vlen];for (int i = 0; i < vlen; i++) {this.vertexs[i] = vertexs[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[vertexs.length]; // 各頂點的終點EData[] rets = new EData[vertexs.length-1]; // 結果數組，保存最后的最小生成樹EData[] edges = getEdges(); // 獲取所有的邊sortEdges(edges); // 按照權值對邊進行排序for (int i = 0; i < edgeNum; i++) {// 獲取一條邊的兩個頂點int p1 = getPosition(edges[i].start);int p2 = getPosition(edges[i].end);int m = getEnd(ends,p1);int n = getEnd(ends, p2);// 沒構成回路if (m != n) {ends[m] = n;rets[index++] = edges[i];}}System.out.println("最小生成樹為=" + Arrays.toString(rets));}/*** 打印鄰接矩陣*/public void showGraph() {for (int[] link : matrix) {System.out.println(Arrays.toString(link));}}/*** 對邊進行排序,冒泡排序*/public 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*/public int getPosition(char ch) {for (int i = 0; i < vertexs.length; i++) {if (vertexs[i] == ch) {return i;}}return -1;}/*** 通過鄰階矩陣，獲取圖中邊，放到EData[]數組中*/private EData[] getEdges() {int index = 0;EData[] eData = 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) {eData[index++] = new EData(vertexs[i],vertexs[j],matrix[i][j]);}}}return eData;}/*** 獲取下標為i的頂點的終點坐標* @param ends 記錄各個頂點對應的終點是那個* @param i* @return 下標為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;}@Overridepublic String toString() {return "EData{" +"start=" + start +", end=" + end +", weight=" + weight +'}';} }

---

八、迪杰斯特拉算法（Dijkstra）

1. 應用場景 ——最短路徑問題

戰爭時間，有7個村莊，現在有6個郵差，從G點出發，需要分別把郵件送到A,B,C,D,E,F六個村莊。各個村莊的距離用邊線表示，問：如何計算出G村莊到其他各個村莊的最短距離？如何從其他點出發到各個點的最短距離又是多少？

2. 算法思路分析

Dijkstra算法是典型最短路徑算法，用于計算一個結點到其他結點的最短路徑。它的主要特點是以起始點為中心向外層層擴展（廣度優先搜索思想，BFS用來求無權值的圖，Dijkstra用來求有權值的圖的最短路徑），直到擴展到終點為止。
（1） 設置出發頂點為v，頂點集合V{v1,v2,vi…}，v到V中各頂點的距離構成記錄集合Dis{d1,d2,di…}（0表示到自己）。
（2） 從V中選擇一個未被訪問且Dis最小的頂點vi，標記該結點已被訪問。
（3） 更新Dis集合，更新規則：比較v到V集合中頂點的距離值，與v通過vi到V集合中頂點的距離值，保留值較小的一個（同時也應該更新頂點的前驅結點為vi,表示是通過vi到達的）。
（4） 重復執行兩步驟，直到所有結點都被訪問過。

3.代碼

/*** 常用十種算法（八）——迪杰斯特拉算法*/ public class DijkstraAlgorithm {public static void main(String[] args) {final int INF = 65535;char[] vertexs = new char[]{'A','B','C','D','E','F','G'};int [][] matrix = new int[][] {{INF,5,7,INF,INF,INF,2},{5,INF,INF,9,INF,INF,3},{7,INF,INF,INF,8,INF,INF},{INF,9,INF,INF,INF,4,INF},{INF,INF,8,INF,INF,5,4},{INF,INF,INF,4,5,INF,6},{2,3,INF,INF,4,6,INF},};Graph graph = new Graph(vertexs, matrix);graph.showGraph();graph.dsj(6);graph.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 showGraph() {for (int[] link : matrix) {System.out.println(Arrays.toString(link));}}public void dsj(int index) {vv = new VisitedVertex(vertex.length, index);update(index);for (int j = 1;j < vertex.length;j++) {index = vv.updateArr();update(index);}}// 更新index下標頂點周圍頂點的距離和周圍頂點的前驅頂點private void update(int index) {int len = 0;for (int j = 0;j < matrix[index].length;j++) {//出發頂點到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);vv.updateDis(j,len);}}}public void showDijkstra() {vv.show();} } // 已訪問頂點集合 class VisitedVertex {// 記錄各個頂點是否訪問過，1表示訪問過，0表示未訪問，會動態更新public int[] already_arr;// 每個下標對應的值為前一個頂點的下標，會動態更新public int[] pre_visited;// 出發頂點到其他各頂點的距離public int[] dis;/*** 構造器* @param lenght 頂點的個數* @param index 出發頂點的下標*/public VisitedVertex(int lenght,int index) {this.already_arr = new int[lenght];this.pre_visited = new int[lenght];this.dis = new int[lenght];// 初始化dis，出了到自己的距離為0，到其他各頂點的距離為整數最大值Arrays.fill(dis,Integer.MAX_VALUE);this.already_arr[index] = 1; // 設置出發結點被訪問過this.dis[index] = 0;}// 判斷index結點是否被訪問過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];}// 繼續選擇并返回新的訪問頂點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;}}already_arr[index] = 1;return index;}public void show() {System.out.println("=========================================");for (int i : already_arr){System.out.print(i + " ");}System.out.println();for (int i : pre_visited) {System.out.print(i + " ");}System.out.println();for (int i : dis) {System.out.print(i + " ");}} }

---

九、弗洛伊德算法（Floyd）

1.介紹

floyd算法也是用于一種用于尋找給定的加權圖中頂點間最短路徑的算法。該算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特.弗洛伊德命名。
dijkstra算法通過選定的被訪問頂點，求出從出發頂點到其他頂點的最短路徑。floyd算法中每個頂點都是出發訪問點，求出從每一個頂點到其他頂點的最短路徑。

2. 算法思路分析

（1） 設置頂點vi到頂點vk的最短路徑已知為Lik，頂點vk到vj的最短路徑已知為Lkj，頂點vi到vj的路徑為Lij，則vi到vj的最短路徑為：min（（Lik+Lkj），Lij）。vk的取值為圖中所有頂點，則可獲得vi到vj的最短路徑。
（2） 至于vi到vk的最短路徑Ljk或者vk到vj的最短路徑Lkj，是以同樣的方式獲得。



要想更新如上兩張表，需要借助如下圖3個列表：

最外層循環是中間頂點，第二層循環是出發頂點，最內層循環時終點。每次循環時通過步驟（1）來比較更新兩個表。

3.代碼

/*** 常用十種算法（九）——弗洛伊德算法*/ public class FloydAlgorithm {public static void main(String[] args) {final int INF = 65535;char[] vertex = {'A','B','C','D','E','F','G'};int [][] matrix = new int[][] {{0,5,7,INF,INF,INF,2},{5,0,INF,9,INF,INF,3},{7,INF,0,INF,8,INF,INF},{INF,9,INF,0,INF,4,INF},{INF,INF,8,INF,0,5,4},{INF,INF,INF,4,5,0,6},{2,3,INF,INF,4,6,0},};FloydGraph floydGraph = new FloydGraph(vertex.length, matrix, vertex);floydGraph.floyd();floydGraph.show();} }class FloydGraph {private char[] vertex; // 存放頂點的數組private int[][] dis; // 保存從各個頂點出發到其他頂點的距離，最后結果也保存在該數組private int[][] pre; //保存到達目標頂點的前驅頂點/**** @param length 結點個數* @param matrix 鄰接矩陣* @param vertex 結點數組*/public FloydGraph(int length,int [][] matrix,char[] vertex) {this.vertex = vertex;this.dis = matrix;this.pre = new int[length][length];// 初始化前驅頂點數組for (int i = 0; i < length; i++) {Arrays.fill(pre[i],i);}}// 佛洛伊德算法public void floyd() {int len = 0;// 中間頂點遍歷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]) { // 如果len小于出發頂點到終點的距離dis[i][j] = len;pre[i][j] = pre[k][j];}}}}}// 顯示pre和dispublic void show() {for (int k = 0; k < dis.length;k++) {for (int i = 0; i < dis.length;i++) {System.out.print(vertex[pre[k][i]] + " ");}System.out.println();for (int i = 0; i < dis.length;i++) {System.out.print("(" + vertex[k] + "到" + vertex[i] + "最短距離：" + dis[k][i] + ") ");}System.out.println();System.out.println("-----------------------------------------");}} }

---

十、騎士周游問題

1.介紹

（1） 馬踏棋盤算法也稱為騎士周游問題。
（2） 將馬隨機放在國際象棋8*8期盼的某個方格中，馬按照象棋規則進行移動。要求每個方格只能進入一次，走遍棋盤上全部64個方格。

2. 算法思路分析

（1）創建棋盤chessBoard，是一個二維數組
（2）將當前位置設置為已經訪問，然后根據當前位置，計算馬還能走那些位置，并放入到一個集合中（ArrayList），最多有8個位置。
（3）遍歷ArrayList中存放的所有位置，看那個可以走通，如果走通，就繼續走，走不通就回溯。
（4）判斷馬是否完成了任務，使用step和應走步數比較。如果沒達到，則沒有完成任務，將整個棋盤置0。
注意：馬不同的走法，會得到不同的結果，效率也會有影響。
貪心算法優化： 對下一步還能走的位置的集合中每個點的下一步集合數目，進行非遞減排序。

3.代碼

/*** 常用十種算法（十）——騎士周游算法/馬踏棋盤算法*/ public class HorseChessboard {private static int X; // 棋盤的列private static int Y; // 棋盤的行private static boolean visited[]; // 標記棋盤各個位置是否被訪問過private static boolean finished; // 標記棋盤的所有位置都被訪問過public static void main(String[] args) {X = 8;Y = 8;int row = 1; // 初始行int column = 1; // 列int[][] chessboard = new int[Y][X];visited = new boolean[X*Y];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();}}/*** 騎士周游問題算法* @param chessboard 棋盤* @param row 馬的當前位置的行* @param column 馬的當前位置的列* @param step 是第幾步，初始位置就是第一步*/public static void traversalChessboard(int[][] chessboard,int row,int column,int step) {chessboard[row][column] = step;visited[row*X + column] = true;ArrayList<Point> ps = next(new Point(column, row)); // 獲取當前位置可以走的下一個位置的集合sort(ps); // 貪心算法優化while (!ps.isEmpty()) {Point p = ps.remove(0);// 判斷該點是否已經被訪問過if (!visited[p.y*X + p.x]) {traversalChessboard(chessboard,p.y,p.x,step + 1);}}if (step < X*Y && !finished) {chessboard[row][column] = 0;visited[row*X+column] = false;} else {finished = true;}}public static void sort(ArrayList<Point> ps) {ps.sort(new Comparator<Point>() {@Overridepublic int compare(Point o1, Point o2) {int count1 = next(o1).size();int count2 = next(o2).size();if (count1 < count2) {return -1;} else if (count1 == count2) {return 0;} else {return 1;}}});}/*** 根據當前位置（Point對象），計算馬還能走那些位置，并放入到一個集合中* @param curPoint* @return*/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) { // 5ps.add(new Point(p1));}if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y -2) >= 0) { // 6ps.add(new Point(p1));}if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y -2) >= 0) { // 7ps.add(new Point(p1));}if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y -1) >= 0) { // 0ps.add(new Point(p1));}if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y +1) < Y) { // 1ps.add(new Point(p1));}if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y +2) < Y) { // 2ps.add(new Point(p1));}if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) { // 3ps.add(new Point(p1));}if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y +1) < Y) { // 4ps.add(new Point(p1));}return ps;}}

總結

以上是生活随笔為你收集整理的数据结构和算法基础（6）——常用十种算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。