XMD

无语

算法基础17：常用的10种算法

发表于 更新于 分类于 ，
本文字数： 25k 阅读时长 ≈ 23 分钟

二分查找算法

  1. 非递归

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class BinarySearchNoRecur {

    public static void main(String[] args) {
        int[] arr = {1, 3, 8, 10, 11, 67, 100};
        int index = binarySearch(arr, 11);
        System.out.println(index);
    }

    /**
     * 二分查找的非递归实现
     *
     * @param arr    待查找的数组
     * @param target 需要查找的数
     * @return 返回对应下标，-1表示没有找到
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

分治算法

汉诺塔问题

汉诺塔问题代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class HanoiTower {

    public static void main(String[] args) {
        hanoiTower(5, 'A', 'B', 'C');

    }

    public static void hanoiTower(int num, char a, char b, char c) {
        //如果只有一个盘
        if (num == 1) {
            System.out.println("第1个盘从" + a + "->" + c);
        } else {
            //如果我们有>=2情况，我们总是可以看做是两个盘1.最下边的一个盘2，上面的所有盘
            //1. 先把最上面的所有盘A-> B,移动过程使用到C
            hanoiTower(num - 1, a, c, b);
            //2. 把最小面的盘 A->C
            System.out.println("第" + num + "个盘从" + a + "->" + c);
            //3. 把B的所有盘从B——>C 移动成功使用A
            hanoiTower(num - 1, b, a, c);
        }
    }
}

动态规划算法

介绍

背包问题

背包问题代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class knapsackProblem {
    public static void main(String[] args) {
        //物品重量
        int[] w = {1, 4, 3, 5, 2};
        //物品价值（物品的价值这里val[i]就是前面讲的v[i]）
        int[] val = {1500, 3000, 2000, 4000, 3500};
        //背包容量
        int m = 5;
        //物品个数
        int n = val.length;

        //w[1][j]表示在前i个物品中能够装入容量为j的背包中的最大价值
        int[][] v = new int[n + 1][m + 1];
        //为了记录放入商品的情况，我们定一个二维数组
        int[][] path = new int[n + 1][m + 1];
        //初始化第一行第一列，这里在本程序中可以不去处理，因为默认为0
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0;
        }
        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0;
        }

        //根据更是规划处理
        for (int i = 1; i < v.length; i++) {//不处理第一行1是从1开始的
            for (int j = 1; j < v[0].length; j++) {//不处理第一列，j是从1开始的
                if (w[i - 1] > j) {//因为我们程序i是从1开始的，因此原来公式中的w[i]修改成w[i-1]
                    v[i][j] = v[i - 1][j];
                } else {
                    //因为我们的1从1开始的，因此公式需要调整如下
//                    v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                    if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        path[i][j] = 1;
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }

        }


        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print(v[i][j] + "   ");
            }
            System.out.println();
        }

//        for (int i = 0; i < path.length; i++) {
//            for (int j = 0; j < path[i].length; j++) {
//                if (path[i][j] == 1) {
//                    System.out.printf("第%d个商品放入到背包", i);
//                }
//                System.out.println();
//            }
//
//        }

        int i = path.length - 1;
        int j = path[0].length - 1;
        while (1 > 0 && j > 0) {
            if (path[i][j] == 1) {
                System.out.printf("第%d个商品放入到背包", i);
                System.out.println();
                j -= w[i - 1];
            }
            i--;
        }
    }
}

KMP 算法

暴力算法 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class ViolentMatch {
    public static void main(String[] args) {
        String str1 = "付货款都是垃圾和家里房东还是垃圾和家圾和家里";
        String str2 = "是垃圾和家圾";
        final int match = violentMatch(str1, str2);
        System.out.println(match);
    }

    /**
     * 暴力匹配算法
     *
     * @param str1
     * @param str2
     * @return
     */
    public static int violentMatch(String str1, String str2) {
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        int s1len = s1.length;
        int s2len = s2.length;

        int i = 0;
        int j = 0;

        while (i < s1len && j < s2len) {
            if (s1[i] == s2[j]) {
                i++;
                j++;
            } else {
                i = i - (j - 1);
                j = 0;
            }
        }
        if (j == s2len) {
            return i - j;
        } else {
            return -1;
        }
    }
}

