分治算法

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

  • 二分搜索

  • 大整数乘法

  • 棋盘覆盖

  • 合并排序

  • 快速排序

  • 线性时间选择

  • 最接近点对问题

  • 循环赛日程表

  • 汉诺塔

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
合并：将各个子问题的解合并为原问题的解。

汉诺塔

如果是有一个盘， A->C
如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘

  1. 先把 最上面的盘 A->B
  2. 把最下边的盘 A->C
  3. 把B塔的所有盘 从 B->C 
1
2
3
4
5
6
7
8
9
10
11
12
public static void hanoiTower(int num,char a ,char b, char c){
    if (num == 1){
        System.out.println("第1个盘从 "+a+"->"+c);
    }else {
        //1.先把最上面的所有盘A->B
        hanoiTower(num-1,a,c,b);
        //把下面的盘A->C
        System.out.println("第"+num+"个盘从 "+a+"->"+c);
        //3.把B的盘移动到C
        hanoiTower(num-1,b,a,c);
    }
}

动态规划

动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法

动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )

动态规划可以通过填表的方式来逐步推进，得到最优解.

背包问题

有一个背包，容量为4磅 ， 现有如下物品

物品 重量 价格
a 1 1500
b 4 3000
c 3 2000

要求达到的目标为装入的背包的总价值最大，并且重量不超出
要求装入的物品不能重复

算法的主要思想，利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们有下面的结果：

物品 0 1 2 3 4
0 0 0 0 0
a 0 1500(a) 1500(a) 1500(a) 1500(a)
b 0 1500(a) 1500(a) 1500(a) 3000(b)
c 0 1500(a) 1500(a) 2000(c) 3500(a+c) 
1
2
3
4
5
6
7
8
9
(1)  v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是0
(2) 当w[i]> j 时：v[i][j]=v[i-1][j]   // 当准备加入新增的商品的容量大于 当前背包的容量时，就直接使用上一个单元格的装入策略
(3) 当j>=w[i]时： v[i] [j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}  
// 当 准备加入的新增的商品的容量小于等于当前背包的容量,
// 装入的方式:
v[i-1][j]： 就是上一个单元格的装入的最大值
v[i] : 表示当前商品的价值 
v[i-1][j-w[i]] ： 装入i-1商品，到剩余空间j-w[i]的最大值
当j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} : 
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 static void main(String[] args) {
    int[] w = {1, 4, 3};//物品的重量
    int[] val = {1500, 3000, 2000}; //物品的价值 这里val[i] 就是前面讲的v[i]
    int m = 4; //背包的容量
    int n = val.length; //物品的个数

    //创建二维数组，
    //v[i][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; //将第一列设置为0
    }
    for(int i=0; i < v[0].length; i++) {
        v[0][i] = 0; //将第一行设置0
    }

    //根据前面得到公式来动态规划处理
    for(int i = 1; i < v.length; i++) { //不处理第一行 i是从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 {
                //说明:
                //因为我们的i 从1开始的， 因此公式需要调整成
                //v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
                //v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                //为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用if-else来体现公式
                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
                    path[i][j] = 1;
                } else {
                    v[i][j] = v[i - 1][j];
                }

            }
        }
    }

    //输出一下v 看看目前的情况
    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();
    }

    System.out.println("============================");
    //输出最后我们是放入的哪些商品
    //遍历path, 这样输出会把所有的放入情况都得到, 其实我们只需要最后的放入
    // 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个商品放入到背包\n", i);
    //         }
    //     }
    // }
    //动脑筋
    int i = path.length - 1; //行的最大下标
    int j = path[0].length - 1;  //列的最大下标
    while(i > 0 && j > 0 ) { //从path的最后开始找
        if(path[i][j] == 1) {
            System.out.printf("第%d个商品放入到背包\n", i);
            j -= w[i-1]; //w[i-1]
        }
        i--;
    }
}

KMP算法

暴力匹配

