Hello everyone , I'm Xiaoyu .

For programming , Only when we master the algorithm can we understand it The soul of programming , Algorithm for novices , It's hard to be true , But I want to have better development in the future , If you get a better upgrade , Systematic learning of the algorithm is the most important .

about Java For the programmer , This back-end language is just our external skill , We learn more about its grammar , Framework and the use of some tools . And algorithm is our real internal skill , It's more about how to design systems , How to write high performance code , constantly Cultivate our thinking ability , So as to improve our work efficiency .

What Xiaoyu introduces to you today is about Java We need to know some classical algorithms in the , I hope you can learn from these classic algorithms , Taste the beauty and strangeness of algorithms , Interested in her , Better help our career development forward . Okay , Start to enter our text :

Two points search

brief introduction

The basic idea : Also called half search , Ask for the sequence to be found Orderly , It's a fast search algorithm , The time complexity is O(logn), The data set is required to be an ordered data set .

Use

Application scenarios : Commonly used in Find array Elements , And the array must be ordered before searching ( It's generally in ascending order ).

step

1、 take In the middle Compare the value of with the keyword to be looked up , If the value of the middle position is larger than the keyword to be queried , Then loop the search process in the first half ,

2、 If the value of the middle position is smaller than the keyword to be queried , Then loop the search process in the second half .

3、 until We found it until , Otherwise, there are no keywords to be searched in the sequence .

Code example :

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;// In the middle
        if(array[mid]==a){
            return mid;
        }else if(array[mid]<a){ // Search right
            lo=mid+1;
        }else{ // Search left
            hi=mid-1;
        } 
  }
    return -1;
}

Bubble sort algorithm

brief introduction

The basic idea : Compare Next to each other Two data of , If the previous data is larger than the following data , Just exchange these two data . So for the second part of the array 0 Data to N-1 After a data traversal , The biggest one is the data “ sink ” Go to array number N-1 A place .N=N-1, If N Not for 0 Just repeat the first two steps , Otherwise, the sorting is complete .

Use

Application scenarios : Not a lot of data , There are requirements for stability , And the data is basically Orderly The situation of .

step

1、 Compare all elements of the sequence in pairs , Put the biggest one at the back .

2、 Compare all elements of the remaining sequence in pairs , Put the biggest one at the back .

3、 Repeat step 2 , Until there is only a number .

Code example :

public static void bubbleSort1(int [] a, int n){
    int i, j;
    for(i=0; i<n; i++){// Express  n  Second sorting process .
        for(j=1; j<n-i; j++){
            if(a[j-1] > a[j]){// If the number in front is greater than the number in the back, we swap
                // In exchange for  a[j-1] and  a[j]
                int temp;
                temp = a[j-1];
                a[j-1] = a[j];
                a[j]=temp;
            } 
    }
  }
}

Insertion sort algorithm

brief introduction

The basic idea : By building an ordered sequence , For unsorted data , In the sorted sequence From the back forward scanning , Find the appropriate location and insert .

Use

Application scenarios : Not a lot of data , The stability of the algorithm is required , And data Part or whole An orderly situation .

step

1、 Think of the first element of the first sequence to be sorted as an ordered sequence , Think of the second element to the last as an unsorted sequence .

2、 From a to Z Scan the unordered sequence in turn , Insert each element scanned into the appropriate location in the ordered sequence .( If the element to be inserted is equal to an element in an ordered sequence , Inserts the element to be inserted after an equal element .)

Code example

public class InsertSort implements IArraySort {
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        //  Yes  arr  Copy , Do not change the parameter content
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        //  From the subscript for 1 Element to start selecting the appropriate position to insert , Because the index is zero 0 There's only one element , The default is ordered
        for (int i = 1; i < arr.length; i++) {
            //  Record the data to be inserted
            int tmp = arr[i];
            //  Start with the rightmost part of the sorted sequence , Find something smaller
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            //  There are smaller Numbers , Insert
            if (j != i) {
                arr[j] = tmp;
            }
        }
        return arr;
    }
}

Fast sorting algorithm

brief introduction

The basic idea : Select a key value as At baseline . The ones smaller than the benchmark are all in the left sequence ( It's usually out of order ), Those larger than the benchmark are on the right ( It's usually out of order ). Generally select the first element of the sequence .

Use

Application scenarios The number wide , The probability of the same value is small , Large amount of data without considering stability , It's more powerful when the number is much larger than the amount of data .

step