KMP 算法介绍

KMP 算法代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * KMP算法
 *
 * @author：XMD
 * @date: 17.10.22
 */
public class KmpAlgorithm {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int[] ints = kmpNext(str2);

        final int search = kmpSearch(str1, str2, ints);
        System.out.println(search);
    }


    /**
     * KMP算法
     *
     * @param str1 源数据
     * @param str2 子数据
     * @param next 部分匹配表，是子串对应的部分匹配表
     * @return 如果是-1就是没有匹配到，否则返回第一个匹配的位置
     */
    public static int kmpSearch(String str1, String str2, int[] next) {
        for (int i = 0, j = 0; i < str1.length(); i++) {
            //需要处理str1,charAt(i)！=str2,charAt(j),去调整j的大小
            // KMP算法核心点
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j - 1];
            }
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

    /**
     * 获取到一个字符串（子串）的部分匹配值表
     *
     * @param dest
     * @return
     */
    public static int[] kmpNext(String dest) {
        //创建一个neXt数组保存部分匹配值
        int[] next = new int[dest.length()];
        ///如果字符串是长度为1部分匹配值就是0
        next[0] = 0;
        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) 成立时退出
            //这是kmp算法的核心点
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }

            //当dest.charAt(i)== dest.charAt(j)满足时，部分匹配值就+1
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

贪婪（贪心）算法

案例

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 * 贪婪算法
 *
 * @author：XMD
 * @date: 17.10.22
 */
public class AreedyAlgorithm {
    public static void main(String[] args) {
        Map<String, HashSet<String>> broadcasts = new HashMap<>();
        HashSet<String> hashSet1 = new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");

        HashSet<String> hashSet2 = new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");

        HashSet<String> hashSet3 = new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");

        HashSet<String> hashSet4 = new HashSet<>();
        hashSet4.add("上海");
        hashSet4.add("天津");

        HashSet<String> hashSet5 = new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");

        broadcasts.put("K1", hashSet1);
        broadcasts.put("K2", hashSet2);
        broadcasts.put("K3", hashSet3);
        broadcasts.put("K4", hashSet4);
        broadcasts.put("K5", hashSet5);

        //存放所有的地区
        HashSet<String> allAdress = new HashSet<>();
        allAdress.addAll(hashSet1);
        allAdress.addAll(hashSet2);
        allAdress.addAll(hashSet3);
        allAdress.addAll(hashSet4);
        allAdress.addAll(hashSet5);

        //创建list，存放选择的电台集合
        List<String> selects = new ArrayList<>();
        //定义一个临时的集合，在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
        HashSet<String> tempSet = new HashSet<>();
        //定义给maxKey,保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
        String maxKey;
        // 如果naxKey不为nul1,则会加入到selects
        //如果allAreas不为0，则表示还没有覆盖到所有的地区
        while (allAdress.size() != 0) {
            maxKey = null;
            for (String key : broadcasts.keySet()) {
                tempSet.clear();
                HashSet<String> areas = broadcasts.get(key);
                tempSet.addAll(areas);
                //求出tempSet和allAreas集合的交集，交集会赋给tempSet
                tempSet.retainAll(allAdress);
                //如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多
                //就需要重置maxKey 体现出贪心算法的特点，每次都选择最优的
                //broadcasts.get(maxKey).size()
                if (tempSet.size() > 0 &&
                        (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
                    maxKey = key;
                }
            }
            //maxKey!=null,就应该将maxKey加入selects
            if (maxKey != null) {
                selects.add(maxKey);
                //将maxKey指向的广播电台覆盖的地区，从allArees去掉
                allAdress.removeAll(broadcasts.get(maxKey));
            }

        }
        System.out.println("结果：" + selects);
    }
}

普里姆算法

正确的思路，就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少

普里姆算法介绍

