前言

本文主要讲解10种常见算法

数据结构与算法文章列表

数据结构与算法文章列表: 点击此处跳转查看

初始化变量：界说目标值 target，数组的开端索引 start 和完毕索引 end。
循环查找：运用循环（一般是 while 循环）进行查找，直到 start 大于 end，表明没有找到目标值。
核算中心索引：经过核算中心索引 mid，能够获得数组中心元素的索引。
比较中心元素：将目标值与中心元素 array[mid] 进行比较。
- 假如目标值等于中心元素，表明找到目标值，回来中心索引 mid。
- 假如目标值小于中心元素，表明目标值在左半部分，更新完毕索引 end 为 mid - 1。
- 假如目标值大于中心元素，表明目标值在右半部分，更新开端索引 start 为 mid + 1。
重复过程 3 和 4，直到找到目标值或确认目标值不存在。

下面是 Java 代码完结二分查找的示例：

public class BinarySearch {
    public static int binarySearch(int[] array, int target) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (array[mid] == target) {
                return mid; // 找到目标值，回来索引
            } else if (array[mid] < target) {
                start = mid + 1; // 目标值在右半部分，更新开端索引
            } else {
                end = mid - 1; // 目标值在左半部分，更新完毕索引
            }
        }
        return -1; // 目标值不存在，回来 -1
    }
    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9};
        int target = 5;
        int index = binarySearch(array, target);
        if (index != -1) {
            System.out.println("目标值 " + target + " 的索引为 " + index);
        } else {
            System.out.println("目标值 " + target + " 不存在");
        }
    }
}

运转成果：

目标值 5 的索引为 2

在上述示例中，咱们界说了 binarySearch 办法，承受一个有序数组 array 和目标值 target 作为参数。该办法运用循环进行二分查找，终究回来目标值在数组中的索引，假如目标值不存在则回来 -1。

在 main 办法中，咱们创立了一个有序数组 array，并界说目标值 target 为 5。然后调用 binarySearch 办法进行查找，并输出成果。

2 分治算法

分治算法（Divide and Conquer）是一种将问题区分为更小的子问题，逐一处理子问题，然后将子问题的解兼并为原问题解的算法思维。

以下是分治算法的完结过程：

区分问题：将原问题区分为更小的子问题。这一般触及将问题分红两个或更多的子问题。
处理子问题：递归地处理区分得到的子问题。假如子问题足够小，能够直接求解。
兼并子问题的解：将子问题的解兼并为原问题的解。这是分治算法的关键过程。

下面是一个运用分治算法处理数组中最大值问题的示例代码：

public class DivideAndConquer {
    public static int findMax(int[] array, int start, int end) {
        if (start == end) {
            return array[start]; // 只要一个元素，直接回来
        } else {
            int mid = (start + end) / 2;
            // 递归地处理左右两个子问题
            int leftMax = findMax(array, start, mid);
            int rightMax = findMax(array, mid + 1, end);
            // 兼并子问题的解
            return Math.max(leftMax, rightMax);
        }
    }
    public static void main(String[] args) {
        int[] array = {7, 2, 9, 1, 5};
        int max = findMax(array, 0, array.length - 1);
        System.out.println("数组中的最大值为: " + max);
    }
}

运转成果：

数组中的最大值为: 9

在上述示例中，咱们界说了 findMax 办法，承受一个数组 array、开端索引 start 和完毕索引 end 作为参数。该办法运用分治算法递归地处理子问题，并回来数组中的最大值。

在 main 办法中，咱们创立了一个数组 array，并调用 findMax 办法找到数组中的最大值，并输出成果。

3 动态规划算法

动态规划（Dynamic Programming）是一种经过将问题区分为堆叠子问题并运用记忆化技能来加速核算的算法思维。它适用于具有堆叠子问题和最优子结构性质的问题。

以下是动态规划算法的完结过程：

