算法很美，聽我講完這些Java經(jīng)典算法包你愛上她

大家好，我是小羽。

對于編程來說的話，只有掌握了算法才是了解了編程的靈魂，算法對于新手來說的話，屬實有點難度，但是以后想有更好的發(fā)展，得到更好的進階的話，對算法進行系統(tǒng)的學習是重中之重的。

對于 Java 程序員來說，這一門后端語言只是我們的外功，我們更多的是學習它的語法，框架以及一些工具的使用。而算法才是我們真正的內(nèi)功，它更多的是關注如何設計系統(tǒng)，如何編寫高性能的代碼，不斷培養(yǎng)我們的思維能力，從而提升我們的工作效率。

小羽今天為大家介紹的是關于 Java 中我們需要了解的一些經(jīng)典算法，希望大家能從這些經(jīng)典算法中，品嘗到算法的美妙與奇特，對她產(chǎn)生興趣，更好的為我們的職業(yè)發(fā)展助力前行。好了，開始進入我們的正文：

二分查找

簡介

基本思想：又叫折半查找，要求待查找的序列有序，是一種快速查找算法，時間復雜度為 O(logn)，要求數(shù)據(jù)集為一個有序數(shù)據(jù)集。

使用

應用場景：一般用于查找數(shù)組元素，并且數(shù)組在查找之前必須已經(jīng)排好序（一般是升序）。

步驟：

1、取中間位置的值與待查關鍵字比較，如果中間位置的值比待查關鍵字大，則在前半部分循環(huán)這個查找的過程，

2、如果中間位置的值比待查關鍵字小，則在后半部分循環(huán)這個查找的過程。

3、直到查找到了為止，否則序列中沒有待查的關鍵字。

代碼示例：

public static int biSearch(int []array,int a){
    int lo=0;
    int hi=array.length-1;
    int mid;
    while(lo<=hi){
        mid=(lo+hi)/2;//中間位置
        if(array[mid]==a){
            return mid+1;
        }else if(array[mid]<a){ //向右查找
            lo=mid+1;
        }else{ //向左查找
            hi=mid-1;
        } 
  }
    return -1;
}

冒泡排序算法

簡介

基本思想：比較前后相鄰的兩個數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將這二個數(shù)據(jù)交換。這樣對數(shù)組的第 0 個數(shù)據(jù)到 N-1 個數(shù)據(jù)進行一次遍歷后，最大的一個數(shù)據(jù)就“沉”到數(shù)組第 N-1 個位置。N=N-1，如果 N 不為 0 就重復前面二步，否則排序完成。

使用

應用場景：數(shù)據(jù)量不大，對穩(wěn)定性有要求，且數(shù)據(jù)基本有序的情況。

步驟：

1、將序列中所有元素兩兩比較，將最大的放在最后面。

2、將剩余序列中所有元素兩兩比較，將最大的放在最后面。

3、重復第二步，直到只剩下一個數(shù)。

代碼示例：

public static void bubbleSort1(int [] a, int n){
    int i, j;
    for(i=0; i<n; i++){//表示 n 次排序過程。
        for(j=1; j<n-i; j++){
            if(a[j-1] > a[j]){//前面的數(shù)字大于后面的數(shù)字就交換
                //交換 a[j-1]和 a[j]
                int temp;
                temp = a[j-1];
                a[j-1] = a[j];
                a[j]=temp;
            } 
    }
  }
}

插入排序算法

簡介

基本思想：通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應的位置并插入。

使用

應用場景：數(shù)據(jù)量不大，對算法的穩(wěn)定性有要求，且數(shù)據(jù)局部或者整體有序的情況。

步驟：

1、將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。

2、從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）

代碼示例：

public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 對 arr 進行拷貝，不改變參數(shù)內(nèi)容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 從下標為1的元素開始選擇合適的位置插入，因為下標為0的只有一個元素，默認是有序的
        for (int i = 1; i < arr.length; i++) {

            // 記錄要插入的數(shù)據(jù)
            int tmp = arr[i];

            // 從已經(jīng)排序的序列最右邊的開始比較，找到比其小的數(shù)
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的數(shù)，插入
            if (j != i) {
                arr[j] = tmp;
            }

        }
        return arr;
    }
}

快速排序算法

簡介