1、 A loop , From back to front Compare , Compare the reference value with the last value , If the exchange position is smaller than the reference value , If you don't continue to compare the next , It's not until you find the first value smaller than the reference value that you exchange .

2、 After finding this value , also Before and after Start comparing , If there is something larger than the reference value , Swap places , If you don't continue to compare the next , It's not until you find the first value greater than the reference value that you can exchange .

3、 Until the comparison index before and after > Index of comparison from back to front , End the first cycle , here , about At baseline Come on , The left and right sides are orderly .

Code example :

public void sort(int[] a,int low,int high){
    int start = low;
    int end = high;
    int key = a[low]; 
        while(end>start){
            // Compare backwards and forwards
            while(end>start&&a[end]>=key) 
                // If nothing is smaller than the key value , Compare the next , Until there is a swap position smaller than the key value , Then compare before and after
                end--;
            if(a[end]<=key){
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            // From front to back
            while(end>start&&a[start]<=key)
                // If nothing is bigger than the key value , Compare the next , Until there is a larger swap location than the key value
                start++;
            if(a[start]>=key){
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
        // At this point, the first cycle comparison is over , The location of the key values has been determined . The values on the left are all smaller than the key values , The values on the right are larger than the key values , But the order of the two sides may be different , Make the following recursive call
        }
        // recursive
        if(start>low) sort(a,low,start-1);// On the left side of the sequence . The first index position to the key value index -1
        if(end<high) sort(a,end+1,high);// The right sequence . Index from key value +1  To the last
    }
}

Hill sort algorithm

brief introduction

The basic idea : Firstly, the whole record sequence to be sorted is divided into several sub-sequences for direct insertion sort , To be recorded throughout the sequence “ The basic order ” when , All records are then directly inserted in sequence .

Use

Application scenarios : Large amount of data , Does not require stability The situation of .

step

1、 Select a sequence of deltas t1,t2,…,tk, among ti>tj,tk=1;

2、 By incremental sequence number k, Proceeding on sequence k Trip to sort ;

3、 Every trip to sort , According to the corresponding increment ti, The length of the queue is divided into several lengths m The subsequence , Each sub table is divided into two parts direct Insertion sort . The incremental factor is only 1 when , The entire sequence is treated as a table , The table length is the length of the entire sequence .

Code example

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) {
    // Similar to insert sort , It's just that the insertion sort increment is  1, Here the increment is  dk, hold  1  Switch to  dk  That's all right.
    for(int i=dk;i<a.length;i++){
        if(a[i]<a[i-dk]){
            int j;
            int x=a[i];//x  For the element to be inserted
            a[i]=a[i-dk];
            for(j=i-dk; j>=0 && x<a[j];j=j-dk){
                // Through the loop , Move back one bit at a time to find the position to insert .
                a[j+dk]=a[j];
            }
            a[j+dk]=x;// Insert
        }
  }
}

Merge sort algorithm

brief introduction

The basic idea : Merger (Merge) The sorting method is to put two ( Or more than two ) An ordered table is merged into a new ordered table , That is, the sequence to be sorted is divided into several subsequences , Every subsequence is ordered . And then the ordered subsequence Merge It's a whole ordered sequence .

Scene use

Application scenarios : Use when memory is low , Can be done Parallel computing When you use .

step

1、 choice adjacent Two numbers form an ordered sequence .

2、 Select two adjacent ordered sequences to form an ordered sequence .

3、 Repeat step 2 , Until it's all in one Orderly Sequence .

Code example

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(" Sorted array :"); 
        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; 
        //  Find the middle index
        int center = (left + right) / 2; 
        //  Recurse the left array
        sort(data, left, center); 
        //  Recurse the right array
        sort(data, center + 1, right); 
        //  Merge
        merge(data, left, center, right); 
        print(data); 
    } 
    /** 
    *  Merge two arrays , Merge the front  2  Arrays are ordered , It's still orderly after the merger
    * @param data 
    *  Array objects
    * @param left 
    *  Index of the first element of the left array
    * @param center 
    *  Index of the last element of the left array ,center+1  Is the index of the first element of the right array
    * @param right 
    *  The index of the last element of the right array
    */ 
    public static void merge(int[] data, int left, int center, int right) { 
        //  Temporary array
        int[] tmpArr = new int[data.length]; 
        //  Index of the first element of the right array
        int mid = center + 1; 
        // third  Record the index of the temporary array
        int third = left; 
        //  Cache the index of the first element of the left array
        int tmp = left; 
        while (left <= center && mid <= right) { 
            //  Take the smallest of the two arrays and put it into a temporary array
            if (data[left] <= data[mid]) { 
                tmpArr[third++] = data[left++]; 
            } else { 
                tmpArr[third++] = data[mid++]; 
            } 
        } 
        //  The rest is put into the temporary array in turn ( Actually, two  while  Only one of them will be executed )
        while (mid <= right) { 
            tmpArr[third++] = data[mid++]; 
        } 
        while (left <= center) { 
            tmpArr[third++] = data[left++]; 
        } 
        //  Copy the contents of the temporary array back to the original array
        // ( primary  left-right  The contents of the range are copied back to the original array )
        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(); 
    } 
}