  1. 普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图

  2. 普利姆的算法如下：

    1. 设G=(N,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合

    2. 若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited[u]=1

    3. 若集合U中顶点ui与集合V-U中的顶点v之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边(ui,vj)加入集合D中，标记visited[vj]=1

    4. 重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边

    5. 提示：单独看步骤很难理解，我们通过代码来讲解，比较好理解.

代码实现（修路问题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
public class PrimAlgorithm {
    public static void main(String[] args) {
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int verxs = data.length;
        //10000表示两点不连通
        final int[][] weight = {
                {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 = new MGraph(verxs);
        MinTree minTree = new MinTree();
        minTree.createGraph(mGraph, verxs, data, weight);
        minTree.showGraph(mGraph);


        minTree.prim(mGraph, 0);
    }
}

//创建最小生成树->村庄的图
class MinTree {
    /**
     * 创建图的邻接矩阵
     *
     * @param graph  图对象
     * @param verxs  图对应的顶点个数
     * @param data   图的各个顶点的值
     * @param weight 图的邻接矩阵
     */
    public void createGraph(MGraph graph, int verxs, char[] data, int[][] weight) {
        int i, j;
        for (i = 0; i < verxs; i++) {
            graph.data[i] = data[i];
            for (j = 0; j < verxs; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }


    /**
     * 显式图的邻接矩阵
     *
     * @param graph
     */
    public void showGraph(MGraph graph) {
        for (int[] link : graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * 编写prim算法，得到最小生成树
     *
     * @param graph
     * @param v     表示从图的第几个顶点开始生成'A'->0'B'->1,··
     */
    public void prim(MGraph graph, int v) {
        int[] visited = new int[graph.verxs];
        //把当前这个结点标记为已访问
        visited[v] = 1;
        //h1和h2记录两个顶点的下标
        int h1 = -1;
        int h2 = -1;
        //将minWeight初始成一个大数，后面在遍历过程中，会被替换
        int minWeight = 10000;
        //因为有graph,verxs顶点，普利姆算法结束后，有graph.verxs-l边
        for (int k = 1; k < graph.verxs; k++) {
            //确定每一次生成的子图和哪个节点的距离最近
            //节点表示被访问的结点
            for (int i = 0; i < graph.verxs; i++) {
                //j表示还没有被访问过的节点
                for (int j = 0; j < graph.verxs; j++) {
                    if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
                        //寻找已经访问过的结点和未访问过的结点间的权值最小的边
                        minWeight = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            //找到一条最小的边
            System.out.println("边" + graph.data[h1] + "," + graph.data[h2] + "权值：" + minWeight);
            //将当前这个结点标记为已经访问
            visited[h2] = 1;
            minWeight = 10000;
        }
    }
}

class MGraph {
    //表示图的节点个数
    int verxs;
    //存放结点数据
    char[] data;
    //存放边，就是我们的邻接矩阵
    int[][] weight;

    public MGraph(int verxs) {
        this.verxs = verxs;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }
}

克鲁斯卡尔算法

介绍

  1. 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
  2. 基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路
  3. 具体做法：首先构造一个只含个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止

图解说明

以城市公交站问题来图解说明克鲁斯卡尔算法的原理和步骤：

克鲁斯卡尔算法分析
根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：
问题一对图的所有边按照权值大小进行排序。
问题二将边添加到最小生成树中时，怎么样判断是否形成了回路。

问题一很好解决，采用排序算法进行排序即可。
问题二，处理方式是：记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。

如何判断是否构成回路

公交站问题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
import java.util.Arrays;

/**
 * 克鲁斯卡尔算法
 *
 * @author：XMD
 * @date: 18.10.22
 */
public class KruskalCase {
    //两个顶点不能连通
    private static final int INF = Integer.MAX_VALUE;
    //顶点数组
    private final char[] vertexs;
    //邻接矩阵
    private final int[][] matrix;
    //边的个数
    private int edgeNum;

    public KruskalCase(char[] vertexs, int[][] matrix) {
        int vlen = vertexs.length;
        //初始化顶点
        this.vertexs = new char[vlen];
        for (int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexs[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];
            }
        }
        //统计边
        for (int i = 0; i < vlen; i++) {
            for (int j = i + 1; j < vlen; j++) {
                if (this.matrix[i][j] != INF) {
                    edgeNum++;
                }
            }
        }
    }

    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

        int[][] matrix = {
                {0, 12, INF, INF, INF, 16, 14},
                {12, 0, 10, INF, INF, 7, INF},
                {INF, 10, 0, 3, 5, 6, INF},
                {INF, INF, 3, 0, 4, INF, INF},
                {INF, INF, 5, 4, 0, 2, 8},
                {16, 7, 6, INF, 2, 0, 9},
                {14, INF, INF, INF, 8, 9, 0}};

        KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
//        kruskalCase.print();

//        final EData[] edges = kruskalCase.getEdges();
//        System.out.println("排序前" + Arrays.toString(edges));
//        kruskalCase.sortEdges(edges);
//        System.out.println("排序后" + Arrays.toString(edges));

        kruskalCase.print();
        kruskalCase.kruskal();
    }

    public void kruskal() {
        //表示最后结果数组的索引
        int index = 0;
        //用于保存已有最小生成树中的每个顶点在最小生成树中的终点
        int[] ends = new int[edgeNum];
        //创建结果数组，保存最后的最小生成树
        EData[] rets = new EData[edgeNum];

        //获取图中所有边的几个
        EData[] edges = getEdges();
        System.out.println("图的边的集合：" + Arrays.toString(edges));


        //按照边的权值排序
        sortEdges(edges);

        //遍历 将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入rts,否则不能加入
        for (int i = 0; i < edgeNum; i++) {
            //获取到第i条边的第一个顶点（起点）
            int p1 = getPosition(edges[i].start);
            //获取到第i条边的第2个顶点
            int p2 = getPosition(edges[i].end);

            //获取p1这个顶点在已有最小生成树中的终点
            int m = getEnd(ends, p1);
            //获取2这个顶点在已有最小生成树中的终点
            int n = getEnd(ends, p2);
            //是否构成回路
            if (m != n) {
                ends[m] = n;
                rets[index++] = edges[i];
            }
        }

        //统计并打印最小生成树
        System.out.println("最小生成树：");
        for (int i = 0; i < index; i++) {
            System.out.println(rets[i]);
        }


    }

    public void print() {
        System.out.println("邻接矩阵：\n");
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%12d\t", matrix[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 对边进行排序处理，冒泡排序
     *
     * @param edges
     */
    private void sortEdges(EData[] edges) {
        for (int i = 0; i < edges.length - 1; i++) {
            for (int j = 0; j < edges.length - 1 - i; j++) {
                if (edges[j].weight > edges[j + 1].weight) {
                    EData temp = edges[j];
                    edges[j] = edges[j + 1];
                    edges[j + 1] = temp;
                }
            }
        }
    }

    /**
     * @param ch
     * @return 返回ch顶点对应的下标，如果找不到，返回-1
     */
    private int getPosition(char ch) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == ch) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 功能：获取图中边，放到EData[]数组中，后面我们需要遍历该数组
     *
     * @return
     */
    private EData[] getEdges() {
        int index = 0;
        EData[] edges = new EData[edgeNum];
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i + 1; j < vertexs.length; j++) {
                if (matrix[i][j] != INF) {
                    edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
                }
            }
        }
        return edges;
    }

    /**
     * 功能：获取下标为的顶点的终点,用于后面判断两个顶点的终点是否相同
     *
     * @param ends 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成
     * @param i    表示传入的顶点对应的下标
     * @return 返回的就是下标为的这个顶点对应的终点的下标
     */
    private int getEnd(int[] ends, int i) {
        while (ends[i] != 0) {
            i = ends[i];
        }
        return i;
    }

}

class EData {
    char start;
    char end;
    int weight;

    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "[" + start + "-" + end + "]:" + weight;
    }
}

迪杰斯特拉算法

应用场景：最短路径问题

  1. 战争时期，胜利乡有7个村庄(A,B,C,D,E,FG),现在有六个邮差，从G点出发，需要分别把邮件分别送到A,B,C,D,E,F六个村庄

  2. 各个村庄的距离用边线表示（权），比如A-B距离5公里

  3. 问：如何计算出G村庄到其它各个村庄的最短距离？

  4. 如果从其它点出发到各个点的最短距离又是多少？

    ​

迪杰斯特拉(Dijkstra)算法介绍

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展（广度优先搜索思想），直到扩展到终点为止。

迪杰斯特拉(Dijkstra)算法过程

设置出发顶点为v,顶点集合V{v1,v2,vi.},v到V中各顶点的距离构成距离集合Dis,Dis{d1,d2,di,…}，Dis集合记录着v到图中各顶点的距离（到自身可以看作0，v到vi距离心应为di)

  1. 从Dis中选择值最小的di并移出Dis集合，同时移出V集合中对应的顶点vi,此时的v到vi即为最短路径
  2. 更新Dis集合，更新规则为：比较v到V集合中顶点的距离值，与v通过vi到V集合中顶点的距离值，保留值较小的一个（同时也应该更新顶点的前驱节点为ⅵ，表明是通过ⅵ到达的)
  3. 重复执行两步骤，直到最短路径顶点为目标顶点即可结束

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
import java.util.Arrays;

/**
 * 迪杰斯特拉算法
 *
 * @author：XMD
 * @date: 18.10.22
 */
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 = new Graph(vertex, matrix);
        graph.showGraph();

        //0表示从A到各个顶点的最短距离
        //打印的结果 A(0) | B(5) | C(7) | D(12) | E(6) | F(8) | G(2) |  表示 A-A最短距离为0  A-B的最短距离为5  。。。。。
        graph.dsj(0);
        graph.showDjs();

    }
}


class Graph {
    //顶点数组
    private char[] vertex;
    //邻接矩阵
    private int[][] matrix;
    //已经访问的顶点的集合
    private VisitedVertex vv;

    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    public void showGraph() {
        for (int[] ints : matrix) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public void showDjs() {
        vv.show();
    }

    /**
     * 迪杰斯特拉算法实现
     *
     * @param index 表示出发顶点对应的下标
     */
    public void dsj(int index) {
        vv = new VisitedVertex(vertex.length, index);
        ////更新index顶点到周围顶点的距离和前驱顶点
        update(index);

        for (int j = 1; j < vertex.length; j++) {
            //选择并返回新的访问顶点
            index = vv.updateArr();
            //更新index顶点到周围顶点的距离和前驱顶点
            update(index);
        }
    }


    /**
     * //更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点，
     *
     * @param index
     */
    private void update(int index) {
        int len = 0;
        ///根据遍历我们的邻接矩阵的matrix[index]行
        for (int i = 0; i < matrix[index].length; i++) {
            //len含义是：出发顶点到index顶点的距离+从index顶点到j顶点的距离的和
            len = vv.getDis(index) + matrix[index][i];
            //如果j顶点没有被访问过，并且len小于出发顶点到j顶点的距离，就需要更新
            if (!vv.in(i) && len < vv.getDis(i)) {
                //更新j顶点的前驱为index顶点
                vv.updatePre(i, index);
                //更新出发顶点到顶点的距离
                vv.updateDis(i, len);
            }
        }
    }
}

/**
 * //已访问顶点集合
 */
class VisitedVertex {
    /**
     * 记录各个顶点是否访问过1表示访问过，0未访问，会动态更新
     */
    public int[] already_arr;
    /**
     * 每个下标对应的值为前一个顶点下标，会动态更新
     */
    public int[] pre_visited;
    /**
     * 记录出发顶点到其他所有顶点的距离，比如G为出发顶点，就会记录G到其它顶点的距离，会动态更新，求的最短距离就会存放到d1s
     */
    public int[] dis;