基本思想：選擇一個關鍵值作為基準值。比基準值小的都在左邊序列（一般是無序的），比基準值大的都在右邊（一般是無序的）。一般選擇序列的第一個元素。

使用

應用場景：數(shù)值范圍較大，相同值的概率較小，數(shù)據(jù)量大且不考慮穩(wěn)定性的情況，數(shù)值遠大于數(shù)據(jù)量時威力更大。

步驟：

1、一次循環(huán)，從后往前比較，用基準值和最后一個值比較，如果比基準值小的交換位置，如果沒有繼續(xù)比較下一個，直到找到第一個比基準值小的值才交換。

2、找到這個值之后，又從前往后開始比較，如果有比基準值大的，交換位置，如果沒有繼續(xù)比較下一個，直到找到第一個比基準值大的值才交換。

3、直到從前往后的比較索引 > 從后往前比較的索引，結(jié)束第一次循環(huán)，此時，對于基準值來說，左右兩邊就是有序的了。

代碼示例：

public void sort(int[] a,int low,int high){
    int start = low;
    int end = high;
    int key = a[low]; 
        while(end>start){
            //從后往前比較
            while(end>start&&a[end]>=key) 
                //如果沒有比關鍵值小的，比較下一個，直到有比關鍵值小的交換位置，然后又從前往后比較
                end--;
            if(a[end]<=key){
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            //從前往后比較
            while(end>start&&a[start]<=key)
                //如果沒有比關鍵值大的，比較下一個，直到有比關鍵值大的交換位置
                start++;
            if(a[start]>=key){
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
        //此時第一次循環(huán)比較結(jié)束，關鍵值的位置已經(jīng)確定了。左邊的值都比關鍵值小，右邊的值都比關鍵值大，但是兩邊的順序還有可能是不一樣的，進行下面的遞歸調(diào)用
        }
        //遞歸
        if(start>low) sort(a,low,start-1);//左邊序列。第一個索引位置到關鍵值索引-1
        if(end<high) sort(a,end+1,high);//右邊序列。從關鍵值索引+1 到最后一個
    }
}

希爾排序算法

簡介

基本思想：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

使用

應用場景：數(shù)據(jù)量較大，不要求穩(wěn)定性的情況。

步驟：

1、選擇一個增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；

2、按增量序列個數(shù) k，對序列進行 k 趟排序；

3、每趟排序，根據(jù)對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

代碼示例：

private void shellSort(int[] a) {
    int dk = a.length/2; 
    while( dk >= 1 ){ 
        ShellInsertSort(a, dk); 
        dk = dk/2;
    }
}

private void ShellInsertSort(int[] a, int dk) {
    //類似插入排序，只是插入排序增量是 1，這里增量是 dk,把 1 換成 dk 就可以了
    for(int i=dk;i<a.length;i++){
        if(a[i]<a[i-dk]){
            int j;
            int x=a[i];//x 為待插入元素
            a[i]=a[i-dk];
            for(j=i-dk; j>=0 && x<a[j];j=j-dk){
                //通過循環(huán)，逐個后移一位找到要插入的位置。
                a[j+dk]=a[j];
            }
            a[j+dk]=x;//插入
        }
  }
}

歸并排序算法

簡介

基本思想：歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。

場景使用

應用場景：內(nèi)存少的時候使用，可以進行并行計算的時候使用。

步驟：

1、選擇相鄰兩個數(shù)組成一個有序序列。

2、選擇相鄰的兩個有序序列組成一個有序序列。

3、重復第二步，直到全部組成一個有序序列。

代碼示例：

public class MergeSortTest { 
    public static void main(String[] args) { 
        int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; 
        print(data); 
        mergeSort(data); 
        System.out.println("排序后的數(shù)組："); 
        print(data); 
    } 

  public static void mergeSort(int[] data) { 
        sort(data, 0, data.length - 1); 
    } 

  public static void sort(int[] data, int left, int right) { 
        if (left >= right) 
            return; 
        // 找出中間索引
        int center = (left + right) / 2; 
        // 對左邊數(shù)組進行遞歸
        sort(data, left, center); 
        // 對右邊數(shù)組進行遞歸
        sort(data, center + 1, right); 
        // 合并
        merge(data, left, center, right); 
        print(data); 
    } 

    /** 
    * 將兩個數(shù)組進行歸并，歸并前面 2 個數(shù)組已有序，歸并后依然有序
    * @param data 
    * 數(shù)組對象
    * @param left 
    * 左數(shù)組的第一個元素的索引
    * @param center 
    * 左數(shù)組的最后一個元素的索引，center+1 是右數(shù)組第一個元素的索引
    * @param right 
    * 右數(shù)組最后一個元素的索引
    */ 
    public static void merge(int[] data, int left, int center, int right) { 
        // 臨時數(shù)組
        int[] tmpArr = new int[data.length]; 
        // 右數(shù)組第一個元素索引
        int mid = center + 1; 
        // third 記錄臨時數(shù)組的索引
        int third = left; 
        // 緩存左數(shù)組第一個元素的索引
        int tmp = left; 
        while (left <= center && mid <= right) { 
            // 從兩個數(shù)組中取出最小的放入臨時數(shù)組
            if (data[left] <= data[mid]) { 
                tmpArr[third++] = data[left++]; 
            } else { 
                tmpArr[third++] = data[mid++]; 
            } 
        } 
        // 剩余部分依次放入臨時數(shù)組（實際上兩個 while 只會執(zhí)行其中一個）
        while (mid <= right) { 
            tmpArr[third++] = data[mid++]; 
        } 
        while (left <= center) { 
            tmpArr[third++] = data[left++]; 
        } 
        // 將臨時數(shù)組中的內(nèi)容拷貝回原數(shù)組中
        // （原 left-right 范圍的內(nèi)容被復制回原數(shù)組）
        while (tmp <= right) { 
            data[tmp] = tmpArr[tmp++]; 
        } 
    } 

    public static void print(int[] data) { 
        for (int i = 0; i < data.length; i++) { 
            System.out.print(data[i] + "\t"); 
        } 
        System.out.println(); 
    } 
}

桶排序算法

簡介

基本思想： 把數(shù)組 arr 劃分為 n 個大小相同子區(qū)間（桶），每個子區(qū)間各自排序，最后合并 。計數(shù)排序是桶排序的一種特殊情況，可以把計數(shù)排序當成每個桶里只有一個元素的情況。

使用

應用場景：在數(shù)據(jù)量非常大，而空間相對充裕的時候是很實用的，可以大大降低算法的運算數(shù)量級。

步驟：

1、找出待排序數(shù)組中的最大值 max、最小值 min

2、我們使用動態(tài)數(shù)組 ArrayList 作為桶，桶里放的元素也用 ArrayList 存儲。桶的數(shù)量為(maxmin)/arr.length+1

3、遍歷數(shù)組 arr，計算每個元素 arr[i] 放的桶

4、每個桶各自排序

代碼示例：

public static void bucketSort(int[] arr){
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    //創(chuàng)建桶
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    //將每個元素放入桶
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    //對每個桶進行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }
}

基數(shù)排序算法

簡介

基本思想：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后,數(shù)列就變成一個有序序列。

使用

應用場景：用于大量數(shù)，很長的數(shù)進行排序時的情況。

步驟：

1、將所有的數(shù)的個位數(shù)取出，按照個位數(shù)進行排序，構(gòu)成一個序列。

2、將新構(gòu)成的所有的數(shù)的十位數(shù)取出，按照十位數(shù)進行排序，構(gòu)成一個序列。

代碼示例：

public class radixSort {
    inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51};

  public radixSort(){
        sort(a);
        for(inti=0;i<a.length;i++){
            System.out.println(a[i]);
        }
  }

    public void sort(int[] array){
        //首先確定排序的趟數(shù);
        int max=array[0];
        for(inti=1;i<array.length;i++){
            if(array[i]>max){
                max=array[i];
            }
    }
        int time=0;
        //判斷位數(shù);
        while(max>0){
            max/=10;
            time++;
        }
        //建立 10 個隊列;
        List<ArrayList> queue=newArrayList<ArrayList>();
        for(int i=0;i<10;i++){
            ArrayList<Integer>queue1=new ArrayList<Integer>();
            queue.add(queue1);
        }
        //進行 time 次分配和收集;
        for(int i=0;i<time;i++){
            //分配數(shù)組元素;
           for(intj=0;j<array.length;j++){
                //得到數(shù)字的第 time+1 位數(shù);
                int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i);
                ArrayList<Integer>queue2=queue.get(x);
                queue2.add(array[j]);
                queue.set(x, queue2);
            }
            int count=0;//元素計數(shù)器;
            //收集隊列元素;
            for(int k=0;k<10;k++){
                while(queue.get(k).size()>0){
                    ArrayList<Integer>queue3=queue.get(k);
                    array[count]=queue3.get(0);
                    queue3.remove(0);
                    count++;
                }
      }
    }
  }
}