Bucket sorting algorithm

brief introduction

The basic idea : Put the array arr Divided into n individual Same size Subinterval ( bucket ), Each subinterval is sorted separately , Final merger . Counting sort is a special case of bucket sort , You can think of counting sort as if there is only one element in each bucket .

Use

Application scenarios : There's a huge amount of data , and There's plenty of space It's very practical when it's time , It can greatly reduce the operation order of the algorithm .

step

1、 Find the maximum value in the array to be sorted max、 minimum value min

2、 We use The dynamic array ArrayList As a barrel , The elements in the bucket are also used ArrayList Storage . The number of barrels is (maxmin)/arr.length+1

3、 Traversal array arr, Calculate each element arr[i] Put the barrel

4、 Each bucket is sorted individually

Code example

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]);
    }
    // Creating buckets
    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>());
    }
    // Place each element into the bucket
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    // Sort each bucket
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }
}

Cardinality sorting algorithm

brief introduction

The basic idea : Compare the values to be compared ( Positive integer ) Uniform to the same digit length , A shorter digit is zeroed . then , from Its lowest Start , Sort them one at a time . In this way, from the lowest ranking to the completion of the highest ranking , The sequence becomes an ordered sequence .

Use

Application scenarios : For a large number of , A long number When sorting .

step

1、 Put all the numbers into Single digit Take out , Sort by single digits , Make a sequence .

2、 All the numbers that will be newly constructed are Ten digits Take out , Sort by tens , Make a sequence .

Code example

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){
        // First, determine the number of times to sort ;
        int max=array[0];
        for(inti=1;i<array.length;i++){
            if(array[i]>max){
                max=array[i];
            }
    }
        int time=0;
        // Determine the number of digits ;
        while(max>0){
            max/=10;
            time++;
        }
        // establish  10  A queue ;
        List<ArrayList> queue=newArrayList<ArrayList>();
        for(int i=0;i<10;i++){
            ArrayList<Integer>queue1=new ArrayList<Integer>();
            queue.add(queue1);
        }
        // Conduct  time  Sub distribution and collection ;
        for(int i=0;i<time;i++){
            // Assign array elements ;
           for(intj=0;j<array.length;j++){
                // Get the number  time+1  digit ;
                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;// Element counter ;
            // Collect queue elements ;
            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++;
                }
      }
    }
  }
}

Pruning algorithm

brief introduction

The basic idea : In search algorithm optimization , prune , It's through some kind of judgment , Avoid unnecessary traversal , Image theory , Is to cut out some of the search tree “ branch ”, So it's called pruning . The core problem of applying pruning optimization is Design pruning judgment method , That is to determine which branches should be discarded , Which branches should be kept .

Use

Application scenarios : Usually used in DFS and BFS In search algorithm , seek Filter conditions , Reduce unnecessary search paths ahead of time .

step

1、 Based on training data set generation Decision tree , The decision tree should be as large as possible ;

2、 Prune the most generated tree of the validation dataset and select Optimal subtree , In this case, the minimum loss function is used as the pruning criterion

Code example

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();
        }
    }
}

Backtracking algorithm

brief introduction

The basic idea : Backtracking algorithm is actually a search attempt process similar to enumeration , Mainly in the During the search attempt Find the solution to the problem , When it is found that the solution conditions are not satisfied , Just “ to flash back ” return , Try another path .

Use

Application scenarios : Set up a recursive function , The parameters of the function carry some information about the current possible solutions , According to these parameters, we can get the possible solution or impossible solution and trace back , I often see N Queen 、 Sudoku 、 aggregate , etc. .

step

1、 Define a Solution space , It contains solutions to the problem ;

2、 Organize the solution space by using the method suitable for searching ;

3、 Use depth first method to search solution space ;

4、 Using a bounded function to avoid moving to a subspace where it is impossible to produce a solution .

Code example