界说状况：确认问题的状况，并界说状况表明。状况是问题的关键信息，它们的组合构成了问题的解空间。
界说状况搬运方程：依据问题的最优子结构性质，界说问题的状况搬运方程。状况搬运方程描绘了状况之间的关系，用于核算当时状况的值。
初始化：确认初始状况的值。初始状况是问题解空间中的边界条件，它们是处理问题的根底。
递推核算：依照状况搬运方程进行递推核算，核算出一切状况的值。
解的表明：依据问题的要求，确认如何表明问题的解。

下面是一个运用动态规划处理斐波那契数列问题的示例代码：

public class DynamicProgramming {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n; // 基本状况
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // 状况搬运方程
        }
        return dp[n]; // 回来终究成果
    }
    public static void main(String[] args) {
        int n = 6;
        int result = fibonacci(n);
        System.out.println("斐波那契数列第 " + n + " 项为: " + result);
    }
}

运转成果：

斐波那契数列第 6 项为: 8

在上述示例中，咱们界说了 fibonacci 办法，承受一个整数 n 作为参数，核算斐波那契数列的第 n 项。该办法运用动态规划算法，运用一个数组 dp 存储中心状况值。经过递推核算和状况搬运方程 dp[i] = dp[i - 1] + dp[i - 2]，得到终究成果。

在 main 办法中，咱们调用 fibonacci 办法核算斐波那契数列的第 6 项，并输出成果。

4 KMP算法

KMP算法（Knuth-Morris-Pratt Algorithm）是一种字符串匹配算法，用于在一个文本串中查找一个形式串的出现方位。它经过运用现已匹配过的部分信息，防止不必要的回溯，然后提高匹配的功率。

以下是KMP算法的完结过程：

构建部分匹配表（Partial Match Table，PMT）：关于形式串，构建一个部分匹配表，用于记载形式串中每个方位的最长公共前后缀长度。
依据部分匹配表进行匹配：在文本串中查找形式串，运用部分匹配表进行匹配过程，防止不必要的回溯。

下面是一个运用KMP算法进行字符串匹配的示例代码：

public class KMPAlgorithm {
    public static int kmpSearch(String text, String pattern) {
        int[] pmt = buildPMT(pattern);
        int i = 0; // 文本串指针
        int j = 0; // 形式串指针
        while (i < text.length() && j < pattern.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else if (j > 0) {
                j = pmt[j - 1]; // 依据部分匹配表回溯
            } else {
                i++;
            }
        }
        if (j == pattern.length()) {
            return i - j; // 回来形式串在文本串中的开端方位
        } else {
            return -1; // 未找到匹配
        }
    }
    private static int[] buildPMT(String pattern) {
        int[] pmt = new int[pattern.length()];
        int i = 0;
        int j = 1;
        while (j < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                pmt[j] = i + 1;
                i++;
                j++;
            } else if (i > 0) {
                i = pmt[i - 1]; // 依据部分匹配表回溯
            } else {
                pmt[j] = 0;
                j++;
            }
        }
        return pmt;
    }
    public static void main(String[] args) {
        String text = "ABCABDABACDABABCABDE";
        String pattern = "ABABCABDE";
        int index = kmpSearch(text, pattern);
        if (index != -1) {
            System.out.println("形式串在文本串中的开端方位：" + index);
        } else {
            System.out.println("未找到匹配");
        }
    }
}

运转成果：

形式串在文本串中的开端方位：10

在上述示例中，咱们界说了 kmpSearch 办法，承受一个文本串 text 和一个形式串 pattern 作为参数，运用KMP算法在文本串中查找形式串的开端方位。

在 kmpSearch 办法中，咱们首要调用 buildPMT 办法构建部分匹配表。然后，运用两个指针 i 和 j 别离指向文本串和形式串，经过比较字符进行匹配。假如当时字符匹配，两个指针同时后移；假如当时字符不匹配且形式串指针大于0，依据部分匹配表回溯；假如当时字符不匹配且形式串指针为0，文本串指针后移。终究回来形式串在文本串中的开端方位。