    /**
     * @param lenght 表示顶点的个数
     * @param index  出发顶点对应的下标，比如G顶点，下标就是6
     */
    public VisitedVertex(int lenght, int index) {
        this.already_arr = new int[lenght];
        this.pre_visited = new int[lenght];
        this.dis = new int[lenght];

        //初始化dis数组
        Arrays.fill(dis, 65535);
        //设置出发顶点被访问过
        this.already_arr[index] = 1;
        //设置出发顶点的访问距离为0
        this.dis[index] = 0;
    }

    /**
     * 功能：判断index顶点是否被访问过
     *
     * @param index
     * @return 如果访问过，就返回true,否则访问false
     */
    public boolean in(int index) {
        return already_arr[index] == 1;
    }

    /**
     * 功能：更新出发顶点到index顶点的距离
     *
     * @param index
     * @param len
     */
    public void updateDis(int index, int len) {
        dis[index] = len;
    }

    /**
     * 功能：更新pre这个顶点的前驱顶点为index顶点
     *
     * @param pre
     * @param index
     */
    public void updatePre(int pre, int index) {
        pre_visited[pre] = index;
    }

    /**
     * 功能：返回出发顶点到index顶点的距离
     *
     * @param index
     */
    public int getDis(int index) {
        return dis[index];
    }