function backtrack(n, used) {
    //  Determine whether the input or state is illegal
    if (input/state is invalid) {
        return;
      }
    //  Judge whether recursion should end , If the end condition is satisfied, the result is returned
    if (match condition) {
        return some value;
      }
    //  Go through all the current possibilities , And try every situation
    for (all possible cases) {
        //  If the previous attempt will affect the next attempt , Need to write status
        used.push(case)
        //  Recursion takes the next step , Search the subtree
        result = backtrack(n + 1, used)
        //  In this case, the attempt has been made , Reset state , To facilitate the following backtracking attempts
        used.pop(case)
    } 
}

Shortest path algorithm

brief introduction

The basic idea : Starting from a vertex , The path along the edge of a graph to another vertex , The sum of weights on each side is the smallest The shortest path is called the shortest path . There are the following algorithms to solve the shortest path problem ,Dijkstra Algorithm ,Bellman-Ford Algorithm ,Floyd Algorithm and SPFA Algorithm etc. .

Use

Application scenarios : Application of computer network routing algorithm , Robots explore the way , Traffic route navigation , Artificial intelligence , Game design, etc .

step :(Dijkstra Algorithm example )

1、 Visit the road network The starting point is recent and has not been checked The point of , Put this in OPEN Waiting for check in group .

2、 from OPEN Find the point closest to the starting point in the table , Find all the children of this point , Put this point in CLOSE In the table .

3、 Traverse the child nodes of this point . Find out the distance between these child nodes and the starting point , Put the child node to OPEN In the table .

4、 repeat 2,3, Step . until OPEN Table is empty , Or find the target point .

Code example

//Dijkstra  Algorithm
static int[] pathSrc = new int[9];
static int[] shortPath = new int[9];
static void shortestPath_DijkStra(MGraph m, int v0) {    
    // finalPath[w] = 1  Indicates that the vertex has been obtained V0 To Vw Shortest path     
    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 To v0 The path of is 0    
    shortPath[v0] = 0;    
    // vo To v0 There's no need to find a path     
    finalPath[v0] = 1;    
    for (int i = 1; i < m.numVertexes; i++) {        
        //  What is known at present V0 The nearest distance         
        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; //  modify finalPath Value , Mark as having found the shortest path
        for (int w = 0; w < m.numVertexes; w++) {            
            //  If passed V The path of the vertex is smaller than the original path ( Not pass V) Short words             
            if(finalPath[w] == 0 && (min + m.arc[k][w]) < shortPath[w]) {       
                //  It shows that a shorter path has been found , modify                 
                shortPath[w] = min + m.arc[k][w]; //  Modify the length of the path
                pathSrc[w] = k; //  Modify vertex subscripts W The vanguard apex of
            }        
        }    
    }
}

Maximum subarray algorithm

brief introduction

The basic idea : Given an array of integers nums , Find one with Maximum and A continuous subarray of ( A subarray contains at least one element ), Return to its maximum and .

Use

Application scenarios : Life can be used to check the stock within a week of Growth status , You need to get the best time to buy and sell .

step

1、 Discard substrings and substrings that are negative , Just stay Harmony is positive The string of .

2、 If nums There are positive numbers in , Traverse from left to right nums, With variable cur Record the sum of each step , Traverse to a positive number cur increase , Traverse to a negative number cur Reduce .

3、 When cur>=0 when , Each accumulation can be the largest accumulation sum , therefore , With another variable max Track the whole process cur The emergence of Maximum that will do .

Code example

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++ minimum value
        for(int i=0; i<nums.size(); i++)  
        {  
            if(cur < 0)
                cur = nums[i];// If the sum of the preceding sums is less than 0, Abandon the front
            else
                cur+=nums[i];
            if(cur > max)
                max = cur;
        }  
        return max;  
    }
};

The longest common suborder algorithm

brief introduction

The basic idea : The longest common subsequence is a set of subsequences used to find all of the sequences The longest subsequence The problem of . The difference between this and the problem of finding the longest common substring is : Subsequences do not need to occupy continuous positions in the original sequence .

Use

Application scenarios : The longest common subsequence problem is a classical computer science problem , It's also Data comparison program , such as Diff Tools , And the basis of bioinformatics applications . It is also widely used in version control , such as Git Used to reconcile changes between files .

step

1、 have access to recursive To solve the , You need to traverse all the possibilities , Very slowly ;

2、 For general LCS problem , All belong to NP problem ;

3、 When the quantity of a sequence is fixed , Both can be used Dynamic programming To solve the .

Code example

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 That's ok 0 Column reservation
        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];
    }
}