剪枝算法

簡介

基本思想：在搜索算法中優(yōu)化中，剪枝，就是通過某種判斷，避免一些不必要的遍歷過程，形象的說，就是剪去了搜索樹中的某些“枝條”，故稱剪枝。應用剪枝優(yōu)化的核心問題是設計剪枝判斷方法，即確定哪些枝條應當舍棄，哪些枝條應當保留的方法。

使用

應用場景：通常應用在 DFS 和 BFS 搜索算法中，尋找過濾條件，提前減少不必要的搜索路徑。

步驟：

1、基于訓練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大；

2、用驗證數(shù)據(jù)集最已生成的樹進行剪枝并選擇最優(yōu)子樹，這時用損失函數(shù)最小作為剪枝的標準

代碼示例：

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        LinkedList<Integer> track = new LinkedList<>();
        combinationSum(candidates, 0, target, track);
        return result;
    }

    private List<List<Integer>> result = new ArrayList<>();

    private void combinationSum(int[] candidates, int start, int target, LinkedList<Integer> track) {
        if (target < 0) {
            return;
        } else if (target == 0) {
            result.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (target < candidates[i]) {
                break;
            }
            track.add(candidates[i]);
            combinationSum(candidates, i, target - candidates[i], track);
            track.removeLast();
        }

    }
}