    /**
     * //继续选择并返回新的访问顶点，比如这里的G完后，就是A点作为新的访问顶点（注意不是出发顶点）
     *
     * @return
     */
    public int updateArr() {
        int min = 65535, index = 0;
        for (int i = 0; i < already_arr.length; i++) {
            if (already_arr[i] == 0 && dis[i] < min) {
                min = dis[i];
                index = i;
            }
        }
        already_arr[index] = 1;
        return index;
    }

    /**
     * //即将三个数组的情况输出
     */
    public void show() {
        System.out.println("===========");
        for (int i : already_arr) {
            System.out.print(i + ">>");
        }
        System.out.println();
        System.out.println("===========");
        for (int i : pre_visited) {
            System.out.print(i + ">>");
        }
        System.out.println();
        System.out.println("===========");
        for (int di : dis) {
            System.out.print(di + ">>");
        }
        System.out.println();
        System.out.println("===========");
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int count = 0;
        for (int i : dis) {
            if (i != 65535) {
                System.out.print(vertex[count] + "(" + i + ") | ");
            } else {
                System.out.println("N  ");
            }
            count++;
        }
        System.out.println();
    }
}

弗洛伊德算法

弗洛伊德(Floyd)算法介绍

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import java.util.Arrays;

/**
 * 弗洛伊德算法
 *
 * @author：XMD
 * @date: 19.10.22
 */
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.length, matrix, vertex);
        graph.floyd();
        graph.show();

    }

}