在 main 办法中，咱们界说了一个文本串 text 和一个形式串 pattern，调用 kmpSearch 办法进行匹配，并输出成果。

5 贪心算法

贪心算法（Greedy Algorithm）是一种在每一步挑选中都挑选当时最优解的算法思维。它经过贪心的挑选办法，希望终究得到全局最优解。但是，贪心算法不能确保一定能得到最优解，因此在运用贪心算法时需求留意问题的性质和是否适用贪心策略。

以下是贪心算法的完结过程：

确认问题的贪心挑选办法：依据问题的性质，确认每一步的贪心挑选办法，即当时最优解。
结构问题的解：经过贪心挑选办法，逐渐结构问题的解。
查看解的有效性：查看结构的解是否满意问题的约束条件和要求。
更新问题的状况：依据问题的性质，更新问题的状况，继续下一步的贪心挑选。

下面是一个运用贪心算法处理找零钱问题的示例代码：

import java.util.Arrays;
public class GreedyAlgorithm {
    public static int[] findMinCoins(int[] coins, int amount) {
        Arrays.sort(coins); // 将零钱面额按升序排序
        int[] result = new int[coins.length];
        for (int i = coins.length - 1; i >= 0; i--) {
            if (amount >= coins[i]) {
                result[i] = amount / coins[i]; // 核算当时面额的零钱数量
                amount %= coins[i]; // 更新剩下金额
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] coins = {1, 2, 5, 10, 20, 50};
        int amount = 123;
        int[] minCoins = findMinCoins(coins, amount);
        System.out.println("找零 " + amount + " 元的最少硬币数量为:");
        for (int i = coins.length - 1; i >= 0; i--) {
            if (minCoins[i] > 0) {
                System.out.println(coins[i] + " 元硬币：" + minCoins[i] + " 枚");
            }
        }
    }
}

运转成果：

找零 123 元的最少硬币数量为:
50 元硬币：2 枚
20 元硬币：1 枚
2 元硬币：1 枚
1 元硬币：1 枚

在上述示例中，咱们界说了 findMinCoins 办法，承受一个零钱面额数组 coins 和一个金额 amount 作为参数，运用贪心算法找零。首要对零钱面额进行升序排序，然后从最大面额开端，核算当时面额的零钱数量，并更新剩下金额。最后回来每个面额的零钱数量。

在 main 办法中，咱们创立了一个零钱面额数组 coins 和一个金额 amount，调用 findMinCoins 办法进行找零，并输出成果。

6 普里姆算法

普里姆算法（Prim’s Algorithm）是一种用于求解最小生成树的算法。给定一个连通加权无向图，普里姆算法经过逐渐挑选边，将极点逐渐参加生成树中，直到生成树包括图中的一切极点。

以下是普里姆算法的完结过程：

初始化：挑选一个开端极点作为生成树的根节点，将其参加生成树调集，并将其一切邻接边参加候选边调集。
挑选边：从候选边调集中挑选一条最小权重的边，将其参加生成树调集。
更新候选边：将新参加的极点的一切邻接边中，权重小于已有边的边参加候选边调集。
重复过程2和过程3，直到生成树包括图中的一切极点。

下面是一个运用普里姆算法构建最小生成树的示例代码：

import java.util.*;
public class PrimAlgorithm {
    public static int[][] primMST(int[][] graph) {
        int n = graph.length; // 图的极点数量
        boolean[] visited = new boolean[n]; // 记载极点是否已被拜访
        int[][] mst = new int[n][n]; // 存储最小生成树的邻接矩阵
        for (int i = 0; i < n; i++) {
            Arrays.fill(mst[i], Integer.MAX_VALUE);
        }
        int start = 0; // 开端极点
        visited[start] = true;
        PriorityQueue<Edge> pq = new PriorityQueue<>(); // 候选边调集
        addEdges(graph, pq, start);
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int u = edge.u;
            int v = edge.v;
            int weight = edge.weight;
            if (visited[v]) {
                continue; // 跳过已拜访的极点
            }
            visited[v] = true;
            mst[u][v] = weight;
            mst[v][u] = weight;
            addEdges(graph, pq, v);
        }
        return mst;
    }
    private static void addEdges(int[][] graph, PriorityQueue<Edge> pq, int v) {
        for (int u = 0; u < graph.length; u++) {
            int weight = graph[u][v];
            if (weight > 0) {
                pq.offer(new Edge(u, v, weight));
            }
        }
    }
    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 0, 6, 0},
            {2, 0, 3, 8, 5},
            {0, 3, 0, 0, 7},
            {6, 8, 0, 0, 9},
            {0, 5, 7, 9, 0}
        };
        int[][] mst = primMST(graph);
        System.out.println("最小生成树的邻接矩阵为:");
        for (int i = 0; i < mst.length; i++) {
            for (int j = 0; j < mst[i].length; j++) {
                System.out.print(mst[i][j] + " ");
            }
            System.out.println();
        }
    }
}
class Edge implements Comparable<Edge> {
    int u; // 边的一个极点
    int v; // 边的另一个极点
    int weight; // 边的权重
    public Edge(int u, int v, int weight) {
        this.u = u;
        this.v = v;
        this.weight = weight;
    }
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

运转成果：

最小生成树的邻接矩阵为:
0 2 0 6 0 
2 0 3 0 5 
0 3 0 0 7 
6 0 0 0 9 
0 5 7 9 0

在上述示例中，咱们界说了 primMST 办法，承受一个邻接矩阵表明的图作为参数，运用普里姆算法构建最小生成树。

在 primMST 办法中，咱们运用一个布尔数组 visited 记载极点是否已被拜访，一个二维数组 mst 存储最小生成树的邻接矩阵。经过运用优先行列 pq 来存储候选边调集。咱们挑选开端极点，并将其符号为已拜访。然后，将开端极点的一切邻接边参加候选边调集。在每一步迭代中，从候选边调集中挑选一条权重最小的边，将其参加最小生成树，并将新参加极点的邻接边参加候选边调集。重复此过程，直到最小生成树包括图中的一切极点。

在 main 办法中，咱们界说了一个邻接矩阵 graph，调用 primMST 办法构建最小生成树，并输出成果。

需求留意的是，上述示例中的 Edge 类用于表明边的信息，并完结了 Comparable 接口，以便优先行列能够依照边的权重进行排序。

7 克鲁斯卡尔算法

克鲁斯卡尔算法（Kruskal’s Algorithm）是一种用于求解最小生成树的算法。给定一个连通加权无向图，克鲁斯卡尔算法经过按边权重从小到大的次序逐渐挑选边，将极点逐渐参加生成树中，直到生成树包括图中的一切极点。

以下是克鲁斯卡尔算法的完结过程：

初始化：将每个极点看作一个独立的调集。
排序边：按边的权重从小到大进行排序。
挑选边：从排序后的边调集中挑选一条边。
查看环路：查看挑选的边是否会发生环路，假如不会，则将该边参加最小生成树。
重复过程3和过程4，直到生成树包括图中的一切极点。

下面是一个运用克鲁斯卡尔算法构建最小生成树的示例代码：

import java.util.*;
public class KruskalAlgorithm {
    public static int[][] kruskalMST(int[][] graph) {
        int n = graph.length; // 图的极点数量
        PriorityQueue<Edge> pq = new PriorityQueue<>(); // 存储边的优先行列
        // 将图中的边参加优先行列
        for (int u = 0; u < n; u++) {
            for (int v = u + 1; v < n; v++) {
                int weight = graph[u][v];
                if (weight > 0) {
                    pq.offer(new Edge(u, v, weight));
                }
            }
        }
        DisjointSet ds = new DisjointSet(n); // 并查集，用于查看环路
        int[][] mst = new int[n][n]; // 存储最小生成树的邻接矩阵
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int u = edge.u;
            int v = edge.v;
            int weight = edge.weight;
            if (ds.find(u) != ds.find(v)) {
                ds.union(u, v); // 兼并两个调集
                mst[u][v] = weight;
                mst[v][u] = weight;
            }
        }
        return mst;
    }
    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 0, 6, 0},
            {2, 0, 3, 8, 5},
            {0, 3, 0, 0, 7},
            {6, 8, 0, 0, 9},
            {0, 5, 7, 9, 0}
        };
        int[][] mst = kruskalMST(graph);
        System.out.println("最小生成树的邻接矩阵为:");
        for (int i = 0; i < mst.length; i++) {
            for (int j = 0; j < mst[i].length; j++) {
                System.out.print(mst[i][j] + " ");
            }
            System.out.println();
        }
    }
}
class Edge implements Comparable<Edge> {
    int u; // 边的一个极点
    int v; // 边的另一个极点
    int weight; // 边的权重
    public Edge(int u, int v, int weight) {
        this.u = u;
        this.v = v;
        this.weight = weight;
    }
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}
class DisjointSet {
    int[] parent;
    public DisjointSet(int size) {
        parent = new int[size];
        Arrays.fill(parent, -1);
    }
    public int find(int x) {
        if (parent[x] < 0) {
            return x;
        } else {
            parent[x] = find(parent[x]); // 途径紧缩
            return parent[x];
        }
    }
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (parent[rootX] <= parent[rootY]) {
            parent[rootX] += parent[rootY];
            parent[rootY] = rootX;
        } else {
            parent[rootY] += parent[rootX];
            parent[rootX] = rootY;
        }
    }
}