现在str1匹配到 i 位置，子串str2匹配到 j 位置，则有:

  • 如果当前字符匹配成功（即str1[i] == str2[j]），则i++，j++，继续匹配下一个字符
  • 如果失配（即str1[i]! = str2[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。
  • 用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int violenceMatch(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方法算法就利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间

https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

字符串 bread

  • 前缀 b br bre ,brea
  • 后缀d ed ead read

abcda 前缀 a ab abc abcd 后缀 bcda ,cda,da,a 共有长度为1

  1. 完成部分匹配表

  2. 使用部分匹配表匹配字符串

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
next数组每次
ABABCABAA
001201231
AB ABC A   最长为1 
要让下一位匹配 只用判断下一位是不是B就可以了 
如果相同
 len++;
 next[i] = len; 
如果不相同
需要向前进行比较比
len = next[len-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()) {//找到了 // j = 3 i
                return i - j + 1;
            }
        }
        return  -1;
    }

    //获取到一个字符串(子串) 的部分匹配值表
    public static  int[] kmpNext(String dest) {
        //创建一个next 数组保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0; //如果字符串是长度为1 部分匹配值就是0

        int i = 1; //表示当前位置的最长公共子串
        int len = 0; //len表示最长的公共子串长度
        while (i<dest.length()){
            if (dest.charAt(i) == dest.charAt(len)){ //这一步是比较这一位是否相同
                len++;
                next[i] = len; //这一位的最长公共子串
                i++;
            }else {  //如果这一位不相等
                if (len > 0){   //len>0时需要向前找到相等的
                    len = next[len - 1];
                }else {
                    next[i] = len; //最长公共子串为0
                    i++;
                }
            }
        }
        return next;
    }

贪心算法

在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法.

不一定是最优的结果(有时候会是最优解)

集合覆盖问题

假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号

广播台 覆盖地区
K1 “北京”, “上海”, “天津”
K2 “广州”, “北京”, “深圳”
K3 “成都”, “上海”, “杭州”
K4 “上海”, “天津”
K5 “杭州”, “大连” 
1
2
3
遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系） 
将这个电台加入到一个集合中(比如ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
重复第1步直到覆盖了全部的地区

普里姆算法

有胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在需要修路把7个村庄连通
各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里
问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?

最小生成树：普里姆算法和克鲁斯卡尔算法

1
2
3
4
5
1.设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合 
2.若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited[u]=1
3.若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边（ui,vj）加入集合D中，标记visited[vj]=1
4.重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-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
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
public class Prim {

    public static final int MAX = 10000;

    public static void main(String[] args) {
        //测试看看图是否创建ok
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxs = data.length;
        //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
        int [][]weight=new int[][]{
                {0,5,7,10000,10000,10000,2},
                {5,0,10000,9,10000,10000,3},
                {7,10000,0,10000,8,10000,10000},
                {10000,9,10000,0,10000,4,10000},
                {10000,10000,8,10000,0,5,4},
                {10000,10000,10000,4,5,0,6},
                {2,3,10000,10000,4,6,0},};

        //创建MGraph对象
        MGraph graph = new MGraph(verxs);

        //创建一个MinTree对象
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, verxs, data, weight);
        //输出
        minTree.showGraph(graph);
        //测试普利姆算法
        minTree.prim(graph);//
    }


}
class MinTree {

    public static final int MAX = 10000; //默认10000不可达
    //创建图的邻接矩阵
    /**
     *
     * @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];
            }
        }
    }
    //显示图的邻接矩阵
    public void showGraph(MGraph graph) {
        for(int[] link: graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }
    /**
     * 默认从1开始
     * @param graph 图
     */
    public void prim(MGraph graph) {

        int[] lowcost = new int[graph.verxs];  //v0与其他顶点的距离
        int[] mst = new int[graph.verxs];
        //h1 和 h2 记录两个顶点的下标
        int min = 0;  //最小值
        int minid;   //记录最小值节点
        int sum = 0;//总长

        for(int i = 1; i < graph.verxs; i++){
            lowcost[i] = graph.weight[0][i]; //初始化赋值
            mst[i] = 0;
        }

        for(int i = 1; i < graph.verxs; i++){
            min = MAX;
            minid = 0;
            for (int j = 1;j<graph.verxs; j++){
                if (lowcost[j]<min && lowcost[j] != 0){  //当前节点的路径最小，且不为0（自己，数组已经包含的）
                    min = lowcost[j];
                    minid = j;
                }
            }
            System.out.println(graph.data[mst[minid]] + "到" + graph.data[minid] + " 权值：" + min);

            sum += min;
            lowcost[minid] = 0; //这条路不可以再走了
            //重新生成lowcost
            for (int j = 0;j<graph.verxs;j++){
                if (graph.weight[minid][j] < lowcost[j]){ //加入minid重新计算可达
                    lowcost[j] = graph.weight[minid][j];
                    mst[j] = minid;  //记录前一个节点
                }
            }
        }

        System.out.println("sum:"+sum);
    }
}
class MGraph {
    int verxs; //表示图的节点个数
    char[] data;//存放结点数据
    int[][] weight; //存放边，就是我们的邻接矩阵

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

克鲁斯卡尔

先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止

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
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
public class Kruskal {