class Graph {
    //顶点数组
    private char[] vertex;
    //保存，从各个顶点出发到其它顶点的距离，最后的结果，也是保留在该数组
    private int[][] dis;
    //保存到达目标顶点的前驱顶点
    private int[][] pre;

    /**
     * @param lenght 大小
     * @param matrix 邻接矩阵
     * @param vertex 顶点数
     */
    public Graph(int lenght, int[][] matrix, char[] vertex) {
        this.vertex = vertex;
        this.dis = matrix;
        this.pre = new int[lenght][lenght];
        for (int i = 0; i < lenght; i++) {
            Arrays.fill(pre[i], i);
        }
    }

    //显式pre数组和dis数组
    public void show() {
        for (int k = 0; k < dis.length; k++) {
            //先将pre数组输出的一行
            for (int i = 0; i < dis.length; i++) {
                System.out.print(pre[k][i] + " ");
            }
            System.out.println();
            //dis数组输出的一行
            for (int i = 0; i < dis.length; i++) {
                System.out.print(vertex[k] + "到" + vertex[i] + "最短路径：" + dis[k][i] + " / ");
            }
            System.out.println();
        }
    }


    public void floyd() {
        //保存距离
        int len = 0;
        //对中间顶点遍历，k就是中间顶点的下标[A,B,C,D,E,F,G]
        for (int k = 0; k < dis.length; k++) {
            //从i顶点开始出发[A,B,C,D,E,F,G]
            for (int i = 0; i < dis.length; i++) {
                for (int j = 0; j < dis.length; j++) {
                    //求出从i顶点出发，经过k中间顶点，到达j顶点距离
                    len = dis[i][k] + dis[k][j];
                    if (len < dis[k][j]) {
                        dis[i][j] = len;
                        //更新前驱顶点
                        pre[i][j] = pre[k][j];
                    }
                }
            }
        }
    }


}