Minimum spanning tree algorithm

brief introduction

The basic idea : It contains n Vertex Weighted undirected connected graphs Choose from n-1 side , Form a minimal connected subgraph , And make the connected subgraph n-1 The sum of weights on the edge of the bar reaches the minimum , It is called the minimum spanning tree of connected network ( Not necessarily the only one ).

General situation , To solve the minimum spanning tree problem , There are usually two algorithms :Prim Algorithm and Kruskal Algorithm .

Use

Application scenarios : Generally used to calculate Cost minimization The situation of .

step :(Prim Algorithm example )

1、 Start at a certain point , Find the current point that can be accessed All the sides ;

2、 Found in the edges that have been searched The smallest edge , This side must have a point that has not been accessed , Add points that have not been accessed to our collection , Record the edges added ;

3、 Find all the edges that the current collection can access , repeat 2 The process of , Until there's no new point to add ;

4、 In this case, all the edges make up Trees This is the minimum spanning tree .

Code example

/** prim Algorithm
    * @param first   Identification of the starting point of the minimum spanning tree
    * @return   Returns the edge of the smallest spanning tree
    */
public List<Edge> generateMinTreePrim(T first){
    // Store the edges of the minimum spanning tree
    List<Edge> result=new LinkedList<>();
    // First set up map,key by vertex,value by edge
    HashMap<Vertex<T>, Edge> map=new HashMap<>();
    Iterator<Vertex<T>> vertexIterator=getVertexIterator();
    Vertex<T> vertex;
    Edge edge;
    while(vertexIterator.hasNext()){
        // In limine ,value by edge Both ends are for themselves ,weight=maxDouble
        vertex=vertexIterator.next();
        edge=new Edge(vertex, vertex, Double.MAX_VALUE);
        map.put(vertex, edge);
    }
    //first Is the identification of the starting point of the minimum spanning tree
    vertex=vertexMap.get(first);
    if(vertex==null){
        System.out.println(" No nodes :"+first);
        return result;
    }
    // All nodes that are not in the spanning tree , All are map Of key, If map It's empty , Represents that all nodes are in the tree
    while(!map.isEmpty()){
        // The node to be added to the spanning tree in this loop is vertex, Side is vertex Corresponding edge( That's the smallest edge )
        edge=map.get(vertex);
        // Every node j Joined the tree A, First of all, from the map Remove this node from
        map.remove(vertex);
        result.add(edge);
        System.out.println(" Spanning trees add edges , The vertices :"+vertex.getLabel()+
                " , The end of the side is :"+edge.getEndVertex().getLabel()+" , The weight of the edge is : "+edge.getWeight());;
        // If it's the first node , The corresponding edge is to its own , Delete
        if(vertex.getLabel().equals(first)){
            result.remove(edge);
        }
        // And then look map The remaining node to node j Distance of , If the distance of this side is less than the distance of the front side , Just replace the edge with this to the node j The edge of
        // In traversal substitution , At the same time, find the shortest side minEdge
        Edge minEdge=new Edge(vertex, vertex, Double.MAX_VALUE);
        for(Vertex<T> now:map.keySet()){
            edge=map.get(now);
            //newEdge by now To the node j The edge of
            Edge newEdge=now.hasNeighbourVertex(vertex);
            if(newEdge!=null&&newEdge.getWeight()<edge.getWeight()){
                // If the distance of this side is less than the distance of the front side , Just replace the edge with this to the node j The edge of
                edge=newEdge;
                map.put(now, edge);
            }
            if(edge.getWeight()<minEdge.getWeight()){
                // to update minEdge
                minEdge=edge;
            }
        }
        // The orientation of the edge is not on the tree v( As the starting point ) To the tree u
        // The starting point of this side is not in the tree , Is the next node to join the spanning tree
        vertex=minEdge.getBeginVertex();            
    }       
    return result;
}

Last

Algorithms, whether for learning or working , Are essential . If we know what's behind these algorithms Logic thinking , It will promote our study and work .

Second, the algorithm for the interview , Especially into Some big factories BAT Companies such as It's all a stepping stone , Big companies will evaluate your overall technical level through algorithms , If you have good algorithmic skills , I believe it will also be of great help to your future career path .

In the late stage of career development , Good algorithmic skills , Can help us faster 、 More efficient coding , Go to Architects Direction of development , Same position , If you have the corresponding algorithm knowledge , The salary you can get will be better than others .

Of course , The algorithm is much more than that , There are many complex algorithms to learn , Come on ~