DSA_常用10种算法（java数据结构与算法）
生活随笔
收集整理的這篇文章主要介紹了
DSA_常用10种算法（java数据结构与算法）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
常用10種算法
- 二分查找算法(非遞歸)
- 二分查找算法(非遞歸)介紹
- 二分查找算法(非遞歸)代碼實現
- 分治算法
- 分治算法介紹
- 分治算法的基本步驟
- 分治算法最佳實踐-漢諾塔
- 漢諾塔的傳說
- 漢諾塔游戲的演示和思路分析:
- 漢諾塔游戲的代碼實現:
- 動態規劃算法
- 動態規劃算法介紹
- 背包問題
- 背包問題
- 思路分析
- 圖解
- 代碼實現
- KMP 算法
- 應用場景-字符串匹配問題
- 暴力匹配算法
- KMP 算法介紹
- KMP 算法最佳應用-字符串匹配問題
- 字符串匹配問題：：
- 思路分析圖解
- 代碼實現
- 貪心算法
- 貪心算法介紹
- 貪心算法注意事項和細節
- 貪心算法最佳應用-集合覆蓋
- 問題描述
- 思路分析:
- 代碼實現
- 普里姆算法
- 普里姆算法介紹
- 普里姆算法最佳實踐(修路問題)
- 最小生成樹
- 代碼實現
- 克魯斯卡爾算法
- 克魯斯卡爾算法介紹
- 應用場景-公交站問題
- 克魯斯卡爾算法圖解說明
- 克魯斯卡爾算法分析
- 如何判斷是否構成回路
- 代碼實現
- 迪杰斯特拉算法
- 迪杰斯特拉(Dijkstra)算法介紹
- 迪杰斯特拉(Dijkstra)算法過程
- 迪杰斯特拉(Dijkstra)算法最佳應用-最短路徑
- 問題描述
- 思路圖解
- 代碼實現
- 弗洛伊德算法
- 弗洛伊德(Floyd)算法介紹
- 弗洛伊德(Floyd)算法圖解分析
- 弗洛伊德(Floyd)算法最佳應用-最短路徑
- 代碼實現
- 運行結果
- 馬踏棋盤算法
- 馬踏棋盤算法介紹和游戲演示
- 思路圖解
- 代碼實現
二分查找算法(非遞歸)
二分查找算法(非遞歸)介紹
二分查找算法(非遞歸)代碼實現
數組 {1,3, 8, 10, 11, 67, 100}, 編程實現二分查找， 要求使用非遞歸的方式完成.
package cn.chasing.Algorithm.binarySearch;/*** @author 柴柴快樂每一天* @create 2021-08-23 10:50 上午* <p>* 『Stay hungry, stay foolish. 』*/ 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=" + index);}/*** 二分查找的非遞歸實現* @param arr 待查找的數組，arr是升序排列* @param target 需要查找的數* @return 返回對應下標，-1表示沒有找到*/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;}if (target < arr[mid]) {right = mid-1;} else {left = mid + 1;}}return -1;} }分治算法
分治算法介紹
分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)……
分治算法可以求解的一些經典問題
-
二分搜索
-
大整數乘法
-
棋盤覆蓋
-
合并排序
-
快速排序
-
線性時間選擇
-
最接近點對問題
-
循環賽日程表
-
漢諾塔
分治算法的基本步驟
分治法在每一層遞歸上都有三個步驟：
分治(Divide-and-Conquer§)算法設計模式如下：
分治算法最佳實踐-漢諾塔
漢諾塔的傳說
漢諾塔：漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著 64 片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
假如每秒鐘一次，共需多長時間呢？移完這些金片需要 5845.54 億年以上，太陽系的預期壽命據說也就是數百億年。真的過了 5845.54 億年，地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。
漢諾塔游戲的演示和思路分析:
如果是有一個盤， A->C
如果我們有 n >= 2 情況，我們總是可以看做是兩個盤
1.最下邊的盤 2. 上面的盤
先把 最上面的盤 A->B
把最下邊的盤 A->C
把 B 塔的所有盤 從 B->C
漢諾塔游戲的代碼實現:
package cn.chasing.Algorithm.divideAndConquer;/*** @author 柴柴快樂每一天* @create 2021-08-23 3:45 下午* <p>* 『Stay hungry, stay foolish. 』*/ public class HanoiTower {public static void main(String[] args) {hanoiTower(3, 'A', 'B', 'C');}/*** 漢諾塔移動的方法，將起始塔a的所有圓盤借助輔助塔b移動到目標塔c* @param num 漢諾塔的層數* @param a 起始塔* @param b 輔助塔* @param c 目標塔*/public static void hanoiTower(int num, char a, char b, char c) {// 如果只有一個圓盤if (num == 1) {System.out.println("第1個圓盤從 " + a + "->" + c);} else {// 當 n >= 2 時，始終可以看做兩個圓盤：1. 最底部的一個盤；2. 上面的所有盤// 1. 先把最上面所有的盤移動從a->b,移動過程中會用到chanoiTower(num-1, a, c, b);// 2. 把最下面的盤移動到a->cSystem.out.println("第" + num + "個盤從 " + a + "->" + c);// 3. 把b塔上的所有盤從b->c，移動過程中會用到ahanoiTower(num-1, b, a, c);}} }動態規劃算法
動態規劃算法介紹
背包問題
背包問題
有一個背包，容量為 4 磅 ， 現有如下物品
思路分析
vTable[i] [0] = vTable[0] [j] = 0;
表示填入表第一行和第一列是 0
當 weight[i] > j 時：
vTable[i] [j] = vTable[i-1] [j]
當準備加入新增的商品的容量大于當前背包的容量時，就直接使用上一個單元格的裝入策略
當 w[i] <= j時：
vTable[i] [j] = max{ vTable[i-1] [j], value[i] + vTable[i-1] [j-weight[i]] }
當 準備加入的新增的商品的容量小于等于當前背包的容量,
裝入的方式:
j 為當前動態容量，i為商品下標
vTable [i-1] [j]： 就是上一個單元格的裝入的最大值
value[i] : 表示當前商品的價值
vTable [i-1] [j-weight[i]] ： 裝入 i-1 商品，到剩余空間 j-weight[i]的最大值
當w[i] <= j時： vTable[i] [j] = max{vTable[i-1] [j], value[i] + vTable[i-1] [j-weight[i]] }
圖解
代碼實現
package cn.chasing.Algorithm.dynamic;/*** @author 柴柴快樂每一天* @create 2021-08-23 5:44 下午* <p>* 『Stay hungry, stay foolish. 』*/ public class Knapsack {public static void main(String[] args) {// 物體的重量int[] weight = {0, 1, 4, 3};// 物體的價值int[] value = {0, 1500, 3000, 2000};// 背包的容量int capacity = 4;// 物體的個數int n = value.length;// 創建二維數組狀態表，vTable[i][j] 表示從前i個物品中，裝入到容量為j的背包中的最大價值// n個物品，第一個物品0磅，capacity+1是因為要保證表頭為0 1 2 3 4，不加1就沒有4int[][] vTable = new int[n][capacity + 1];// 存儲最優解的路徑int[][] path = new int[n][capacity+1];// 初始化第一行和第一列，使其都為0，但但是數組默認值為0，所以可以不處理// 進行動態規劃,從非0行列開始處理for (int i = 1; i < vTable.length; i++) {for (int j = 1; j < vTable[0].length; j++) {if (weight[i] > j) {vTable[i][j] = vTable[i - 1][j];} else {vTable[i][j] = Math.max(vTable[i - 1][j], value[i] + vTable[i - 1][j - weight[i]]);path[i][j] = 1;}}}// 輸出狀態表for (int i = 0; i < vTable.length; i++) {for (int j = 0; j < vTable[i].length; j++) {System.out.print(vTable[i][j] + " ");}System.out.println();}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.printf("第%d個商品放入到背包\n", i);j -= weight[i];}i--;}} }KMP 算法
應用場景-字符串匹配問題
字符串匹配問題：：
暴力匹配算法
如果用暴力匹配的思路，并假設現在 str1 匹配到 i 位置，子串 str2 匹配到 j 位置，則有:
KMP 算法介紹
KMP 算法最佳應用-字符串匹配問題
字符串匹配問題：：
有一個字符串 str1= “BBC ABCDAB ABCDABCDABDE”，和一個子串 str2=“ABCDABD”
現在要判斷 str1 是否含有 str2, 如果存在，就返回第一次出現的位置, 如果沒有，則返回-1
要求：使用 KMP 算法完成判斷，不能使用簡單的暴力匹配算法.
思路分析圖解
舉例來說，有一個字符串 Str1 = “BBC ABCDAB ABCDABCDABDE”，判斷，里面是否包含另一個字符串 Str2 = “ABCDABD”？
已知空格與 D 不匹配時，前面六個字符”ABCDAB”是匹配的。查表可知，最后一個匹配字符 B 對應的”部分匹配值”為 2，因此按照下面的公式算出向后移動的位數：
移動位數 = 已匹配的字符數 - 對應的部分匹配值
因為 6 - 2 等于 4，所以將搜索詞向后移動 4 位。
因為空格與Ｃ不匹配，搜索詞還要繼續往后移。這時，已匹配的字符數為 2（”AB”），對應的”部分匹配值” 為 0。所以，移動位數 = 2 - 0，結果為 2，于是將搜索詞向后移 2 位。
“部分匹配值”就是”前綴”和”后綴”的最長的共有元素的長度。以”ABCDABD”為例，
- ”A”的前綴和后綴都為空集，共有元素的長度為 0；
- ”AB”的前綴為[A]，后綴為[B]，共有元素的長度為 0；
- ”ABC”的前綴為[A, AB]，后綴為[BC, C]，共有元素的長度 0；
- ”ABCD”的前綴為[A, AB, ABC]，后綴為[BCD, CD, D]，共有元素的長度為 0；
- ”ABCDA”的前綴為[A, AB, ABC, ABCD]，后綴為[BCDA, CDA, DA, A]，共有元素為”A”，長度為 1；
- ”ABCDAB”的前綴為[A, AB, ABC, ABCD, ABCDA]，后綴為[BCDAB, CDAB, DAB, AB, B]，共有元素為”AB”，長度為 2；
- ”ABCDABD”的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為 0。
到此 KMP 算法思想分析完畢!
代碼實現
package cn.chasing.kmp;import java.util.Arrays;/*** @author 柴柴快樂每一天* @create 2021-08-23 11:02 下午* <p>* 『Stay hungry, stay foolish. 』*/ public class KMP {public static void main(String[] args) {String str1 = "BBC ABCDAB ABCDABCDABDE";String str2 = "ABCDABD"; // String str2 = "AABAAA";int[] next = kmpNext(str2);System.out.println("next = " + Arrays.toString(next));int index = kmpSearch(str1, str2, next);System.out.println(index);}public static int kmpSearch(String str, String dest, int[] next) {for (int i = 0, j = 0; i < str.length(); i++) {// 需要處理str.charAt(i) != dest.charAt(j),去調整j的位置while (j > 0 && str.charAt(i) != dest.charAt(j)) {j = next[j-1];}if (str.charAt(i) == dest.charAt(j)) {j++;}if (j == dest.length()) {return i-j+1;}}return -1;}/*** 獲取到一個字符串的部分匹配表* @param dest 目標字符串* @return 返回該字符串的部分匹配表*/public static int[] kmpNext(String dest) {// 創建一個next數組保存部分匹配值int[] next = new int[dest.length()];// 字符串長度為1，則部分匹配值的值為0next[0] = 0;// j一直在前綴活動，i在找對應的后綴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) 時才退出, j > 0防止next[j-1]越界while (j > 0 && dest.charAt(i) != dest.charAt(j)) {// j表示已經匹配上的位數。失配時，// 之前我們比較模式串和文本串時遇到沖突回退到next數組前一位代表的下標位置，現在我們也是匹配只不過匹配的時前綴(相當于模式串)和后綴(相當于文本串)j = next[j-1];}if (dest.charAt(i) == dest.charAt(j)) {j++;}next[i] = j;}return next;} }貪心算法
貪心算法介紹
貪心算法注意事項和細節
貪心算法最佳應用-集合覆蓋
問題描述
假設存在如下表的需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區。 如何選擇最少的廣播臺，讓所有的地區都可以接收到信號
思路分析:
如何找出覆蓋所有地區的廣播臺的集合呢，使用窮舉法實現,列出每個可能的廣播臺的集合，這被稱為冪集。假設總的有 n 個廣播臺，則廣播臺的組合總共有 2? -1 個,假設每秒可以計算 10 個子集， 如圖:
使用貪婪算法，效率高:
分析的圖解:
代碼實現
package cn.chasing.Algorithm.greedy;import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet;/*** @author 柴柴快樂每一天* @create 2021-08-25 10:45 上午* <p>* 『Stay hungry, stay foolish. 』*/ 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);//allAreas 存放所有的地區HashSet<String> allAreas = new HashSet<String>();allAreas.add("北京");allAreas.add("上海");allAreas.add("天津");allAreas.add("廣州");allAreas.add("深圳");allAreas.add("成都");allAreas.add("杭州");allAreas.add("大連");// 創建ArrayList，存放選擇的電臺集合ArrayList<String> selects = new ArrayList<>();// 定義一個臨時的集合，在遍歷過程中，存放該電臺覆蓋區域和當前allAreas剩余未覆蓋區域的交集HashSet<String> tempSet = new HashSet<>();// 定義maxKey，保存在遍歷過程中，能夠覆蓋最大未覆蓋區域的key// maxAreaSize是能夠覆蓋最大未覆蓋區域的tempSet的size// 當maxKey != null，加入到selectsString maxKey;Integer maxAreaSize = null;// 當allAreas 里還有元素，這說明還有未覆蓋到的區域while (allAreas.size() > 0) {// 每次遍歷比較前，需將上一次的maxKey清空maxKey = null;// 遍歷broadcasts，取出對應keyfor (String key : broadcasts.keySet()) {// 每一次for都要清空臨時settempSet.clear();// 獲取當前這個key可以覆蓋的地區HashSet<String> areas = broadcasts.get(key);tempSet.addAll(areas);// 求出tempSet和allAreas交集，結果會直接賦給tempSettempSet.retainAll(allAreas);// 第一次maxKey為null，通過判斷makKey == null 進入if賦初始maxKey；// 之后每一次for循環則比較當前key和maxKey對應覆蓋區域交集的大小，通過判斷tempSet.size() > maxAreas更新maxKeyif (tempSet.size() > 0 && (maxKey == null || tempSet.size() > maxAreaSize)) {maxKey = key;maxAreaSize = tempSet.size();}}// 一輪比較結束后，如果maxKey != null, 就把maxKey加入selectsif (maxKey != null) {selects.add(maxKey);// 將maxKey指向的廣播電臺覆蓋的區域，從allAreas中去掉allAreas.removeAll(broadcasts.get(maxKey));}}// K1, K2, K3, K5System.out.println("得到的選擇結果是：" + selects);} }普里姆算法
普里姆算法介紹
普利姆(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 條邊
提示: 單獨看步驟很難理解，我們通過代碼來講解，比較好理解.
圖解普利姆算法
普里姆算法最佳實踐(修路問題)
思路:
將 10 條邊，連接即可，但是總的里程數不是最小。正確的思路，就是盡可能的選擇少的路線，并且每條路線最小，保證總里程數最少。
最小生成樹
修路問題本質就是就是最小生成樹問題， 先介紹一下最小生成樹(Minimum Cost Spanning Tree)，簡稱 MST。
給定一個帶權的無向連通圖,如何選取一棵生成樹,使樹上所有邊上權的總和為最小,這叫最小生成樹
包含全部頂點
N-1 條邊都在圖中
舉例說明(如圖:)
求最小生成樹的算法主要是普里姆算法和克魯斯卡爾算法
代碼實現
package cn.chasing.Algorithm.prim;import java.util.Arrays;/*** @author 柴柴快樂每一天* @create 2021-08-25 4:07 下午* <p>* 『Stay hungry, stay foolish. 』*/ public class PrimAlgorithm {public static void main(String[] args) {//測試看看圖是否創建okchar[] data = new char[]{'A','B','C','D','E','F','G'};int verNum = 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(verNum, data, weight);// 創建一個MinTree對象MinTree minTree = new MinTree(graph);minTree.showGraphWeight();minTree.prim(1);} }/*** 創建最小生成樹*/ class MinTree {private MGraph mGraph;public MinTree(MGraph mGraph) {this.mGraph = mGraph;}/*** 顯示圖的鄰接矩陣*/public void showGraphWeight() {for (int[] link : this.mGraph.weight) {System.out.println(Arrays.toString(link));}}/*** 編寫prim算法，得到最小生成樹* @param v 表示從圖的第幾個頂點開始生成A->0 B->1*/public void prim(int v) {// 標記頂點是否被訪問過，默認值為0，表示未訪問過int[] visited = new int[this.mGraph.verNum];// 把當前節點標記已訪問visited[v] = 1;// h1, h2記錄聯通的兩點下標int h1 = -1, h2 = -1;int minWeight = 10000;// prim算法結束后，會產生的 邊 = 頂點-1for (int e = 0; e < this.mGraph.verNum - 1; e++) {// 確定當前生成的 子圖<X1, X2> 跟哪一個節點Y 距離最近// i 表示已經訪問過的節點，j表示未訪問的。實際不知道訪問沒有，直接都遍歷，拉進循環判斷for (int i = 0; i < this.mGraph.verNum; i++) {for (int j = 0; j < this.mGraph.verNum; j++) {if (visited[i] == 1 && visited[j] == 0 && mGraph.weight[i][j] < minWeight) {minWeight = mGraph.weight[i][j];h1 = i;h2 = j;}}}// 找到一條邊最小了System.out.println("邊<" + mGraph.data[h1] + ", " + mGraph.data[h2] + "> 權值：" + minWeight);// 將當前節點標記為已訪問visited[h2] = 1;minWeight = 10000;}} }class MGraph {/*** @param verNum 表示圖的節點個數* @param data 存放節點數據* @param weight 存放邊，即鄰接矩陣*/int verNum;char[] data;int[][] weight;public MGraph() {}/*** 初始化圖（村莊）* @param verNum 圖對應的頂點個數* @param data 圖各個頂點的值* @param weight 圖的鄰接矩陣*/public MGraph (int verNum, char[] data, int[][] weight) {this.verNum = verNum;this.data = new char[verNum];this.weight = new int[verNum][verNum];for (int i = 0; i < verNum; i++) {this.data[i] = data[i];for (int j = 0; j < verNum; j++) {this.weight[i][j] = weight[i][j];}}} }克魯斯卡爾算法
克魯斯卡爾算法介紹
應用場景-公交站問題
看一個應用場景和問題：
克魯斯卡爾算法圖解說明
以城市公交站問題來圖解說明 克魯斯卡爾算法的原理和步驟：
在含有 n 個頂點的連通圖中選擇 n-1 條邊，構成一棵極小連通子圖，并使該連通子圖中 n-1 條邊上權值之和達到最小，則稱其為連通網的最小生成樹。
例如，對于如上圖 G4 所示的連通網可以有多棵權值總和不相同的生成樹。
以上圖 G4 為例，來對克魯斯卡爾進行演示(假設，用數組 R 保存最小生成樹結果)。
將邊<E,F>加入 R 中。
邊<E,F>的權值最小，因此將它加入到最小生成樹結果 R 中。
將邊<C,D>加入 R 中。
上一步操作之后，邊<C,D>的權值最小，因此將它加入到最小生成樹結果 R 中。
將邊<D,E>加入 R 中。
上一步操作之后，邊<D,E>的權值最小，因此將它加入到最小生成樹結果 R 中。
將邊<B,F>加入 R 中。
上一步操作之后，邊<C,E>的權值最小，但<C,E>會和已有的邊構成回路；因此，跳過邊<C,E>。同理，跳過邊<C,F>。將邊<B,F>加入到最小生成樹結果 R 中。
將邊<E,G>加入 R 中。
上一步操作之后，邊<E,G>的權值最小，因此將它加入到最小生成樹結果 R 中。
將邊<A,B>加入 R 中。
上一步操作之后，邊<F,G>的權值最小，但<F,G>會和已有的邊構成回路；因此，跳過邊<F,G>。同理，跳過邊<B,C>。將邊<A,B>加入到最小生成樹結果 R 中。
此時，最小生成樹構造完成！它包括的邊依次是：
<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。
克魯斯卡爾算法分析
根據前面介紹的克魯斯卡爾算法的基本思想和做法，我們能夠了解到，克魯斯卡爾算法重點需要解決的以下兩個問題：
問題一很好解決，采用排序算法進行排序即可。
問題二，處理方式是：記錄頂點在"最小生成樹"中的終點，頂點的終點是"在最小生成樹中與它連通的最大頂點"。
然后每次需要將一條邊添加到最小生存樹時，判斷該邊的兩個頂點的終點是否重合，重合的話則會構成回路。
如何判斷是否構成回路
在將<E,F> <C,D> <D,E>加入到最小生成樹 R 中之后，這幾條邊的頂點就都有了終點：
- C 的終點是 F。
- D 的終點是 F。
- E 的終點是 F。
- F 的終點是 F。
關于終點的說明：
就是將所有頂點按照從小到大的順序排列好之后；某個頂點的終點就是"與它連通的最大頂點"。
因此，接下來，雖然<C,E>是權值最小的邊。但是 C 和 E 的終點都是 F，即它們的終點相同，因此，將<C,E> 加入最小生成樹的話，會形成回路。這就是判斷回路的方式。也就是說，我們加入的邊的兩個頂點不能都指向同一個終點，否則將構成回路。
代碼實現
package cn.chasing.Algorithm.kruskal;import java.util.Arrays;/*** @author 柴柴快樂每一天* @create 2021-08-25 11:05 下午* <p>* 『Stay hungry, stay foolish. 』*/ public class KruskalCaseDemo {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 kruskalCase = new KruskalCase(vertexs, matrix);kruskalCase.showMatrix();kruskalCase.kruskal();} }class KruskalCase {/**邊的個數*/private int edgeNum;private char[] vertexes;private int[][] matrix;private Edge[] edges;private static final int INF = Integer.MAX_VALUE;/*** 創建最小生成樹，實現克魯斯卡爾算法* @param vertexes 頂點數組* @param matrix 鄰接矩陣*/public KruskalCase(char[] vertexes, int[][] matrix) {int vLen = vertexes.length;// 初始化頂點，復制拷貝數據的方式this.vertexes = new char[vLen];for (int i = 0; i < vLen; i++) {this.vertexes[i] = vertexes[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];}}// 統計邊的條數，AB和BA是一條邊，統計上三角，不算對角線，自己跟自己沒有算邊for (int i = 0; i < vLen; i++) {for (int j = i+1; j < vLen; j++) {if (this.matrix[i][j] != INF) {edgeNum++;}}}}/*** 打印鄰接矩陣*/public void showMatrix() {System.out.println("鄰接矩陣為: \n");for(int i = 0; i < vertexes.length; i++) {for(int j=0; j < vertexes.length; j++) {System.out.printf("%12d", matrix[i][j]);}System.out.println();//換行}}/*** 通過頂點的值返回其對應下標* @param c 頂點的值，如 A, B* @return 返回c對應的下標，找不到則返回-1*/public int getPosition(char c) {for (int i = 0; i < vertexes.length; i++) {if (vertexes[i] == c) {return i;}}return -1;}/*** 獲取圖中的邊的信息，存放到Edge[]數組中* 通過matrix鄰接矩陣來獲取* 數組形如[ ['A','B', 12], ['B','F',7], ..... ]*/public void setEdges() {int index = 0;this.edges = new Edge[edgeNum];for (int i = 0; i < vertexes.length; i++) {for (int j = i+1; j < vertexes.length; j++) {if (matrix[i][j] != INF) {// i始終比j小，對應后面ends[end1] = end2edges[index++] = new Edge(vertexes[i], vertexes[j], matrix[i][j]);}}}}/*** 對edges數組按照權值進行排序*/public void sortEdges() {Arrays.sort(this.edges);}/*** 獲取下標為i的頂點的終點下標，用于后面判斷兩個終點是否相同* @param ends 終點數組。數組動態記錄各個頂點在加入子圖后對應終點是哪個。ends在加入過程中動態更新* @param i 傳入的頂點的對應下標* @return 下標為i的頂點其對應的終點下標*/public int findEnd(int[] ends, int i) {// 終點數組ends[0,0,0,0,5,0,0,0,0,0,0,0]while (ends[i] != 0) {i = ends[i];}// 節點在未加入子圖時候，終點默認就是自己return i;}public void kruskal() {int index = 0;// 用于保存“已有最小生成樹”中的每個頂點在其中的終點，該數組動態更新int[] ends = new int[edgeNum];// 創建結果數組，保存最后的最小生成樹Edge[] res = new Edge[vertexes.length-1];// 獲取圖中所有邊的集合(12條)this.setEdges();System.out.println("圖的邊的集合=" + Arrays.toString(edges) + " 共"+ edges.length);// 按照邊的權值將邊排序this.sortEdges();System.out.println("圖的邊的集合=" + Arrays.toString(edges) + " 共"+ edges.length);// 遍歷edges數組，將邊添加到最小生成樹中，判斷準備加入的邊是否會形成回路for (int i = 0; i < edgeNum; i++) {// 獲取邊的兩個頂點int p1 = getPosition(edges[i].start);int p2 = getPosition(edges[i].end);// 分別獲取這兩個點對應的終點,ends初始化為[0,0,0,0,0,0,0,0,0,0,0,0]int end1 = findEnd(ends, p1);int end2 = findEnd(ends, p2);if (end1 != end2) {// 未構成回路，則替m對應的字符，設置在最小生成樹中的終點，如<E, F>。/*** @See setEdges() i永遠比j小，導致start對應字符永遠比end小*/ends[end1] = end2;res[index++] = edges[i];}}// 統計并打印最小生成樹//<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。System.out.println("最小生成樹為");for(int i = 0; i < index; i++) {System.out.println(res[i]);}}}class Edge implements Comparable<Edge>{char start;char end;int weight;/*** 對象實例表示一條邊* @param start 邊的一個頂點* @param end 邊的另一個頂點* @param weight 邊的權值*/public Edge(char start, char end, int weight) {this.start = start;this.end = end;this.weight = weight;}@Overridepublic int compareTo(Edge o) {return this.weight - o.weight;}@Overridepublic String toString() {return "Edge [<" + start + ", " + end + ">= " + weight + "]";} }迪杰斯特拉算法
迪杰斯特拉(Dijkstra)算法介紹
迪杰斯特拉(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 到達的)
重復執行兩步驟，直到最短路徑頂點為目標頂點即可結束
迪杰斯特拉(Dijkstra)算法最佳應用-最短路徑
問題描述
戰爭時期，勝利鄉有 7 個村莊(A, B, C, D, E, F, G) ，現在有六個郵差，從 G 點出發，需要分別把郵件分別送到A, B, C , D, E, F 六個村莊
各個村莊的距離用邊線表示(權) ，比如 A – B 距離 5 公里
問：如何計算出 G 村莊到 其它各個村莊的最短距離?
如果從其它點出發到各個點的最短距離又是多少?
思路圖解
代碼實現
package cn.chasing.Algorithm.dijkstra;import java.util.Arrays;/*** @author 柴柴快樂每一天* @create 2021-08-26 3:09 下午* <p>* 『Stay hungry, stay foolish. 』*/ public class DijkstraAlgorithm {public static void main(String[] args) {char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };//鄰接矩陣int[][] matrix = new int[vertex.length][vertex.length];// 表示不可以連接final int N = 65535;matrix[0]=new int[]{N,5,7,N,N,N,2};matrix[1]=new int[]{5,N,N,9,N,N,3};matrix[2]=new int[]{7,N,N,N,8,N,N};matrix[3]=new int[]{N,9,N,N,N,4,N};matrix[4]=new int[]{N,N,8,N,N,5,4};matrix[5]=new int[]{N,N,N,4,5,N,6};matrix[6]=new int[]{2,3,N,N,4,6,N};//創建 Graph對象Graph graph = new Graph(vertex, matrix);//測試, 看看圖的鄰接矩陣是否okgraph.showGraph();//測試迪杰斯特拉算法graph.dijkstra(6);graph.showDijkstra();} }class Graph {private char[] vertex;private int[][] matrix;private Vertex ver;public Graph(char[] vertex, int[][] matrix) {this.vertex = vertex;this.matrix = matrix;}public void showDijkstra() {ver.showRes();}public void showGraph() {for (int[] ints : matrix) {System.out.println(Arrays.toString(ints));}}/*** 更新index頂點到其他頂點的距離，更新頂點的前驅頂點* 即更新dis，pre_visited* @param index 訪問頂點的下標*/private void update(int index) {// 表示 出發頂點 到index頂點的距離int distance = 0;// 遍歷matrix數組第index行的數據for (int i = 0; i < matrix[index].length; i++) {distance = ver.getDis(index) + matrix[index][i];if (!ver.isVisited(i) && distance < ver.getDis(i)) {ver.updateDis(distance, i);// 將index節點的前驅節點設置為iver.updatePre(i, index);}}}/*** 迪杰斯特拉算法實現* @param index 出發頂點的下標*/public void dijkstra(int index) {this.ver = new Vertex(vertex.length, index);// 更新距離和前驅節點update(index);for (int i = 0; i < vertex.length; i++) {// 選擇并返回新的訪問節點index = ver.updateArr();// 更新距離和前驅節點update(index);}} }class Vertex {/*** already_arr 記錄各個頂點是否訪問過* pre_visited 每個頂點對應的前一個頂點下標，動態更新* dis 記錄出發頂點到其他所有頂點的距離，會動態更新，始終保持最短距離*/public int[] already_arr;public int[] pre_visited;public int[] dis;/**** @param number 表示頂點的個數* @param index 出發頂點對應的下標*/public Vertex (int number, int index) {this.already_arr = new int[number];this.pre_visited = new int[number];this.dis = new int[number];// 初始化dis數組，到所有節點距離都為最大值，到自身為0Arrays.fill(dis, 65535);this.dis[index] = 0;// 設置出發節點已被訪問this.already_arr[index] = 1;}/*** 判斷下標為index的頂點是否被訪問* @param index 下標* @return 已被訪問則返回true，否則返回false*/public boolean isVisited (int index) {return already_arr[index] == 1;}/*** 返回出發頂點到index頂點的距離* @param index 頂點下標* @return 到該頂點的距離*/public int getDis(int index) {return dis[index];}/*** 更新出發頂點到index頂點的距離* @param len 新距離* @param index 頂點下標*/public void updateDis (int len, int index) {dis[index] = len;}/*** 更新index頂點的前驅節點* @param pre 新前驅節點* @param index 待更新節點*/public void updatePre(int pre, int index) {pre_visited[index] = pre;}/*** 繼續選擇并返回新的訪問頂點，但是并沒有更換出發節點* @return 返回新訪問頂點*/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;}/*** 顯示最后的結果，即將3個數組的情況輸出*/public void showRes() {System.out.println("===================");// 輸出already_arrfor (int i : already_arr) {System.out.print(i + " ");}System.out.println();// 輸出pre_visitedfor (int i : pre_visited) {System.out.print(i + " ");}System.out.println();// 輸出disfor (int di : dis) {System.out.print(di + " ");}System.out.println();char[] vertexes = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };int count = 0;for (int di : dis) {if (di != 65535) {System.out.println(vertexes[count++] + "(" + di + ") ");} else {System.out.println("N ");}}System.out.println();}}弗洛伊德算法
弗洛伊德(Floyd)算法介紹
弗洛伊德(Floyd)算法圖解分析
設置頂點 vi 到頂點 vk 的最短路徑已知為 Lik，頂點 vk 到 vj 的最短路徑已知為 Lkj，頂點 vi 到 vj 的路徑為 Lij，則 vi 到 vj 的最短路徑為：min((Lik+Lkj),Lij)，vk 的取值為圖中所有頂點，則可獲得 vi 到 vj 的最短路徑
至于 vi 到 vk 的最短路徑 Lik 或者 vk 到 vj 的最短路徑 Lkj，是以同樣的方式獲得
弗洛伊德(Floyd)算法最佳應用-最短路徑
代碼實現
package cn.chasing.Algorithm.floyd;import java.util.Arrays;/*** @author 柴柴快樂每一天* @create 2021-08-27 9:56 上午* <p>* 『Stay hungry, stay foolish. 』*/ 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,matrix);//調用弗洛伊德算法graph.floyd();graph.show();}}class Graph {/*** vertex 存放頂點的數組* dis 表示從各個頂點到其他結點的距離，動態更新，最后結果儲存在此數組中* pre 表示各節點的到達目標節點的中間節點*/private char[] vertex;private int[][] dis;private int[][] pre;public Graph (char[] vertex, int[][] matrix) {int len = vertex.length;this.vertex = vertex;this.dis = matrix;this.pre = new int[len][len];for (int i = 0; i < len; i++) {Arrays.fill(pre[i], i);}}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.printf(vertex[pre[k][i]] + "\t\t\t");}System.out.println();// 輸出dis數組的一行數據for (int i = 0; i < dis.length; i++) {System.out.print("("+vertex[k]+"->"+vertex[i]+"=" + dis[k][i] + ")\t");}System.out.println();System.out.println();}}public void floyd() {int len = 0;int disLen = dis.length;//對中間頂點遍歷， k 就是中間頂點的下標 [A, B, C, D, E, F, G]for (int k = 0; k < disLen; k++) {//從i頂點開始出發 [A, B, C, D, E, F, G]for (int i = 0; i < disLen; i++) {//到達j頂點 [A, B, C, D, E, F, G]for (int j = 0; j < disLen; j++) {/// => 求出從i頂點出發，經過k中間頂點，到達j頂點距離// ik之間也可能還有其他節點len = dis[i][k] + dis[k][j];if (len < dis[i][j]) {// 更新距離dis[i][j] = len;// 更新終點的前驅節點// i到j會經過的中間節點必然是k到j要經過的中間節點pre[i][j] = pre[k][j];}}}}} }運行結果
馬踏棋盤算法
馬踏棋盤算法介紹和游戲演示
思路圖解
代碼實現
package cn.chasing.Algorithm.knightTour;import java.awt.*; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator;/*** @author 柴柴快樂每一天* @create 2021-08-27 5:09 下午* <p>* 『Stay hungry, stay foolish. 』*/ public class KnightTourAlgorithm {public static void main(String[] args) {KnightTour knightTour = new KnightTour(8, 8);int row = 1;int column = 1;knightTour.knightTour(row-1, column-1, 1);for (int[] ints : knightTour.chessBoard) {System.out.println(Arrays.toString(ints));}} }class KnightTour {/*** X 列數* Y 行數* visited 標記各個位置是否被訪問過* finished 標記是否所有位置都已被訪問*/private int X;private int Y;private boolean[] visited;private boolean finished;public int[][] chessBoard;public KnightTour(int X, int Y) {this.X = X;this.Y = Y;this.visited = new boolean[X*Y];this.finished = false;this.chessBoard = new int[X][Y];}/*** 根據當前位置（Point對象），計算馬兒還能走哪些位置，并放到一個集合中，最多有8個位置* @param curPoint 當前馬兒的位置* @return 返回能走位置的集合*/public ArrayList<Point> next(Point curPoint) {// 創建一個ArrayListArrayList<Point> points = new ArrayList<>();// 創建一個PointPoint p = new Point();// 表示馬兒可以走p這個位置if ((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y) >= 0) {points.add(new Point(p));}//判斷馬兒可以走6這個位置if((p.x = curPoint.x - 1) >=0 && (p.y=curPoint.y-2)>=0) {points.add(new Point(p));}//判斷馬兒可以走7這個位置if ((p.x = curPoint.x + 1) < X && (p.y = curPoint.y - 2) >= 0) {points.add(new Point(p));}//判斷馬兒可以走0這個位置if ((p.x = curPoint.x + 2) < X && (p.y = curPoint.y - 1) >= 0) {points.add(new Point(p));}//判斷馬兒可以走1這個位置if ((p.x = curPoint.x + 2) < X && (p.y = curPoint.y + 1) < Y) {points.add(new Point(p));}//判斷馬兒可以走2這個位置if ((p.x = curPoint.x + 1) < X && (p.y = curPoint.y + 2) < Y) {points.add(new Point(p));}//判斷馬兒可以走3這個位置if ((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y + 2) < Y) {points.add(new Point(p));}//判斷馬兒可以走4這個位置if ((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y + 1) < Y) {points.add(new Point(p));}return points;}/*** 將每一個能走的位置的下一個能走位置個數進行非遞減排序，減少回溯的次數* @param points 能走的位置集合*/public void sortNext(ArrayList<Point> points) {points.sort(new Comparator<Point>() {@Overridepublic int compare(Point o1, Point o2) {// 獲取到o1的下一步的所有位置個數int count1 = next(o1).size();int count2 = next(o2).size();if (count1 < count2) {return -1;} else if (count1 == count2) {return 0;} else {return 1;}}});}public void knightTour(int row, int column, int step) {this.chessBoard[row][column] = step;// 標記該位置已訪問this.visited[row*X+column] = true;// 獲取當前位置下一步可以走哪些位置ArrayList<Point> next = next(new Point(column, row));// 對next進行排序，貪心優化sortNext(next);// 遍歷nextwhile (!next.isEmpty()) {// 取出下一個可以走的位置Point p = next.remove(0);// 判斷該節點是否訪問過if (!visited[p.y*X + p.x]) {// 沒有訪問過則繼續knightTour(p.y, p.x, step+1);}}// 判斷馬兒是否完成任務，如果沒有，則將整個棋盤置為0// step < X*Y//1. 棋盤到目前位置，仍然沒有走完//2. 棋盤處于回溯狀態if (step < X*Y && !finished) {chessBoard[row][column] = 0;visited[row*X + column] = false;} else {finished = true;}}}總結
以上是生活随笔為你收集整理的DSA_常用10种算法（java数据结构与算法）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ubuntu 18.04 安装网易云音乐
- 下一篇： C和指针 第13章 高级指针话题 13.