D16-常用十种算法[Java数据结构和算法]

1.二分查找（非递归）代码实现

1 //实现查找的非递归查找 2 /** 3 * 4 * @param arr 待查找的数组，arr是升序排序 5 * @param target 需要查找的数 6 * @return 返回对应的下标，-1表示没找到 7 */ 8 public static int binarySearch(int[] arr,int target) { 9 int left=0; 10 int right=arr.length-1; 11 while(left<=right) { 12 int mid=(left+right)/2; 13 if(arr[mid]==target) { 14 return mid; 15 }else if(arr[mid]>target) { 16 right=mid-1; 17 }else { 18 left=mid+1; 19 } 20 } 21 return -1; 22 }

2.分治算法（Divide-and Conquer）

　　2.1 分治算法的思想

　　（1）把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题....直到最后子问题可以简单直接求解，原问题的解即子问题的解的合并；

　　（2）分治算法可以求解的经典问题：二分搜索，大整数乘法，棋盘覆盖，合并排序，快速排序，线性时间选择，最接近点对问题，循环赛日程表，汉诺塔等；

　　2.2 分治算法的基本步骤

　　（1）分解：将原问题分解为若干个较小，相互独立，与原问题形式相同的子问题；

　　（2）解决：将子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；

　　（3）合并：将各个子问题的解合并为原问题的解；

　　2.3 分治算法的最佳实现-汉诺塔问题

　　（1）如果只有一个盘，A->C

　　如果有n>=2情况，踪师可以看作是两个盘1，最下面的盘2，上面的盘

　　　　1）先把最上面的盘A->B

　　　　2）把最下面的盘A->C

　　　　3）把B塔中所有的盘从B->C

　　（2）源代码

 1 //汉诺塔的移动方法，使用分治算法
 2     public static void hanoiTower(int num,char a,char b,char c) {
 3         //如果只有一个盘
 4         if(num==1) {
 5             System.out.println("第1个盘"+a+"->"+c);
 6         }
 7         if(num>=2) {
 8             //将最上面的所有盘从A->B
 9             hanoiTower(num-1, a, c, b);
10             //将最下面的一个盘从a->c
11             System.out.println("第"+num+"个盘"+a+"->"+c);
12             //把b塔所有的盘给c盘
13             hanoiTower(num-1, b, a, c);    
14         }
15     }

3.动态规划(Dynamic Programming)

　　3.1 动态规划算法基本介绍

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

　　（2）动态规划的基本思想是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解；

　　（3）适合于用动态规划求解的问题，经分解得到子问题往往不是相互独立的，即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解；

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

　　3.2 动态规划算法的最佳实践-背包问题

　　（1）思路分析