    private int edgeNum; //边的集合
    private char[] vertexs; //顶点数组
    private int[][] matrix; //邻接矩阵
    //使用 INF 表示两个顶点不能连通
    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //克鲁斯卡尔算法的邻接矩阵
        int matrix[][] = {
                /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/ {   0,  12, INF, INF, INF,  16,  14},
                /*B*/ {  12,   0,  10, INF, INF,   7, INF},
                /*C*/ { INF,  10,   0,   3,   5,   6, INF},
                /*D*/ { INF, INF,   3,   0,   4, INF, INF},
                /*E*/ { INF, INF,   5,   4,   0,   2,   8},
                /*F*/ {  16,   7,   6, INF,   2,   0,   9},
                /*G*/ {  14, INF, INF, INF,   8,   9,   0}};
        //大家可以在去测试其它的邻接矩阵，结果都可以得到最小生成树.

        //创建KruskalCase 对象实例
        Kruskal kruskalCase = new Kruskal(vertexs, matrix);
        //输出构建的
        kruskalCase.print();
        kruskalCase.kruskal();
    }

    //构造器
    public Kruskal(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 void kruskal(){
        int index = 0;
        int[] ends = new int[edgeNum]; //用于保存最小生成树中每个顶点指向的重点

        //创建结果数组,保存最小生成树
        EData[] rets = new EData[edgeNum];
        EData[] edges = getEdges();

        //排序
        Arrays.sort(edges);
        //遍历edges数组，将边添加到最小生成树中，判断是否构成回路
        for (int i = 0; i<edgeNum; i++){
            //获取第i条边的顶点
            int p1 = getPosition(edges[i].start);
            int p2 = getPosition(edges[i].end);

            //获取p1这个顶点在树中的终点
            int m = getEnd(ends, p1); //这个顶点如果没有
            int n = getEnd(ends, p2);
            if (m != n){ //没有构成回路
                ends[m] = n;
                rets[index++] = edges[i]; //一天边加入
            }
        }

        //<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。
        //统计并打印 "最小生成树", 输出  rets
        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", matrix[i][j]);
            }
            System.out.println();//换行
        }
    }

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

    /**
     * 功能: 获取图中边，放到EData[] 数组中，后面我们需要遍历该数组
     * 是通过matrix 邻接矩阵来获取
     * EData[] 形式 [['A','B', 12], ['B','F',7], .....]
     * @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;
    }

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


}
//创建一个类EData ，它的对象实例就表示一条边
class EData implements Comparable<EData>{
    char start; //边的一个点
    char end; //边的另外一个点
    int weight; //边的权值
    //构造器
    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
    //重写toString, 便于输出边信息
    @Override
    public String toString() {
        return "EData [<" + start + ", " + end + ">= " + weight + "]";
    }

    @Override
    public int compareTo(EData o) {
        return this.weight - o.weight;
    }
}

prim算法适合稠密图，kruskal算法适合稀疏图。

prim O(n2)

kruskal O(nlogn)

迪杰斯特拉

Dijkstra O(n²)

以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

1
2
3
4
设置出发顶点为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集合中顶点的距离值，保留值较小的一个(同时也应该更新顶点的前驱节点为vi，表明是通过vi到达的)
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
public class Dijkstra {
    public static void main(String[] args) {
        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        //邻接矩阵
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;// 表示不可以连接
        matrix[0]=new int[]{N,5,7,N,N,N,2};
        matrix[1]=new int[]{5,N,N,9,N,N,3};
        matrix[2]=new int[]{7,N,N,N,8,N,N};
        matrix[3]=new int[]{N,9,N,N,N,4,N};
        matrix[4]=new int[]{N,N,8,N,N,5,4};
        matrix[5]=new int[]{N,N,N,4,5,N,6};
        matrix[6]=new int[]{2,3,N,N,4,6,N};
        //创建 Graph对象
        Graph graph = new Graph(vertex, matrix);
        //测试, 看看图的邻接矩阵是否ok
        graph.showGraph();
        //测试迪杰斯特拉算法
        graph.dsj(0);//C
        graph.showDijkstra();
    }

}
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 showDijkstra() {
        vv.show();
    }

    // 显示图
    public void showGraph() {
        for (int[] link : matrix) {
            System.out.println(Arrays.toString(link));
        }
    }

    //迪杰斯特拉算法实现
    /**
     *
     * @param index 表示出发顶点对应的下标
     */
    public void dsj(int index) {
        vv = new VisitedVertex(vertex.length, index);
        update(index);//更新index顶点到周围顶点的距离和前驱顶点
        for(int j = 1; j <vertex.length; j++) {
            index = vv.updateArr();// 选择并返回新的访问顶点
            update(index); // 更新index顶点到周围顶点的距离和前驱顶点
        }
    }



    //更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点,
    private void update(int index) {
        int len = 0;
        //根据遍历我们的邻接矩阵的  matrix[index]行
        for(int j = 0; j < matrix[index].length; j++) {
            // len 含义是 : 出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和
            len = vv.getDis(index) + matrix[index][j];
            // 如果j顶点没有被访问过，并且 len 小于出发顶点到j顶点的距离，就需要更新
            if(!vv.in(j) && len < vv.getDis(j)) {
                vv.updatePre(j, index); //更新j顶点的前驱为index顶点
                vv.updateDis(j, len); //更新出发顶点到j顶点的距离
            }
        }
    }
}
class VisitedVertex {
    // 记录各个顶点是否访问过 1表示访问过,0未访问,会动态更新
    public int[] already_arr;
    // 每个下标对应的值为前一个顶点下标, 会动态更新
    public int[] pre_visited;
    // 记录出发顶点到其他所有顶点的距离,比如G为出发顶点，就会记录G到其它顶点的距离，会动态更新，求的最短距离就会存放到dis
    public int[] dis;