回溯算法

簡介

基本思想：回溯算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發(fā)現(xiàn)已不滿足求解條件時，就“回溯”返回，嘗試別的路徑。

使用

應用場景：設置一個遞歸函數(shù)，函數(shù)的參數(shù)會攜帶一些當前的可能解的信息，根據(jù)這些參數(shù)得出可能解或者不可能而回溯，平時經(jīng)常見的有 N 皇后、數(shù)獨、集合等情況。

步驟：

1、定義一個解空間，它包含問題的解；

2、利用適于搜索的方法組織解空間；

3、利用深度優(yōu)先法搜索解空間；

4、利用限界函數(shù)避免移動到不可能產(chǎn)生解的子空間。

代碼示例：

function backtrack(n, used) {
    // 判斷輸入或者狀態(tài)是否非法
    if (input/state is invalid) {
        return;
      }
    // 判讀遞歸是否應當結(jié)束，滿足結(jié)束條件就返回結(jié)果
    if (match condition) {
        return some value;
      }
    // 遍歷當前所有可能出現(xiàn)的情況，并嘗試每一種情況
    for (all possible cases) {
        // 如果上一步嘗試會影響下一步嘗試，需要寫入狀態(tài)
        used.push(case)
        // 遞歸進行下一步嘗試，搜索該子樹
        result = backtrack(n + 1, used)
        // 在這種情況下已經(jīng)嘗試完畢，重置狀態(tài)，以便于下面的回溯嘗試
        used.pop(case)
    } 
}

最短路徑算法

簡介

基本思想：從某頂點出發(fā)，沿圖的邊到達另一頂點所經(jīng)過的路徑中，各邊上權值之和最小的一條路徑叫做最短路徑。解決最短路的問題有以下算法，Dijkstra 算法，Bellman-Ford 算法，F(xiàn)loyd 算法和 SPFA 算法等。

使用

應用場景：應用有計算機網(wǎng)絡路由算法，機器人探路，交通路線導航，人工智能，游戲設計等。

步驟：（Dijkstra 算法示例）

1、 訪問路網(wǎng)中里起始點最近且沒有被檢查過的點，把這個點放入 OPEN 組中等待檢查。

2、 從OPEN表中找出距起始點最近的點，找出這個點的所有子節(jié)點，把這個點放到 CLOSE 表中。

3、 遍歷考察這個點的子節(jié)點。求出這些子節(jié)點距起始點的距離值，放子節(jié)點到 OPEN 表中。

4、重復2，3，步。直到 OPEN 表為空，或找到目標點。

代碼示例：