　　（2）源代码实现

 1 package com.atguigu.dynamic;
 2 
 3 public class KnapsackProblem {
 4 
 5     public static void main(String[] args) {
 6         // TODO Auto-generated method stub
 7         int[] w= {1,4,3};//物品的重量
 8         int[] val= {1500,3000,2000};//物品的价值
 9         int m=4;//背包的容量
10         int n=val.length;//物品的价值
11         
12         
13         //创建二维数组
14         //v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
15         int[][] v=new int[n+1][m+1];
16         
17         //为了记录放入商品的情况，定义一个二维数组
18         int[][] path=new int[n+1][m+1];
19         
20         //初始化第一行和第一列
21         for(int i=0;i<v.length;i++) {//处理第一列
22             v[i][0]=0;
23         }
24         for(int i=0;i<v[0].length;i++) {//处理第一行
25             v[0][i]=0;
26         }
27         
28         for(int i=1;i<v.length;i++) {//不处理第一行
29             for(int j=1;j<v[0].length;j++) {
30                 if(w[i-1]>j) {
31                     v[i][j]=v[i-1][j];
32                 }else {
33 //                    v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
34                     if(v[i-1][j]>val[i-1]+v[i-1][j-w[i-1]]) {
35                         v[i][j]=v[i-1][j];
36                     }else {
37                         v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
38                         path[i][j]=1;
39                     }
40                 }
41             }
42         }
43         
44         for(int i=0;i<v.length;i++) {
45             for(int j=0;j<v[0].length;j++) {
46                 System.out.print(v[i][j]+" ");
47             }
48             System.out.println();
49         }
50         
51         //输出最后我们放入说的是哪些商品
52         int i=path.length-1;//行的最大下标
53         int j=path[0].length-1;//列的最大下标
54         while(i>0&&j>0) {
55             if(path[i][j]==1) {
56                 System.out.printf("第%d个商品放入到背包
",i);
57                 j-=w[i-1];
58             }
59             i--;
60         }
61     }
62 
63 }

4.KMP算法

　　4.1暴力匹配算法

　　（1）思路，假设现在str1匹配到i位置，子串str2匹配到j位置，则有：

　　　　1）若当前字符匹配成功，则i++，j++，继续匹配下一个字符；

　　　　2）若失配，令i=i-(j-1)，j=0。相当于每次匹配失败时，i回溯，j被置为9；

　　　　3）用暴力方法解决会有大量的回溯，每次只移动一次，若不匹配，移动到下一位接着判断，浪费大量时间；

　　（2）算法实现

 1 public static int violenceMatch(String str1,String str2) {
 2         int i=0;
 3         int j=0;
 4         while(i<str1.length()&&j<str2.length()) {
 5             if(str1.charAt(i)==str2.charAt(j)) {//如果匹配就继续
 6                 i++;
 7                 j++;
 8             }else {//如果不匹配
 9                 i=i-(j-1);
10                 j=0;
11             }
12         }
13         if(j==str2.length()) {
14             return i-j;
15         }else {
16             return -1;
17         }
18         
19     }

　　4.2 KMP算法(Knuth-Morris-Pratt)

　　（1）解决模式串在文本串中是否出现过，如果出现过，最早出现的位置的经典算法；

　　（2）利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到前面匹配过的位置，省去了大量的时间；

　　（3）源代码

 1 //写出我们的kmp搜索算法
 2     /**
 3      * 
 4      * @param str1 源字符串
 5      * @param str2 子串
 6      * @param next 部分匹配表，是子串对应的部分匹配表
 7      * @return 如果是-1就是没有匹配到，否则返回第一个匹配的位置
 8      */
 9     public static int kmpSearch(String str1,String str2,int[] next) {
10         //遍历
11         for (int i = 0, j=0 ; i < str1.length(); i++) {
12             
13             //需要处理str1.charAt(i)!=str2.charAt(j),要去调整j的大小
14             //KMP算法的核心点
15             while( j >0 &&  str1.charAt(i)!=str2.charAt(j)) {
16                 j=next[j-1];
17             }
18             if(str1.charAt(i)==str2.charAt(j)) {
19                 j++;
20             }
21             if(j==str2.length()) {//说明找到了
22                 return i-j+1;
23             }
24         }
25         return -1;
26     }
27 
28     // 获取到一个字符串的部分匹配值表
29     public static int[] kmpNext(String dest) {
30         // 创建一个next 数组保存部分匹配值
31         int[] next = new int[dest.length()];
32         next[0] = 0;// 如果字符串的长度为1，部分匹配值就是0
33         for (int i = 1, j = 0; i < dest.length(); i++) {
34             //当dest.charAt(i)!=dest.charAt(j)，需要从next[j-1]获取新的j
35             //直到我们发现有dest.charAt(i)==dest.charAt(j)成立时才退出
36             //kmp算法的核心点
37             while(j>0 && dest.charAt(i)!=dest.charAt(j)) {
38                 j=next[j-1];
39             }
40             // 当dest.charAt(i)==dest.charAt(j)满足时，部分匹配值就是+1
41             if (dest.charAt(i) == dest.charAt(j)) {
42                 j++;
43             }
44             next[i] = j;
45         }
46         return next;
47     }

5.贪心算法

　　5.1　介绍

　　（1）贪心算法（贪婪算法）指在问题求解时，在每一步选择中都采取最好或者最优的选择，从而希望能够导致结果是最好或是最优的算法；

　　（2）贪婪算法所得到的结果不一定是最优的结果（有时候是最优解），但是都是相对近似（接近）最优解的结果；

　　5.2 源代码-集合覆盖问题

 1 package com.atguigu.greedy;
 2 
 3 import java.util.ArrayList;
 4 import java.util.HashMap;
 5 import java.util.HashSet;
 6 
 7 public class GreedyAlgorithm {
 8     public static void main(String[] args) {
 9         //创建广播电台
10         HashMap<String, HashSet<String>> broadcasts=new HashMap<String, HashSet<String>>();
11         //将各个电台放入到broadcasts
12         HashSet<String> hashSet1=new HashSet<String>();
13         hashSet1.add("北京");
14         hashSet1.add("上海");
15         hashSet1.add("天津");
16         
17         HashSet<String> hashSet2=new HashSet<String>();
18         hashSet2.add("广州");
19         hashSet2.add("上海");
20         hashSet2.add("深圳");
21         
22         HashSet<String> hashSet3=new HashSet<String>();
23         hashSet3.add("成都");
24         hashSet3.add("上海");
25         hashSet3.add("杭州");
26         
27         HashSet<String> hashSet4=new HashSet<String>();
28         hashSet4.add("上海");
29         hashSet4.add("天津");
30         
31         HashSet<String> hashSet5=new HashSet<String>();
32         hashSet5.add("杭州");
33         hashSet5.add("大连");
34         
35         broadcasts.put("K1", hashSet1);
36         broadcasts.put("K2", hashSet2);
37         broadcasts.put("K3", hashSet3);
38         broadcasts.put("K4", hashSet4);
39         broadcasts.put("K5", hashSet5);
40         
41         HashSet<String> allAreas=new HashSet<String>();//存放所有的城市
42         allAreas.add("北京");
43         allAreas.add("上海");
44         allAreas.add("天津");
45         allAreas.add("广州");
46         allAreas.add("深圳");
47         allAreas.add("成都");
48         allAreas.add("杭州");
49         allAreas.add("大连");
50         
51         ArrayList<String> SelectedBC=new ArrayList<String>();//存放选择电台的集合
52         
53         //定义一个临时的集合，在遍历过程中，存放遍历过程中电台覆盖地区和当前没有覆盖地区的交集
54         HashSet<String> tempSet=new HashSet<String>();
55         
56         //定义maxKey,保存在一次遍历过程中，能够覆盖最大未覆盖地区对应的电台key
57         //如果maxKey不为null，则会加入到SelectedBC
58         String maxKey=null;
59         while(allAreas.size()!=0) {//如果allAreas不为0，则表示还没有覆盖到所有的地区
60             //每进行一次while，需要
61             maxKey=null;
62             //遍历broadcasts,取出对应的key
63             for(String key:broadcasts.keySet()) {
64                 //没进行一次for
65                 tempSet.clear();
66                 //当前这个key能覆盖的地区
67                 HashSet<String> areas=broadcasts.get(key);
68                 tempSet.addAll(areas);
69                 //求出tempSet和allAreas集合的交集
70                 tempSet.retainAll(allAreas);
71                 //如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多
72                 //tempSet.size()>broadcasts.get(maxKey).size()) 体现出贪心算法的特点
73                 if(tempSet.size()>0 &&
74                         (maxKey==null ||tempSet.size()>broadcasts.get(maxKey).size())) {
75                     maxKey=key;
76                 }
77             }
78             //maxKey!=null，就应该将maxKey加入到SelectedBC
79             if(maxKey!=null) {
80                     SelectedBC.add(maxKey);
81                     //将maxKey指向的广播电台覆盖的地区，从allAreas去掉
82                     allAreas.removeAll(broadcasts.get(maxKey));
83                 }
84         }
85         System.out.println("得到的选择结果"+SelectedBC);
86     }
87     
88     
89 }

6 普里姆算法(Prim)

　　6.1 最小生成树（Minimum Cost Spanning Tree,MST）

　　（1）给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，称为最小生成树；

　　（2）N个顶点，一定有N-1条边;

　　（3）包含所有顶点；

　　（4）求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法；

　　6.2 普里姆算法介绍

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

　　（2）设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合；

　　（3）若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入到集合U中，标记顶点v 的visted[u]=1;

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

　　（5）重复步骤3，若U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边；

　　6.3 普里姆算法的应用实例

  1 package com.atguigu.prim;
  2 
  3 import java.util.Arrays;
  4 
  5 public class PrimAlgorithm {
  6 
  7     public static void main(String[] args) {
  8         // 测试图是否创建成功
  9         char[] data=new char[]{'A','B','C','D','E','F','G'};
 10         int verxs=data.length;
 11         //邻接矩阵的关系使用二维数组表示
 12         int[][] weight=new int[][] {
 13             {10000,5,7,10000,10000,10000,2},
 14             {5,10000,10000,9,10000,10000,3},
 15             {7,10000,10000,10000,8,10000,10000},
 16             {10000,9,10000,10000,10000,4,10000},
 17             {10000,10000,8,10000,10000,5,4},
 18             {10000,10000,10000,4,5,10000,6},
 19             {2,3,10000,10000,4,6,10000}
 20         };
 21         //创建MGraph对象
 22         MGraph mGraph=new MGraph(verxs);
 23         //创建MinTree对象
 24         MinTree minTree=new MinTree();
 25         minTree.createGraph(mGraph, verxs, data, weight);
 26         minTree.showGraph(mGraph);
 27         minTree.prim(mGraph, 0);
 28     }
 29 
 30 }
 31 //创建最小生成树->村庄的图
 32 class MinTree{
 33     //创建图的邻接矩阵
 34     /**
 35      * 
 36      * @param graph 图对象
 37      * @param verxs 图对应的顶点个数
 38      * @param data 图的各个顶点的值
 39      * @param weight 图的邻接矩阵
 40      */
 41     public void createGraph(MGraph graph,int verxs,char data[],int[][] weight) {
 42         int i,j;
 43         for ( i = 0; i < verxs; i++) {//顶点
 44             graph.data[i]=data[i];
 45             for ( j = 0; j < verxs; j++) {
 46                 graph.weight[i][j]=weight[i][j];
 47             }
 48         }
 49     }
 50     
 51     //显示图的邻接矩阵
 52     public void showGraph(MGraph graph) {
 53         for(int[] link:graph.weight) {
 54             System.out.println(Arrays.toString(link));
 55         }
 56     }
 57     
 58     //编写prim算法，得到最小生成树
 59     /**
 60      * 
 61      * @param graph 图
 62      * @param v 表示从图的第几个顶点开始生成
 63      */
 64     public void prim(MGraph graph,int v) {
 65         //visited[] 标记顶点是否被访问过
 66         int visited[]=new int[graph.verxs];
 67         //visitd[] 默认元素的值是0，表示没有被访问过
 68         for (int i = 0; i < visited.length; i++) {
 69             visited[i]=0;
 70         }
 71         //把当前这个顶点标记为已经访问
 72         visited[v]=1;
 73         //h1和h2为记录为两个顶点的下标
 74         int h1=-1;
 75         int h2=-1;
 76         //将minWeight初始化为一个大数，后面在遍历过程中，会被替换
 77         int minWeight=10000;
 78         //因为graph.verxs顶点，普里姆算法结束后，有graph.verxs-1边
 79         for(int k=1;k<graph.verxs;k++) {
 80             //确定顶每一次生成的子图，和哪个节点和这次遍历的距离最近
 81             for(int i=0;i<graph.verxs;i++) {//i节点表示被访问过的节点
 82                 for(int j=0;j<graph.verxs;j++) {//j节点表示还没有访问过的节点
 83                     if(visited[i]==1&&visited[j]==0&&graph.weight[i][j]<minWeight) {
 84                         minWeight=graph.weight[i][j];//替换minWeight(寻找已经访问过的节点和未访问过的节点间的权值最小的边)
 85                         h1=i;
 86                         h2=j;
 87                     }
 88                 }
 89             }//这个一条边是最小
 90             System.out.println("本次的找到边权值最小的为："+graph.data[h1]+"===>"+graph.data[h2]+"，其权值为："+minWeight);
 91             //将当前找到的节点标记为已经访问过的
 92             visited[h2]=1;
 93             //重置minWeight
 94             minWeight=10000;
 95         }
 96     }
 97 }
 98 
 99 class MGraph{
100     int verxs;//表示图的节点个数
101     char[] data;//存放节点数据
102     int[][] weight;//存放边，就是邻接矩阵
103     public MGraph(int verxs) {
104         this.verxs=verxs;
105         data=new char[verxs];
106         weight=new int[verxs][verxs];
107     }
108 }

7.克鲁斯卡尔算法(Kruskal)

　　7.1克鲁斯卡尔算法介绍

　　（1）克鲁斯卡尔算法是用来求加权连通图的最小生成树的算法；

　　（2）基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路；

　　（3）具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择加入到森林中，并使森林中不产生回路，直到森林变成一棵树为止；

　　（4）加入的边的两个顶点不能都指向同一个终点，否则将构成回路；

　　7.2 源代码

  1 package com.atguigu.Kruskal;
  2 
  3 import java.sql.Array;
  4 import java.util.Arrays;
  5 
  6 public class KruskalAlgorithm {
  7     private int edgeNum;//边的个数
  8     private char[] vertexs;//顶点数组
  9     private int[][] matrix;//邻接矩阵
 10     private static final int INF=Integer.MAX_VALUE;//使用INF表示两个质点不能连通
 11     public static void main(String[] args) {
 12         char[] vertexs= {'A','B','C','D','E','F','G'};
 13         int[][] matrix= {
 14                 {0,12,INF,INF,INF,16,14},
 15                 {12,0,10,INF,INF,7,INF},
 16                 {INF,10,0,3,5,6,INF},
 17                 {INF,INF,3,0,4,INF,INF},
 18                 {INF,INF,5,4,0,2,8},
 19                 {16,7,6,INF,2,0,9},
 20                 {14,INF,INF,INF,8,9,0}
 21         };
 22         //创建对象
 23         KruskalAlgorithm kruskalCase=new KruskalAlgorithm(vertexs, matrix);
 24         kruskalCase.print();
 25         System.out.println(Arrays.toString(kruskalCase.getEdges()));
 26         kruskalCase.kruskal();
 27 
 28     }
 29     
 30     public KruskalAlgorithm(char[] vertexs,int[][] matrix) {
 31         //初始化顶点数和边的个数
 32         int vlen=vertexs.length;
 33         
 34         //初始化顶点
 35         this.vertexs=new char[vlen];
 36         for(int i=0;i<vertexs.length;i++) {
 37             this.vertexs[i]=vertexs[i];
 38         }
 39         
 40         //初始化边,使用的复制拷贝的方式
 41         this.matrix=new int[vlen][vlen];
 42         for (int  i= 0;  i< vlen; i++) {
 43             for (int j = 0; j < vlen; j++) {
 44                 this.matrix[i][j]=matrix[i][j];
 45             }
 46         }
 47         
 48         //统计边
 49         for (int  i= 0;  i< vlen; i++) {
 50             for (int j = i+1; j < vlen; j++) {
 51                 if(this.matrix[i][j]!=INF) {
 52                     edgeNum++;
 53                 }
 54             }
 55         }
 56     }
 57     public void kruskal() {
 58         int index=0;//表示最后结果数组的索引
 59         int[] ends=new int[edgeNum];//用于保存"已有最小生成树"中的每个顶点在最小生成树中的终点
 60         //创建结果数组，保存最后的最小生成树
 61         EData[] rets=new EData[edgeNum];
 62         
 63         //获取图中所有的边的集合，一共有12边
 64         EData[] edges=getEdges();
 65         System.out.println("图的边的集合："+Arrays.toString(edges)+"共"+edges.length);
 66         //按照边的权值大小排序
 67         sortEdge(edges);
 68         //遍历edges数组,将边添加到最小生成树时，判断准备加入的边是否形成了回路，如果没有，就加入rets，否则不能加入
 69         for (int i = 0; i < edgeNum; i++) {
 70             //获取到第i条边的第一个顶点
 71             int p1=getPosition(edges[i].start);
 72             //获取到第i条边的第二个顶点
 73             int p2=getPosition(edges[i].end);
 74             //获取到p1这个顶点在已有最小生成树中的终点
 75             int m=getEnd(ends, p1);
 76             //获取到p2这个顶点在已有最小生成树中的终点
 77             int n=getEnd(ends, p2);
 78             if(m!=n) {//说明没有构成回路
 79                 ends[m]=n;//设置m"已有最小生成树"的终点
 80                 rets[index++]=edges[i];//有一条边加入到rets数组中
 81                 
 82             }
 83         }
 84         
 85         //统计并打印最小生成树 输出rets
 86         System.out.println("最小生成树为：");
 87         for (int i = 0; i < index; i++) {
 88             System.out.println(rets[i]);
 89         }
 90     }
 91     //打印邻接矩阵
 92     public void print() {
 93         System.out.println("邻接矩阵为：
");
 94         for (int i = 0; i < vertexs.length; i++) {
 95             for (int j = 0; j < vertexs.length; j++) {
 96                 System.out.printf("%12d	",matrix[i][j]);
 97             }
 98             System.out.println();
 99         }
100     }
101     /**
102      * 功能：先按照边的权值进行排序,冒泡排序
103      * @param edges 边的集合
104      */
105     private void sortEdge(EData[] edges) {
106         for (int i = 0; i < edges.length-1; i++) {
107             for (int j = 0; j < edges.length-1-i; j++) {
108                 if(edges[j].weight>edges[j+1].weight) {//交换
109                     EData tmp=edges[j];
110                     edges[j]=edges[j+1];
111                     edges[j+1]=tmp;
112                 }
113             }
114         }
115     }
116     /**
117      * 
118      * @param ch 顶点的值，比如'A','B'
119      * @return 返回ch顶点对应的下标，如果找不到，返回-1
120      */
121     private int getPosition(char ch) {
122         for (int i = 0; i < vertexs.length; i++) {
123             if(vertexs[i]==ch) {
124                 return i;
125             }
126         }
127         return -1;
128     }
129     /**
130      * 获取图中边，放到EData数组中，后面需要遍历该数组
131      * 通过matrix邻接矩阵来获取
132      * EData[] 形式['A','B',12],['B','F',7]....
133      * @return
134      */
135     private EData[] getEdges() {
136         int index=0;
137         EData[] edges=new EData[edgeNum];
138         for (int i = 0; i < vertexs.length; i++) {
139             for (int j = i+1; j < vertexs.length; j++) {
140                 if(matrix[i][j]!=INF) {
141                     edges[index++]=new EData(vertexs[i], vertexs[j], matrix[i][j]);
142                 }
143             }
144         }
145         return edges;
146     }
147     /**
148      * 获取下标为i的顶点的终点，用于后面判断两个顶点的重点是否相同
149      * @param ends 数组就是记录了各个顶点对应的终点是哪个，ends数组在遍历过程中，逐步形成
150      * @param i 表示传入的顶点对应的下标
151      * @return 返回的是下标为i的这个顶点对应的终点的下标
152      */
153     private int getEnd(int[] ends,int i) {
154         while(ends[i]!=0) {
155             i=ends[i];
156         }
157         return i;
158     }
159 }
160 
161 //创建了一个类EData，它的对象实例就表示一条边
162 class EData{
163     char start;//边的一个点
164     char end;//边的另外一个点
165     int weight;//边的权值
166     
167     public EData(char start,char end,int weight) {
168         this.start=start;
169         this.end=end;
170         this.weight=weight;
171     }
172 
173     @Override//重写toString方法，便于输出边
174     public String toString() {
175         return "EData [<" + start + ", " + end + ">=" + weight + "]";
176     }
177 }

8.迪杰斯特拉算法(Dijkstra)

　　8.1 迪杰斯特拉算法介绍

　　（1）是典型的最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层（广度优先搜索）层层扩展，直到扩展到终点为止；

　　8.2 迪杰斯特拉算法过程

　　设置出发顶点为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）重复执行两步骤，直到最短路径顶点为目标顶点即可结束；

　　8.3 源代码

  1 package com.atguigu.dijkstra;
  2 
  3 import java.util.Arrays;
  4 
  5 public class DijkstraAlgorithm {
  6 
  7     public static void main(String[] args) {
  8         char[] vertex= {'A','B','C','D','E','F','G'};
  9         //邻接矩阵
 10         int[][] matrix=new int[vertex.length][vertex.length];
 11         final int N=65535;//表示不可连接
 12         matrix[0]=new int[] {N,5,7,N,N,N,2};
 13         matrix[1]=new int[] {5,N,N,9,N,N,3};
 14         matrix[2]=new int[] {7,N,N,N,8,N,N};
 15         matrix[3]=new int[] {N,9,N,N,N,4,N};
 16         matrix[4]=new int[] {N,N,8,N,N,5,4};
 17         matrix[5]=new int[] {N,N,N,4,5,N,6};
 18         matrix[6]=new int[] {2,3,N,N,4,6,N};
 19         //创建Graph 对象
 20         Graph graph=new Graph(vertex, matrix);
 21         graph.showGraph();
 22         //测试迪杰斯特拉算法
 23         graph.dsj(6);
 24         graph.showDijkstra();
 25     }
 26 
 27 }
 28 
 29 class Graph{
 30     private char[] vertex;//顶点数组
 31     private int[][] matrix;//邻接矩阵
 32     private VisitedVertex vv;//已经访问顶点的集合
 33     
 34     public Graph(char[] vertex,int[][] matrix) {//构造器
 35         this.vertex=vertex;
 36         this.matrix=matrix;
 37     }
 38     public void showDijkstra() {
 39         vv.show();
 40     }
 41     //显示图
 42     public void showGraph() {
 43         for(int[] link:matrix) {
 44             System.out.println(Arrays.toString(link));
 45         }
 46     }
 47     
 48     /**
 49      * 迪杰斯特拉算法实现
 50      * @param index 出发顶点对应的下标
 51      */
 52     public void dsj(int index) {
 53         vv=new VisitedVertex(vertex.length, index);
 54         update(index);//更新index下标到周围顶点的距离和前驱结点
 55         for(int j=1;j<vertex.length;j++) {
 56             index=vv.updateArr();//选择并返回新的访问顶点
 57             update(index);//更新index下标到周围顶点的距离和前驱结点
 58         }
 59     }
 60     //更新index下标顶点到周围顶点的距离和周围顶点的前驱结点
 61     public void update(int index) {
 62         int len=0;
 63         //根据遍历我们的邻接矩阵matrix[index]行
 64         for(int j=0;j<matrix[index].length;j++) {
 65             //len :出发顶点到index顶点的距离+从index顶点到j顶点的距离之和
 66             len=vv.getDis(index)+matrix[index][j];
 67             //如果j顶点没有被访问过，并且len小于出发顶点到j顶点的距离，就需要更新
 68             if(!vv.in(j)&&len<vv.getDis(j)) {
 69                 vv.update(j, index);//更新j顶点的前驱为index顶点
 70                 vv.updateDis(j, len);//更新出发顶点到j顶点的距离
 71             }
 72         }
 73     }
 74     
 75 }
 76 
 77 //已访问顶点集合
 78 class VisitedVertex{
 79     //记录各个顶点是否访问过 1表示访问过，0表示未访问过，动态更新
 80     public int[] already_arr;
 81     //每个下标对应的值为前一个顶点的下标，动态更新
 82     public int[] pre_visited;
 83     //记录出发顶点到其他所有顶点的距离，比如G为出发顶点，就会记录G到出发顶点的距离，动态更新，求的最短距离会存放在dis中
 84     public int[] dis;
 85     /**
 86      * 构造器
 87      * @param length 表示顶点的个数
 88      * @param index 出发顶点对应的下标，比如G顶点的下标为6
 89      */
 90     public VisitedVertex(int length,int index) {
 91         this.already_arr=new int[length];
 92         this.pre_visited=new int[length];
 93         this.dis=new int[length];
 94         //初始化dis数组
 95         Arrays.fill(dis, 65535);
 96         this.dis[index]=0;//设置出发顶点的访问距离为0
 97         this.already_arr[index]=1;//设置出发顶点为访问过
 98     }
 99     /**
100      * 判断index节点是否被访问过
101      * @param index
102      * @return如果访问过返回true，否则返回false
103      */
104     public boolean in(int index) {
105         return already_arr[index]==1;
106     }
107     /**
108      * 更新出发顶点到index顶点的距离
109      * @param index
110      * @param len
111      */
112     public void updateDis(int index,int len) {
113         dis[index]=len;
114     }
115     /**
116      * 更新pre节点的前驱结点为index顶点
117      * @param pre
118      * @param index
119      */
120     public void update(int pre,int index) {
121         pre_visited[pre]=index;
122     }
123     /**
124      * 返回出发顶点到index顶点的距离
125      * @param index
126      */
127     public int getDis(int index) {
128         return dis[index];
129     }
130     /**
131      * 继续选择并返回新的访问顶点，比如这里的G结束后，就是A点作为新的访问顶点
132      * @return
133      */
134     public int updateArr() {
135         int min=65535,index=0;
136         for(int i=0;i<already_arr.length;i++) {
137             if(already_arr[i]==0&&dis[i]<min) {
138                 min=dis[i];
139                 index=i;
140             }
141         }
142         //更新index 顶点被访问过
143         already_arr[index]=1;
144         return index;
145     }
146     
147     public void show() {
148         System.out.println("==========================================");
149         for (int i : already_arr) {
150             System.out.print(i+" ");
151         }
152         System.out.println();
153         System.out.println("==========================================");
154         for (int i : pre_visited) {
155             System.out.print(i+" ");
156         }
157         System.out.println();
158         System.out.println("==========================================");
159         for (int i : dis) {
160             System.out.print(i+" ");
161         }
162         System.out.println();
163         System.out.println("==========================================");
164         char[] vertex= {'A','B','C','D','E','F','G'};
165         int count =0;
166         for(int i:dis) {
167             if(i!=65535) {
168                 System.out.print(vertex[count]+"("+i+")");
169             }else {
170                 System.out.println("N");
171             }
172             count++;
173         }
174         System.out.println();
175     }
176 }

9.佛洛依德算法(Floyd)

　　9.1 佛洛依德算法介绍

　　（1）用于寻找给定的加权图中顶点间最短路径的算法；

　　（2）佛洛依德算法计算图中各个顶点之间的最短路径；

　　（3）迪杰斯特拉算法用于计算图中某个顶点到其他顶点的最短路径；

　　（4）迪杰斯特拉算法与佛洛依德算法的比较：迪杰斯特拉算法通过选定的被访问顶点，求出出发顶点到其他顶点的最短路径；佛洛依德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看作被访问顶点，求出每一个顶点到其他顶点的最短路径；

　　9.2 算法分析

　　（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，是以同样的方式获得的；

　　9.3 源代码

 1 package com.atguigu.floyd;
 2 
 3 import java.util.Arrays;
 4 
 5 
 6 public class FloydAlgorithm {
 7 
 8     public static void main(String[] args) {
 9         //测试图是否创建成功
10         char[] vertex= {'A','B','C','D','E','F','G'};
11         //创建邻接矩阵
12         int[][] matrix= new int[vertex.length][vertex.length];
13         final int N=65535;
14         matrix[0]=new int[] {0,5,7,N,N,N,2};
15         matrix[1]=new int[] {5,0,N,9,N,N,3};
16         matrix[2]=new int[] {7,N,0,N,8,N,N};
17         matrix[3]=new int[] {N,9,N,0,N,4,N};
18         matrix[4]=new int[] {N,N,8,N,0,5,4};
19         matrix[5]=new int[] {N,N,N,4,5,0,6};
20         matrix[6]=new int[] {2,3,N,N,4,6,0};
21         //创建Graph对象
22         Graph graph=new Graph(vertex.length, matrix, vertex);
23         graph.floyd();
24         graph.show();
25     }
26 
27 }
28 class Graph{
29     private char[] vertex;//存放顶点的数组
30     private int[][] dis;//保存从各个顶点出发到其他顶点的距离，最后的结果保留在该数组
31     private int[][] pre;//保存到达目标点的前驱顶点
32     
33     /**
34      * 构造器
35      * @param length 大小
36      * @param matrix 邻接矩阵
37      * @param vertex 顶点数组
38      */
39     public Graph(int length,int[][] matrix,char[] vertex) {
40         this.vertex=vertex;
41         this.dis=matrix;
42         this.pre=new int[length][length];
43         //对pre数组初始化，注意存放的是前驱顶点的下标
44         for (int i = 0; i < length; i++) {
45             Arrays.fill(this.pre[i],i);
46         }
47     }
48     
49     //显示pre数组和dis数组
50     public void show() {
51         char[] vertex= {'A','B','C','D','E','F','G'};
52         
53         for (int k = 0; k < dis.length; k++) {
54             //先将pre数组输出的一行数组
55             for (int i = 0; i < dis.length; i++) {
56                 System.out.print(vertex[pre[k][i]]+" ");
57             }
58             System.out.println();
59             //输出dis数组的一行数据
60             for (int i = 0; i < dis.length; i++) {
61                 System.out.print("("+vertex[k]+"到"+vertex[i]+"的最短路径是"+dis[k][i]+")  ");
62             }
63             System.out.println();
64             System.out.println();
65         }
66     }
67     //佛洛依德算法
68     public void floyd() {
69         int len=0;//保存距离
70         //对中间顶点的遍历，k是中间顶点的下标
71         for (int k = 0; k < dis.length; k++) {
72             //从i顶点开始出发['A','B',"C'...]
73             for (int i = 0; i < dis.length; i++) {
74                 //到j顶点结束
75                 for (int j = 0; j < dis.length; j++) {
76                     len=dis[i][k]+dis[k][j];//求出从i顶点出发经过k中间顶点的距离，
77                     if(len<dis[i][j]){//如果len小于dis[i][j]
78                         dis[i][j]=len;//更新距离
79                         pre[i][j]=pre[k][j];//更新前驱节点
80                     }
81                 }
82             }
83         }
84     }
85 }

10.回溯算法

　　10.1 骑士周游问题的解决方法和思路

　　（1）创建棋盘chessBoard，是一个二维数组；

　　（2）将当前位置设置为已经访问，然后根据当前位置i，计算马还能走哪些位置，并放入到一个集合中(ArrayList)，最多有8个位置，没走一步，step+1；

　　（3）遍历ArrayList中存放的所有位置，看看哪个可以走通，走通就继续，走不通就回溯；

　　（4）判断马是否完成任务，使用step和应该走的步数比较，如果没有达到数量，则表示没有完成任务，将整个棋盘置0；

　　10.2 使用贪心算法对上述算法进行优化

　　（1）获取到当前位置，可以走的下一个位置的集合；

　　（2）需要对ps的下一步的所有的point的下一步的所有集合的个数进行非递减排序；

  1 package com.atguigu.horse;
  2 
  3 import java.awt.Point;
  4 import java.util.ArrayList;
  5 import java.util.Comparator;
  6 
  7 public class HorseChessBoard {
  8 
  9     private static int X;// 棋盘的列
 10     private static int Y;// 棋盘的行数
 11     //创建一个数组，标记棋盘的各个位置是否被访问过
 12     private static boolean visited[];
 13     //使用一个属性，标记是否棋盘的所有位置都被访问过
 14     private static boolean finished;//如果为true，表示成功
 15     public static void main(String[] args) {
 16         // 测试
 17         X=8;
 18         Y=8;
 19         int row=1;//马初始位置的行，从1开始编号
 20         int column=1;//马初始位置的列，从1开始编号
 21         //创建棋盘
 22         int[][] chessboard=new int[X][Y];
 23         visited=new boolean[X*Y];//初始值是false
 24         long start=System.currentTimeMillis();
 25         traversalChessboard(chessboard, row-1, column-1,1);
 26         long end=System.currentTimeMillis();
 27         System.out.println(end-start);
 28         
 29         //输出棋盘的最后情况
 30         for (int[] rows:chessboard) {
 31             for(int step:rows) {
 32                 System.out.print(step+"	");
 33             }
 34             System.out.println();
 35         }
 36 
 37     }
 38     /**
 39      * 完成骑士周游问题的算法
 40      * @param chessboard 棋盘
 41      * @param row 马当前位置的行 从0开始
 42      * @param column 马当前位置的列 从0开始
 43      * @param step 是第几步，初始位置就是第1步
 44      */
 45     public static void traversalChessboard(int [][] chessboard,int row,int column,int step) {
 46         chessboard[row][column]=step;
 47         visited[row*X+column]=true;//标记该位置已经被访问
 48         //获取当前位置可以走的下一个位置的集合
 49         ArrayList<Point> ps=next(new Point(column,row));
 50         //对ps进行排序，排序的规则就是对ps的所有的Point对象的下一步的位置的数目，进行非递减排序
 51         sort(ps);
 52         //遍历集合
 53         while (!ps.isEmpty())  {
 54             Point p=ps.remove(0);
 55             //如果当前的p没有被访问过
 56             if(!visited[p.y*X+p.x]) {
 57                 traversalChessboard(chessboard, p.y, p.x, step+1);
 58             }
 59         }
 60         //判断马是否完成了任务，使用step和应该走的步数进行比较；
 61         //如果没有到达数量，就表示没有完成任务
 62         if(step<X*Y && !finished) {//如果访问不成功
 63             chessboard[row][column]=0;
 64             visited[row*X+column]=false;
 65         }else {
 66             finished=true;
 67         }
 68     }
 69 
 70     /**
 71      * 根据当前位置(Point对象)，计算马还能走哪些位置(Point),并放入到一个集合中(ArrayList)，总共有8个位置
 72      * 
 73      * @param curPoint
 74      * @return
 75      */
 76     public static ArrayList<Point> next(Point curPoint) {
 77         // 创建一个ArrayList
 78         ArrayList<Point> ps = new ArrayList<Point>();
 79         // 创建一个Point
 80         Point p1 = new Point();
 81         // 表示马可以走5这个位置
 82         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
 83             ps.add(new Point(p1));
 84         }
 85         // 表示马可以走6这个位置
 86         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
 87             ps.add(new Point(p1));
 88         }
 89         // 表示马可以走7这个位置
 90         if ((p1.x = curPoint.x + 1) <  X && (p1.y = curPoint.y - 2) >= 0) {
 91             ps.add(new Point(p1));
 92         }
 93         // 表示马可以走0这个位置
 94         if ((p1.x = curPoint.x + 2) <  X && (p1.y = curPoint.y - 1) >= 0) {
 95             ps.add(new Point(p1));
 96         }
 97         // 表示马可以走1这个位置
 98         if ((p1.x = curPoint.x + 2) <  X && (p1.y = curPoint.y + 1) <  Y) {
 99             ps.add(new Point(p1));
100         }
101         // 表示马可以走2这个位置
102         if ((p1.x = curPoint.x + 1) <  X && (p1.y = curPoint.y + 2) <  Y) {
103             ps.add(new Point(p1));
104         }
105         // 表示马可以走3这个位置
106         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) <  Y) {
107             ps.add(new Point(p1));
108         }
109         // 表示马可以走4这个位置
110         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) <  Y) {
111             ps.add(new Point(p1));
112         }
113          return ps;
114     }
115     //根据当前这一步的所有的下一步的选择位置，进行非递减排序
116     //减少回溯的可能
117     public static void sort(ArrayList<Point> ps) {
118         ps.sort(new Comparator<Point>() {
119 
120             @Override
121             public int compare(Point o1, Point o2) {
122                 //获取o1的下一步所有位置的个数
123                 int count1=next(o1).size();
124                 int count2=next(o2).size();
125                 if(count1<count2) {
126                     return -1;
127                 }else if(count1==count2) {
128                     return 0;
129                 }else {
130                     return 1;
131                 }
132             }
133         });
134     }
135 }