运转成果：

最小生成树的邻接矩阵为:
0 2 0 0 0 
2 0 3 0 5 
0 3 0 0 7 
0 0 0 0 9 
0 5 7 9 0

在上述示例中，咱们界说了 kruskalMST 办法，承受一个邻接矩阵表明的图作为参数，运用克鲁斯卡尔算法构建最小生成树。

在 kruskalMST 办法中，咱们运用一个优先行列 pq 存储边，依照边的权重从小到大进行排序。然后，运用并查集 ds 来查看边是否会发生环路。咱们遍历优先行列中的边，假如边的两个极点不在同一个调集中，则将它们兼并，并将边参加最小生成树。终究，回来最小生成树的邻接矩阵。

在 main 办法中，咱们界说了一个邻接矩阵 graph，调用 kruskalMST 办法构建最小生成树，并输出成果。

需求留意的是，上述示例中的 Edge 类用于表明边的信息，并完结了 Comparable 接口，以便优先行列能够依照边的权重进行排序。DisjointSet 类完结了并查集数据结构，用于查看边是否会发生环路。

8 迪杰斯特拉算法

迪杰斯特拉算法（Dijkstra’s Algorithm）是一种用于求解单源最短途径的算法。给定一个加权有向图和开端极点，迪杰斯特拉算法能够找到从开端极点到其他一切极点的最短途径。