    //构造器

    /**
     * @param length :表示顶点的个数
     * @param index: 出发顶点对应的下标, 比如G顶点，下标就是6
     */
    public VisitedVertex(int length, int index) {
        this.already_arr = new int[length];
        this.pre_visited = new int[length];
        this.dis = new int[length];
        //初始化 dis数组
        Arrays.fill(dis, 65535);
        this.already_arr[index] = 1; //设置出发顶点被访问过
        this.dis[index] = 0;//设置出发顶点的访问距离为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];
    }

    /**
     * 继续选择并返回新的访问顶点，找出最短的顶点
     * @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;
            }
        }
        //更新 index 顶点被访问过
        already_arr[index] = 1;
        return index;
    }

    //显示最后的结果
    //即将三个数组的情况输出
    public void show() {

        System.out.println("==========================");
        //输出already_arr
        for(int i : already_arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        //输出pre_visited
        for(int i : pre_visited) {
            System.out.print(i + " ");
        }
        System.out.println();
        //输出dis
        for(int i : dis) {
            System.out.print(i + " ");
        }
        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
1.设置顶点vi到顶点vk的最短路径已知为Lik，顶点vk到vj的最短路径已知为Lkj，顶点vi到vj的路径为Lij，则vi到vj的最短路径为：min((Lik+Lkj),Lij)，vk的取值为图中所有顶点，则可获得vi到vj的最短路径
2.至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj，是以同样的方式获得
2张表 ，一张是前驱节点，一张是距离
1.通俗讲，就是讲这个顶点作为中间顶点计算所有顶点的最低路径
2.每次更换中间节点，遍历，最后得出结果
中间顶点  [A,B,C,D,E] K
出发顶点  [A,B,C,D,E] i
	终点  [A,B,C,D,E]	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
public class Floyd {
    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 length 大小
     * @param matrix 邻接矩阵
     * @param vertex 顶点数组
     */
    public Graph(int length, int[][] matrix, char[] vertex) {
        this.vertex = vertex;
        this.dis = matrix;
        this.pre = new int[length][length];
        // 对pre数组初始化, 注意存放的是前驱顶点的下标
        for (int i = 0; i < length; i++) {
            Arrays.fill(pre[i], i);
        }
    }