//Dijkstra 算法
static int[] pathSrc = new int[9];
static int[] shortPath = new int[9];
static void shortestPath_DijkStra(MGraph m, int v0) {    
    // finalPath[w] = 1 表示已經(jīng)獲取到頂點V0到Vw的最短路徑    
    int[] finalPath = new int[9];    
    for (int i = 0; i < m.numVertexes; i++) {        
        finalPath[i] = 0;        
        shortPath[i] = m.arc[v0][i];        
        pathSrc[i] = 0;    
    }    
    // v0到v0的路徑為0    
    shortPath[v0] = 0;    
    // vo到v0不需要求路徑    
    finalPath[v0] = 1;    
    for (int i = 1; i < m.numVertexes; i++) {        
        // 當前所知的離V0最近的距離        
        int min = INFINITY;        
        int k = 0;        
        for (int w = 0; w < m.numVertexes; w++) {            
            if(shortPath[w] < min && finalPath[w] == 0) {                
                min = shortPath [w];                
                k = w;            
            }        
        }  
        finalPath[k] = 1; // 修改finalPath的值，標記為已經(jīng)找到最短路徑
        for (int w = 0; w < m.numVertexes; w++) {            
            // 如果經(jīng)過V頂點的路徑比原來的路徑（不經(jīng)過V）短的話            
            if(finalPath[w] == 0 && (min + m.arc[k][w]) < shortPath[w]) {       
                // 說明找到了更短的路徑，修改                
                shortPath[w] = min + m.arc[k][w]; // 修改路徑的長度
                pathSrc[w] = k; // 修改頂點下標W的前驅(qū)頂點
            }        
        }    
    }
}

最大子數(shù)組算法

簡介

基本思想：給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

使用

應用場景：生活中可以用來查看股票一周之內(nèi)的增長狀態(tài)，需要得到最合適的買入和賣出時間。

步驟：

1、將子串和為負數(shù)的子串丟掉，只留和為正的子串。

2、如果 nums 中有正數(shù)，從左到右遍歷 nums，用變量 cur 記錄每一步的累加和，遍歷到正數(shù) cur 增加，遍歷到負數(shù) cur 減少。

3、當 cur>=0 時，每一次累加都可能是最大的累加和，所以，用另外一個變量 max 全程跟蹤記錄 cur 出現(xiàn)的最大值即可。

代碼示例：

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    int maxSubArray(vector<int> nums) {
        if(nums.size()<=0){
            return 0;
        } 
        int max=INT_MIN,cur=0;//c++最小值
        for(int i=0; i<nums.size(); i++)  
        {  
            if(cur < 0)
                cur = nums[i];//如果前面加起來的和小于0，拋棄前面的
            else
                cur+=nums[i];

            if(cur > max)
                max = cur;
        }  
        return max;  

    }
};

最長公共子序算法

簡介

基本思想：最長公共子序列是一個在一個序列集合中用來查找所有序列中最長子序列的問題。這與查找最長公共子串的問題不同的地方是：子序列不需要在原序列中占用連續(xù)的位置。

使用

應用場景：最長公共子序列問題是一個經(jīng)典的計算機科學問題，也是數(shù)據(jù)比較程序，比如 Diff 工具，和生物信息學應用的基礎。它也被廣泛地應用在版本控制，比如 Git 用來調(diào)和文件之間的改變。

步驟：

1、可以使用遞歸去解決，需要遍歷出所有的可能，很慢；

2、對于一般的 LCS 問題，都屬于 NP 問題；

3、當數(shù)列的量為一定的時，都可以采用動態(tài)規(guī)劃去解決。

代碼示例：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int length1 = text1.length();
        int length2 = text2.length();
        int[][] a = new int[length1 + 1][length2 + 1];//0行0列保留
        for(int i = 1; i <= length1; i++){
            for(int j = 1; j <= length2; j++){
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    a[i][j] = a[i - 1][j - 1] + 1;
                } else {
                    if (a[i][j - 1] > a[i-1][j]) {
                        a[i][j] = a[i][j - 1];
                    } else {
                        a[i][j] = a[i - 1][j];
                    }
                }
            }
        }
        return a[length1][length2];
    }
}

最小生成樹算法

簡介

基本思想：在含有n個頂點的帶權無向連通圖中選擇n-1條邊，構(gòu)成一棵極小連通子圖，并使該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網(wǎng)的最小生成樹（不一定唯一）。

一般情況，要解決最小生成樹問題，通常采用兩種算法：Prim算法和Kruskal算法。

使用

應用場景：一般用來計算成本最小化的情況。