以下是迪杰斯特拉算法的完结过程：

初始化间隔：将开端极点的间隔设为0，其他极点的间隔设为无穷大。
创立一个优先行列，用于存储极点及其间隔，开端时将开端极点参加行列。
循环履行以下过程，直到优先行列为空：
- 从优先行列中取出间隔最小的极点。
- 遍历该极点的一切邻接极点，核算经过当时极点抵达邻接极点的间隔，假如该间隔小于邻接极点的当时间隔，则更新邻接极点的间隔。
- 假如邻接极点不在优先行列中，则将其参加行列。
履行完循环后，一切极点的最短途径现已核算完结。

下面是一个运用迪杰斯特拉算法求解最短途径的示例代码：

import java.util.*;
public class DijkstraAlgorithm {
    public static int[] dijkstra(int[][] graph, int source) {
        int n = graph.length; // 图的极点数量
        int[] dist = new int[n]; // 存储开端极点到其他极点的最短间隔
        Arrays.fill(dist, Integer.MAX_VALUE); // 初始化间隔为无穷大
        dist[source] = 0; // 开端极点到自身的间隔为0
        PriorityQueue<Vertex> pq = new PriorityQueue<>(); // 优先行列，按间隔从小到大排序
        pq.offer(new Vertex(source, 0));
        while (!pq.isEmpty()) {
            Vertex vertex = pq.poll();
            int u = vertex.index;
            for (int v = 0; v < n; v++) {
                int weight = graph[u][v];
                if (weight > 0) {
                    int newDist = dist[u] + weight;
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        pq.offer(new Vertex(v, newDist));
                    }
                }
            }
        }
        return dist;
    }
    public static void main(String[] args) {
        int[][] graph = {
            {0, 4, 0, 0, 0, 0, 0, 8, 0},
            {4, 0, 8, 0, 0, 0, 0, 11, 0},
            {0, 8, 0, 7, 0, 4, 0, 0, 2},
            {0, 0, 7, 0, 9, 14, 0, 0, 0},
            {0, 0, 0, 9, 0, 10, 0, 0, 0},
            {0, 0, 4, 14, 10, 0, 2, 0, 0},
            {0, 0, 0, 0, 0, 2, 0, 1, 6},
            {8, 11, 0, 0, 0, 0, 1, 0, 7},
            {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };
        int source = 0; // 开端极点
        int[] shortestPaths = dijkstra(graph, source);
        System.out.println("从极点 " + source + " 到其他极点的最短间隔为:");
        for (int i = 0; i < shortestPaths.length; i++) {
            System.out.println("到极点 " + i + " 的间隔为: " + shortestPaths[i]);
        }
    }
}
class Vertex implements Comparable<Vertex> {
    int index; // 极点索引
    int distance; // 间隔
    public Vertex(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }
    @Override
    public int compareTo(Vertex other) {
        return Integer.compare(this.distance, other.distance);
    }
}