    // 显示pre数组和dis数组
    public void show() {

        //为了显示便于阅读，我们优化一下输出
        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        for (int k = 0; k < dis.length; k++) {
            // 先将pre数组输出的一行
            for (int i = 0; i < dis.length; i++) {
                System.out.print(vertex[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();
            System.out.println();
        }
    }

    public void floyd(){
        int len = 0; //保存距离

        for (int k = 0;k < dis.length;k++){  //中间节点

            for(int i = 0; i < dis.length; i++){ //从顶点开始
                for (int j = 0; j < dis.length; j++){
                    len = dis[i][k] + dis[k][j];
                    if (len < dis[i][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
public class HorseChessboard {

    private static int X ; // 棋盘的列数
    private static int Y ; // 棋盘的行数

    //创建一个数组，标记棋盘的各个位置是否被访问过
    private static boolean visited[];

    //使用一个属性，标记是否棋盘的所有位置都被访问
    private static boolean finished; // 如果为true,表示成功

    public static void main(String[] args) {
        //测试骑士周游算法是否正确
        X = 8;
        Y = 8;
        int row = 1; //马儿初始位置的行，从1开始编号
        int column = 1; //马儿初始位置的列，从1开始编号
        //创建棋盘
        int[][] chessboard = new int[X][Y];
        visited = new boolean[X * Y];//初始值都是false
        //测试一下耗时
        long start = System.currentTimeMillis();
        traversalChessboard(chessboard, row - 1, column - 1, 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时: " + (end - start) + " 毫秒");

        //输出棋盘的最后情况
        for(int[] rows : chessboard) {
            for(int step: rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 完成骑士周游问题的算法
     * @param chessboard 棋盘
     * @param row 马儿当前的位置的行 从0开始
     * @param column 马儿当前的位置的列  从0开始
     * @param step 是第几步 ,初始位置就是第1步
     */
    public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
        chessboard[row][column] = step;
        //row = 4 X = 8 column = 4 = 4 * 8 + 4 = 36
        visited[row * X + column] = true; //标记该位置已经访问
        //获取当前位置可以走的下一个位置的集合
        ArrayList<Point> ps = next(new Point(column, row));
        //对ps进行排序,排序的规则就是对ps的所有的Point对象的下一步的位置的数目，进行非递减排序
        sort(ps);
        while (!ps.isEmpty()){
            Point p = ps.remove(0); //取出下一个可以走的位置
            //判断这个点是否已经访问过
            if(!visited[p.y * X + p.x]) {//说明还没有访问过
                traversalChessboard(chessboard, p.y, p.x, step + 1);
            }
        }
        //判断马儿是否完成了任务，使用   step 和应该走的步数比较 ，
        //如果没有达到数量，则表示没有完成任务，将整个棋盘置0
        //说明: step < X * Y  成立的情况有两种
        //1. 棋盘到目前位置,仍然没有走完
        //2. 棋盘处于一个回溯过程
        if(step < X * Y && !finished ) {
            chessboard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }
    }

    public static ArrayList<Point> next(Point curPoint){
        //创建一个ArrayList
        ArrayList<Point> ps = new ArrayList<Point>();
        //创建一个Point
        Point p1 = new Point();
        //表示马儿可以走5这个位置
        if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y -1) >= 0) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走6这个位置
        if((p1.x = curPoint.x - 1) >=0 && (p1.y=curPoint.y-2)>=0) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走7这个位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走0这个位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走1这个位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走2这个位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走3这个位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走4这个位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

    //优化，进行非递减排序
    //根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数
    public static void sort(ArrayList<Point> ps) {
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                //获取到o1下一步所有的个数
                int count1 = next(o1).size();
                int count2 = next(o2).size();
                if (count1 < count2){
                    return -1;
                }else if (count1 == count2){
                    return 0;
                }else {
                    return 1;
                }
            }
        });
    }
}