步驟：（Prim 算法示例）

1、以某一個點開始，尋找當前該點可以訪問的所有的邊；

2、在已經(jīng)尋找的邊中發(fā)現(xiàn)最小邊，這個邊必須有一個點還沒有訪問過，將還沒有訪問的點加入我們的集合，記錄添加的邊；

3、尋找當前集合可以訪問的所有邊，重復 2 的過程，直到?jīng)]有新的點可以加入；

4、此時由所有邊構(gòu)成的樹即為最小生成樹。

/** prim算法
    * @param first  構(gòu)成最小生成樹的起點的標識
    * @return  返回最小生成樹構(gòu)成的邊
    */
public List<Edge> generateMinTreePrim(T first){
    //存儲最小生成樹構(gòu)成的邊
    List<Edge> result=new LinkedList<>();
    //首先建立map，key為vertex，value為edge
    HashMap<Vertex<T>, Edge> map=new HashMap<>();
    Iterator<Vertex<T>> vertexIterator=getVertexIterator();
    Vertex<T> vertex;
    Edge edge;
    while(vertexIterator.hasNext()){
        //一開始，value為edge的兩端的都為自己，weight=maxDouble
        vertex=vertexIterator.next();
        edge=new Edge(vertex, vertex, Double.MAX_VALUE);
        map.put(vertex, edge);
    }
    //first是構(gòu)成最小生成樹的起點的標識
    vertex=vertexMap.get(first);
    if(vertex==null){
        System.out.println("沒有節(jié)點："+first);
        return result;
    }
    //所有不在生成樹中的節(jié)點，都是map的key,如果map為空，代表所有節(jié)點都在樹中
    while(!map.isEmpty()){
        //這次循環(huán)要加入生成樹的節(jié)點為vertex，邊為vertex對應的edge（也就是最小的邊）
        edge=map.get(vertex);
        //每將一個結(jié)點j加入了樹A，首先從map中去除這個節(jié)點
        map.remove(vertex);
        result.add(edge);
        System.out.println("生成樹加入邊，頂點："+vertex.getLabel()+
                " ，邊的終點是："+edge.getEndVertex().getLabel()+" ，邊的權值為： "+edge.getWeight());;
        //如果是第一個節(jié)點，對應的邊是到自己的，刪除
        if(vertex.getLabel().equals(first)){
            result.remove(edge);
        }
        //然后看map中剩余的節(jié)點到節(jié)點j的距離，如果這個邊的距離小于之前邊的距離，就將邊替換成這個到節(jié)點j的邊
        //在遍歷替換中，同時發(fā)現(xiàn)距離最短的邊minEdge
        Edge minEdge=new Edge(vertex, vertex, Double.MAX_VALUE);
        for(Vertex<T> now:map.keySet()){
            edge=map.get(now);
            //newEdge為now到節(jié)點j的邊
            Edge newEdge=now.hasNeighbourVertex(vertex);
            if(newEdge!=null&&newEdge.getWeight()<edge.getWeight()){
                //如果這個邊的距離小于之前邊的距離，就將邊替換成這個到節(jié)點j的邊
                edge=newEdge;
                map.put(now, edge);
            }
            if(edge.getWeight()<minEdge.getWeight()){
                //更新minEdge
                minEdge=edge;
            }
        }
        //這里設定邊的方向是不在樹上的v（為起始點）到樹上的u
        //這條邊的起始點是不在樹上的，是下一個加入生成樹的節(jié)點
        vertex=minEdge.getBeginVertex();            
    }       
    return result;
}

最后

算法無論是對于學習還是工作，都是必不可少的。如果說我們掌握了這些算法背后的邏輯思想，那么是會對我們的學習和工作有很好的促進作用的。

其次算法對于面試，尤其是進入一些大廠 BAT 等公司都是一塊敲門磚，大公司都會通過算法來評估你的整體技術水平，如果你有很好的算法功底，相信對你未來的職場道路也會有很大幫助。

在職業(yè)發(fā)展后期，擁有良好的算法技能，可以幫助我們更快、更高效的完成編碼，往架構(gòu)師的方向發(fā)展，同樣的崗位，你有相應的算法知識的話，能拿到的薪資也會比別人更好一點。

當然，算法遠不止這些羅列的，還有很多復雜的算法需要去不斷學習，一起加油吧～

關于我