运转成果：

从极点 0 到其他极点的最短间隔为:
到极点 0 的间隔为: 0
到极点 1 的间隔为: 4
到极点 2 的间隔为: 12
到极点 3 的间隔为: 19
到极点 4 的间隔为: 21
到极点 5 的间隔为: 11
到极点 6 的间隔为: 9
到极点 7 的间隔为: 8
到极点 8 的间隔为: 14

在上述示例中，咱们界说了 dijkstra 办法，承受一个邻接矩阵表明的图和开端极点作为参数，运用迪杰斯特拉算法核算最短途径。

在 dijkstra 办法中，咱们首要初始化间隔数组 dist，将开端极点到其他极点的间隔设为无穷大。然后，创立一个优先行列 pq，用于存储极点及其间隔。咱们将开端极点参加优先行列，并将其间隔设为0。在循环中，从优先行列中取出间隔最小的极点，遍历该极点的一切邻接极点，核算经过当时极点抵达邻接极点的间隔，假如该间隔小于邻接极点的当时间隔，则更新邻接极点的间隔，并将其参加优先行列。终究，回来最短间隔数组。

在 main 办法中，咱们界说了一个邻接矩阵 graph 和一个开端极点 source，调用 dijkstra 办法核算最短途径，并输出成果。

需求留意的是，上述示例中的 Vertex 类用于表明极点的信息，并完结了 Comparable 接口，以便优先行列能够依照极点的间隔进行排序。

9 弗洛伊德算法

弗洛伊德算法（Floyd-Warshall Algorithm）是一种用于求解一切极点对之间最短途径的算法。给定一个加权有向图，弗洛伊德算法能够核算出图中恣意两个极点之间的最短途径及其间隔。