D16-常用十种算法[Java数据结构和算法]

1.二分查找（非递归）代码实现

2.分治算法（Divide-and Conquer）

2.1 分治算法的思想

2.2 分治算法的基本步骤

2.3 分治算法的最佳实现-汉诺塔问题

3.动态规划(Dynamic Programming)

3.1 动态规划算法基本介绍

3.2 动态规划算法的最佳实践-背包问题

4.KMP算法

4.1暴力匹配算法

4.2 KMP算法(Knuth-Morris-Pratt)

5.贪心算法

5.1 介绍

5.2 源代码-集合覆盖问题

6 普里姆算法(Prim)

6.1 最小生成树（Minimum Cost Spanning Tree,MST）

6.2 普里姆算法介绍

6.3 普里姆算法的应用实例

7.克鲁斯卡尔算法(Kruskal)

7.1克鲁斯卡尔算法介绍

7.2 源代码

8.迪杰斯特拉算法(Dijkstra)

8.1 迪杰斯特拉算法介绍

8.2 迪杰斯特拉算法过程

8.3 源代码

9.佛洛依德算法(Floyd)

9.1 佛洛依德算法介绍

9.2 算法分析

9.3 源代码

10.回溯算法

10.1 骑士周游问题的解决方法和思路

10.2 使用贪心算法对上述算法进行优化

　　2.1 分治算法的思想

　　2.2 分治算法的基本步骤

　　2.3 分治算法的最佳实现-汉诺塔问题

　　3.1 动态规划算法基本介绍

　　3.2 动态规划算法的最佳实践-背包问题

　　4.1暴力匹配算法

　　4.2 KMP算法(Knuth-Morris-Pratt)

　　5.1　介绍

　　5.2 源代码-集合覆盖问题

　　6.1 最小生成树（Minimum Cost Spanning Tree,MST）

　　6.2 普里姆算法介绍

　　6.3 普里姆算法的应用实例

　　7.1克鲁斯卡尔算法介绍

　　7.2 源代码

　　8.1 迪杰斯特拉算法介绍

　　8.2 迪杰斯特拉算法过程

　　8.3 源代码

　　9.1 佛洛依德算法介绍

　　9.2 算法分析

　　9.3 源代码

　　10.1 骑士周游问题的解决方法和思路

　　10.2 使用贪心算法对上述算法进行优化