马踏棋盘算法

骑士周游问题

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package com.algorithm.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 马踏棋盘
 *
 * @author：XMD
 * @date: 19.10.22
 */
public class HorseCheckerboard {
    //棋盘列
    private static int X;
    //棋盘行
    private static int Y;
    //标记棋盘的各个位置是否被访问过
    private static boolean visited[];
    //标记是否棋盘的所有位置都被访问
    private static boolean finished;

    public static void main(String[] args) {
        X = 8;
        Y = 8;
        int row = 1;
        int column = 1;
        int[][] chessborad = new int[X][Y];
        visited = new boolean[X * Y];
        final long start = System.currentTimeMillis();
        traversalChessborad(chessborad, row - 1, column - 1, 1);
        final long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start));

        for (int[] ints : chessborad) {
            System.out.println(Arrays.toString(ints));
        }
    }

    /**
     * 完成骑士周游问题的算法
     *
     * @param chessborad 棋盘
     * @param row        当前位置行
     * @param column     当前位置列
     * @param step       第几步
     */
    public static void traversalChessborad(int[][] chessborad, int row, int column, int step) {
        chessborad[row][column] = step;
        visited[row * X + column] = true;
        List<Point> ps = next(new Point(column, row));
        //对ps进行排序，排序的规则就是对ps的所有的Poit对象的下一步的位置的数目，进行非递减排序
        sort(ps);

        while (!ps.isEmpty()) {
            Point p = ps.remove(0);
            if (!visited[p.y * X + p.x]) {
                traversalChessborad(chessborad, p.y, p.x, step + 1);
            }
        }
        //判断马儿是否完成了任务，使用stp和应该走的步数比较，
        //如果没有达到数量，则表示没有完成任务，将整个棋盘置0
        //1,棋盘到目前位置，仍然没有走完
        //2。棋盘处于一个回溯过程
        if (step < X * Y && !finished) {
            chessborad[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }

    }


    /**
     * 功能：根据当前位置(Point.对象)，计算马儿还能走哪些位置(Point),并放入到一个集合中(ArrayList),最多有8个位置
     *
     * @param curPoint
     * @return
     */
    public static List<Point> next(Point curPoint) {
        List<Point> ps = new ArrayList<>();
        Point p1 = new Point();

        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

    //根据当前这个一步的所有的下一步的选择位置，进行非递减排序
    public static void sort(List<Point> ps) {
        ps.sort((o1, o2) -> {
            int count1 = next(o1).size();
            int count2 = next(o2).size();
            if (count1 < count2) {
                return -1;
            } else if (count1 == count2) {
                return 0;
            } else {
                return 1;
            }
        });
    }
}

-------------本文结束感谢您的阅读-------------

相关文章