以下是弗洛伊德算法的完结过程：

初始化间隔矩阵：创立一个二维数组 dist，用于存储恣意两个极点之间的最短途径间隔。假如两个极点之间存在边，则将其间隔存入 dist，不然将其间隔设为无穷大。
三重循环更新间隔：运用三重循环遍历一切极点对 (i, j, k)，其中 k 是中心极点的索引。关于每一对 (i, j)，比较经过中心极点 k 的途径间隔和直接途径间隔，假如经过中心极点 k 的途径间隔更短，则更新 dist[i][j] 的值。
循环完毕后，dist 数组中存储了恣意两个极点之间的最短途径间隔。

下面是一个运用弗洛伊德算法求解最短途径的示例代码：

import java.util.Arrays;
public class FloydWarshallAlgorithm {
    public static int[][] floydWarshall(int[][] graph) {
        int n = graph.length; // 图的极点数量
        int[][] dist = new int[n][n]; // 存储最短途径间隔
        // 初始化间隔矩阵
        for (int i = 0; i < n; i++) {
            System.arraycopy(graph[i], 0, dist[i], 0, n);
        }
        // 三重循环更新间隔
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        return dist;
    }
    public static void main(String[] args) {
        int[][] graph = {
            {0, 4, 6, Integer.MAX_VALUE, Integer.MAX_VALUE},
            {4, 0, 3, 7, Integer.MAX_VALUE},
            {6, 3, 0, 8, 2},
            {Integer.MAX_VALUE, 7, 8, 0, 5},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, 2, 5, 0}
        };
        int[][] shortestPaths = floydWarshall(graph);
        System.out.println("恣意两个极点之间的最短途径间隔为:");
        for (int i = 0; i < shortestPaths.length; i++) {
            for (int j = 0; j < shortestPaths[i].length; j++) {
                System.out.print(shortestPaths[i][j] + " ");
            }
            System.out.println();
        }
    }
}

运转成果：

恣意两个极点之间的最短途径间隔为:
0 4 6 10 8 
4 0 3 7 9 
6 3 0 8 2 
12 7 5 0 5 
8 11 2 5 0

在上述示例中，咱们界说了 floydWarshall 办法，承受一个邻接矩阵表明的图作为参数，运用弗洛伊德算法核算恣意两个极点之间的最短途径。

在 floydWarshall 办法中，咱们首要初始化间隔矩阵 dist，将其赋值为图中的间隔数组。然后，运用三重循环遍历一切极点对 (i, j, k)，并依据中心极点 k 更新极点对 (i, j) 的最短途径间隔。终究，回来 dist 数组，其中存储了恣意两个极点之间的最短途径间隔。

在 main 办法中，咱们界说了一个邻接矩阵 graph，调用 floydWarshall 办法核算最短途径，并输出成果。

需求留意的是，上述示例中运用了 Integer.MAX_VALUE 表明两个极点之间不存在直接边的状况。

10 马踏棋盘算法

马踏棋盘算法（Knight’s Tour Algorithm）是一种用于处理马在棋盘上走遍一切格子的问题的算法。在标准的国际象棋棋盘上，给定一个开端方位，马踏棋盘算法经过合理的移动规矩，测验找到一条途径，使得马能够刚好踏遍棋盘上的一切格子。

以下是马踏棋盘算法的完结过程：

创立棋盘：创立一个二维数组来表明棋盘，初始化一切格子为未拜访状况。
设定开端方位：挑选一个开端方位，将其符号为已拜访。
递归回溯：从开端方位开端，依照马的规矩进行移动，递归地测验每一种或许的移动途径，直到找到一条完好的途径或许无法移动为止。
移动规矩：马在棋盘上的移动规矩是以当时方位为基准，依照固定的相对坐标进行移动。马能够向上、下、左、右、斜向上、斜向下等8个方向移动。
判别边界和拜访状况：在每一步移动时，需求判别马的下一个方位是否在棋盘范围内，并且没有被拜访过。
符号途径和回溯：每次移动时，将当时方位符号为已拜访，并递归测验下一步移动。假如找到一条完好的途径，则算法完毕；假如无法移动到下一个方位，则回溯到上一步，取消当时方位的符号，并测验其他或许的移动途径。

下面是一个运用马踏棋盘算法求解问题的示例代码：

public class KnightsTourAlgorithm {
    private static final int BOARD_SIZE = 8; // 棋盘大小
    private static final int[] ROW_OFFSETS = {-2, -1, 1, 2, 2, 1, -1, -2}; // 行的相对偏移量
    private static final int[] COL_OFFSETS = {1, 2, 2, 1, -1, -2, -2, -1}; // 列的相对偏移量
    public static void knightsTour(int[][] board, int row, int col, int move) {
        board[row][col] = move; // 符号当时方位为已拜访
        if (move == BOARD_SIZE * BOARD_SIZE) {
            printBoard(board); // 找到一条完好途径，打印棋盘
        } else {
            for (int i = 0; i < 8; i++) {
                int nextRow = row + ROW_OFFSETS[i];
                int nextCol = col + COL_OFFSETS[i];
                if (isValidMove(board, nextRow, nextCol)) {
                    knightsTour(board, nextRow, nextCol, move + 1);
                }
            }
        }
        board[row][col] = 0; // 取消当时方位的符号，回溯
    }
    public static boolean isValidMove(int[][] board, int row, int col) {
        return row >= 0 && row < BOARD_SIZE && col >= 0 && col < BOARD_SIZE && board[row][col] == 0;
    }
    public static void printBoard(int[][] board) {
        for (int[] row : board) {
            for (int cell : row) {
                System.out.printf("%2d ", cell);
            }
            System.out.println();
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[][] board = new int[BOARD_SIZE][BOARD_SIZE];
        int startRow = 0; // 开端方位的行坐标
        int startCol = 0; // 开端方位的列坐标
        int move = 1; // 当时移动步数
        knightsTour(board, startRow, startCol, move);
    }
}

运转成果中会打印出一切的完好途径。由于马踏棋盘问题存在多个解，因此输出成果会有多种或许性。在上述示例中，咱们界说了 knightsTour 办法来完结马踏棋盘算法。

在 knightsTour 办法中，咱们首要符号当时方位为已拜访，并判别是否现已找到一条完好的途径。假如没有找到完好途径，咱们遍历8个方向的移动或许性，并递归测验每一种或许。假如某个移动途径能够继续向下递归，则继续履行递归调用。假如无法移动到下一个方位，则回溯到上一步，取消当时方位的符号，并测验其他或许的移动途径。

在 main 办法中，咱们创立了一个棋盘数组 board，挑选一个开端方位，然后调用 knightsTour 办法开端寻找马踏棋盘的解。

数据结构与算法：10种常见算法

前言

数据结构与算法文章列表

目录

1 二分查找算法

2 分治算法

3 动态规划算法

4 KMP算法

5 贪心算法

6 普里姆算法

7 克鲁斯卡尔算法

8 迪杰斯特拉算法

9 弗洛伊德算法

10 马踏棋盘算法

作者信息

推广

数据结构与算法：10种常见算法

前言

数据结构与算法文章列表

目录

1 二分查找算法

2 分治算法

3 动态规划算法

4 KMP算法

5 贪心算法

6 普里姆算法

7 克鲁斯卡尔算法

8 迪杰斯特拉算法

9 弗洛伊德算法

10 马踏棋盘算法

相关文章

APP常用跨端技术栈深入分析 | 京东云技术团队

ChatGPT编程秀-5： 测试驱动ChatGPT编程

iOS中为什么会有这么多锁呢？

Android稳定性：Looper兜底框架实现线上容灾（二）

作者信息

推广

ChatGPT编程秀-5：测试驱动ChatGPT编程