Java常用算法

一、二分查找算法（非递归）

1、介绍

二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找。
二分查找法的运行时间为对数时间O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n 步，假设从[0,99]的
队列(100 个数，即 n=100)中寻到目标数 30，则需要查找步数为㏒₂100 , 即最多需要查找 7 次( 2^6 < 100 < 2^7)

步骤：

首先确定整个查找区间的中间位置 mid = （ left + right ）/ 2
用待查关键字值与中间位置的关键字值进行比较；
若相等，则查找成功
若大于，则在后（右）半个区域继续进行折半查找
若小于，则在前（左）半个区域继续进行折半查找
对确定的缩小区域再按折半公式，重复上述步骤。
最后，得到结果：要么查找成功，要么查找失败。折半查找的存储结构采用一维数组存放

优点：ASL≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。

缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不便利。

2、代码实现

package cn.jc.demo1;public class BinarySearchNoRecur {public static void main(String[] args) {int[] arr={-5,9,23,54,67,81,96,234};int result = binarySearch(arr, 81);if(result==-1){System.out.println("该数不存在");}else{System.out.println("该数的下标为："+result);}}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){left=mid+1;}else {right=mid-1;}}return -1;}
}

二、分治算法

1、介绍

分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或
相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
分治算法可以求解的一些经典问题

二分搜索
大整数乘法
棋盘覆盖
合并排序
快速排序
线性时间选择
最接近点对问题
循环赛日程表
汉诺塔

分治法在每一层递归上都有三个步骤：

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

分治(Divide-and-Conquer§)算法设计模式如下：
在这里插入图片描述

2、举例、代码实现

我们用经典的汉诺塔来举例：

有三根木桩，第一根上有n个盘子，最底层的盘子最大，最上层的盘子最小。汉诺塔问题就是将所有的盘子从第一根木桩开始，以第二根木桩为桥梁，全部搬到第三根木桩。

不过在搬动时，尚须遵守以下游戏规则：

1、每次只能从最上面移动一个盘子（乍一看，尼玛还真是栈）
2、任何盘子可以从任何木桩搬到其他木桩。
3、直径较小的盘子永远必须放在直径较大的盘子之上。

以下分析来自于：https://blog.csdn.net/da_jie/article/details/50866741

解决思路：

如果n=1，则将圆盘从A直接移动到C。
如果n=2，则：
1.将A上的n-1(等于1)个圆盘移到B上；
2.再将A上的一个圆盘移到C上；
3.最后将B上的n-1(等于1)个圆盘移到C上。
如果n=3，则：
A. 将A上的n-1(等于2，令其为n)个圆盘移到B(借助于C)，步骤如下：|
(1)将A上的n-1(等于1)个圆盘移到C上。
(2)将A上的一个圆盘移到B。
(3)将C上的n-1(等于1)个圆盘移到B。
B. 将A上的一个圆盘移到C。
C. 将B上的n-1(等于2，令其为n)个圆盘移到C(借助A)，步骤如下：
(1)将B上的n-1(等于1)个圆盘移到A。
(2)将B上的一个盘子移到C。
(3)将A上的n-1(等于1)个圆盘移到C。

到此，完成了三个圆盘的移动过程。

从上面分析可以看出，当n大于等于2时，移动的过程可分解为三个步骤：

第一步把A上的n-1个圆盘移到B上；
第二步把A上的一个圆盘移到C上；
第三步把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。

其实看到这里基本可以看出规律，就是用递归。

设盘数为n，

当n=1时，直接将盘从一号木桩转移到3号木桩

当n=2时，转移顺序：1号->2号，2号->3号，2号->3号

重点就是当n>=3时，将第n个盘和上面的n-1个盘分离，整体看起来就剩下2个部分：n，(1_{n-1)；后面递归就是将(1}n-1)分离成(1~n-2)和(n-1)…以此递归。

递归方法体面放四个参数，n(层数)，p1(一号桩)，p2(二号桩)，p3(三号桩)。每次递归(一号桩)是初始位置，(二号桩)为过渡位置，(三号桩)为目标位置

那么n>=3时递归顺序便是：

先创建方法：public static void hanoiTower(int n, char a, char b, char c){…}

(1)将(1_{n-1)分离放到(二号桩)，这里就是(1}n-1)在一号桩(初始位置)，二号桩就是目标位置

第一次递归代码:hanoiTower(n-1,a,c,b)，说到底，真正有用的参数只有3个，第1个、第2个、第4个；第三个参数就是打酱油的，你也可以认为是借助工具。

(2)将n转移到(三号桩)，按规矩，应该是hanoiTower(n-1,a,b,c)；但是这里写了第一是个死循环，第二，n转移没有借助b，所以默认他很自觉，自己到三号桩，直接

System.out.println(“从”+p1+“移动到”+p3);

(3)将(1~n-1)从(二号桩)转移到(三号桩),方法看懂(1)的这里自然懂

hanoiTower(n-1,b,a,c);

package cn.jc.demo1;public class Hanoitower {public static void main(String[] args) {hanoiTower(5, 'A', 'B', 'C');}//汉诺塔的移动的方法//使用分治算法//第一个参数为多少个盘，第二个参数为初始桩，第三个参数为过渡桩，第四个参数为目标桩public static void hanoiTower(int n, char a, char b, char c) {//如果只有一个盘if(n == 1) {System.out.println("第1个盘从 " + a + "->" + c);} else {//如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的一个盘（即第n个盘） 2. 上面的其余所有盘（n-1个）//1. 先把最上面的n-1个盘 A->B， 移动过程会使用到 chanoiTower(n - 1, a, c, b);//2. 把最下边的盘n A->CSystem.out.println("第" + n + "个盘从 " + a + "->" + c);//3. 把B塔的n-1 从 B->C , 移动过程使用到AhanoiTower(n - 1, b, a, c);}}
}

输出：

第1个盘从 A->C
第2个盘从 A->B
第1个盘从 C->B
第3个盘从 A->C
第1个盘从 B->A
第2个盘从 B->C
第1个盘从 A->C
第4个盘从 A->B
第1个盘从 C->B
第2个盘从 C->A
第1个盘从 B->A
第3个盘从 C->B
第1个盘从 A->C
第2个盘从 A->B
第1个盘从 C->B
第5个盘从 A->C
第1个盘从 B->A
第2个盘从 B->C
第1个盘从 A->C
第3个盘从 B->A
第1个盘从 C->B
第2个盘从 C->A
第1个盘从 B->A
第4个盘从 B->C
第1个盘从 A->C
第2个盘从 A->B
第1个盘从 C->B
第3个盘从 A->C
第1个盘从 B->A
第2个盘从 B->C
第1个盘从 A->C

三、动态规划

1、介绍

动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解
的处理算法
动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这
些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子
阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
动态规划可以通过填表的方式来逐步推进，得到最优解.

2、适用情况

能采用动态规划求解的问题的一般要具有3个性质：

（1）最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

（2）无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

3、基本步骤

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

图1 动态规划决策过程示意图

(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。

实际应用中可以按以下几个简化的步骤进行设计：

（1）分析最优解的性质，并刻画其结构特征。

（2）递归的定义最优解。

（3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值

（4）根据计算最优值时得到的信息，构造问题的最优解

4、举例、代码实现

背包问题：有一个背包，容量为 4 磅，现有如下物品
在这里插入图片描述

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

思路分析和图解
3) 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价
值最大。其中又分 01 背包和完全背包(完全背包指的是：每种物品都有无限件可用)

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

package com.atguigu.dynamic;public class KnapsackProblem {public static void main(String[] args) {// TODO Auto-generated method stubint[] 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];//初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是0for(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]];//把当前的情况记录到pathpath[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--;}}}

输出

0 0 0 0 0 
0 1500 1500 1500 1500 
0 1500 1500 1500 3000 
0 1500 1500 2000 3500 
============================
第3个商品放入到背包
第1个商品放入到背包

四、KMP算法

1、介绍

KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法
Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的出现位置.
KMP 方法算法就利用之前判断过信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间
参考资料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

2、案例

字符串匹配问题：：

有一个字符串 str1= “BBC ABCDAB ABCDABCDABDE”，和一个子串 str2=“ABCDABD”
现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1

3、暴力匹配

package com.atguigu.kmp;public class ViolenceMatch {public static void main(String[] args) {//测试暴力匹配算法String str1 = "BBC ABCDAB ABCDABCDABDE";String str2 = "ABCDABD";int index = violenceMatch(str1, str2);System.out.println("index=" + index);}// 暴力匹配算法实现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; // i索引指向s1int j = 0; // j索引指向s2while (i < s1Len && j < s2Len) {// 保证匹配时，不越界if(s1[i] == s2[j]) {//匹配oki++;j++;} else { //没有匹配成功//如果失配（即str1[i]! = str2[j]），令i = i - (j - 1)，j = 0。i = i - (j - 1);//i要跳过j-1，从i-（j-1）开始j = 0;//j要恢复}}//判断是否匹配成功if(j == s2Len) {return i - j;} else {return -1;}}}

4、KMP图解

1.首先，用 Str1 的第一个字符和 Str2 的第一个字符去比较，不符合，关键词向后移动一位
在这里插入图片描述
2、重复第一步，还是不符合，再后移

3、一直重复，直到 Str1 有一个字符与 Str2 的第一个字符符合为止

4、接着比较字符串和搜索词的下一个字符，还是符合。

5.遇到 Str1 有一个字符与 Str2 对应的字符不符合。
在这里插入图片描述
6.这时候，想到的是继续遍历 Str1 的下一个字符，重复第 1 步。(其实是很不明智的，因为此时BCD 已经比较过了，没有必要再做重复的工作，一个基本事实是，当空格与 D 不匹配时，你其实知道前面六个字符是”ABCDAB”。 KMP 算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。)
在这里插入图片描述
7.怎么做到把刚刚重复的步骤省略掉？可以对 Str2 计算出一张《部分匹配表》，这张表的产生在后面介绍

8.已知空格与 D 不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符 B 对应的”部分匹配值”为 2，因此按照下面的公式算出向后移动的位数：
移动位数 = 已匹配的字符数 - 对应的部分匹配值
因为 6 - 2 等于 4，所以将搜索词向后移动 4 位。

9.因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值” 为 0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移 2 位。
在这里插入图片描述
10.因为空格与 A 不匹配，继续后移一位。

11.逐位比较，直到发现 C 与 D 不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动 4 位。

12.逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动 7 位，这里就不再重复了。
在这里插入图片描述
13.介绍《部分匹配表》怎么产生的先介绍前缀，后缀是什么

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，
－”A”的前缀和后缀都为空集，共有元素的长度为 0；
－”AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；
－”ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－”ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－”ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；－”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为 2；
－”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为 0。

14.”部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动 4 位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。
在这里插入图片描述

5、KMP代码实现

package com.atguigu.kmp;import java.util.Arrays;public class KMPAlgorithm {public static void main(String[] args) {String str1 = "BBC ABCDAB ABCDABCDABDE";String str2 = "ABCDABD";//String str2 = "BBC";int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]System.out.println("next=" + Arrays.toString(next));int index = kmpSearch(str1, str2, next);System.out.println("index=" + index); // 15了}//写出我们的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];//因为相等的时候j都在++，当不相等了需要调整j的大小}if(str1.charAt(i) == str2.charAt(j)) {j++;}			if(j == str2.length()) {//j遍历完了就找到了return i - j + 1;}}return  -1;//如果没有就返回-1}//获取到一个字符串(子串) 的部分匹配值表public static  int[] kmpNext(String dest) {//创建一个next 数组保存部分匹配值int[] next = new int[dest.length()];next[0] = 0; //如果字符串是长度为1 部分匹配值就是0for(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) 满足时，部分匹配值就是+1if(dest.charAt(i) == dest.charAt(j)) {j++;}next[i] = j;}return next;}
}

输出：

next=[0, 0, 0, 0, 1, 2, 0]
index=15

五、贪心算法

1、介绍

贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而
希望能够导致结果是最好或者最优的算法
贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果

2、案例

假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让所有
的地区都可以接收到信号
思路分析:
如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假
设总的有 n 个广播台，则广播台的组合总共有
2ⁿ -1 个,假设每秒可以计算 10 个子集，如图:

使用贪婪算法，效率高:

目前并没有算法可以快速计算得到准备的值，使用贪婪算法，则可以得到非常接近的解，并且效率高。选择
策略上，因为需要覆盖全部地区的最小集合:
遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关
系）
将这个电台加入到一个集合中(比如 ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
重复第 1 步直到覆盖了全部的地区
分析的图解:

比如，在第一轮时，遍历所有的电台，求出每个广播台能够覆盖的地区（之前尚未被覆盖的地区）的个数，第一轮的时候分别是3,3,3,2,2。因为k2没有超过k1，所以选择k1，这时我们需要将待覆盖地区集合allAreas集合中k1已经覆盖到的地区去掉，即allAreas变成了{广州，深圳，成都，杭州，大连}，第二轮遍历开始，这时对比allAreas集合，每个广播台能够覆盖的地区（尚未被覆盖的地区）的个数分别为0,2,2,1,2,选择k2，再在allAreas集合中去掉k2新覆盖的两个地区，一直循环，直至allAreas为null

3、代码实现

package com.atguigu.greedy;import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;public class GreedyAlgorithm {public static void main(String[] args) {//创建广播电台,放入到MapHashMap<String,HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();//将各个电台放入到broadcastsHashSet<String> hashSet1 = new HashSet<String>();hashSet1.add("北京");hashSet1.add("上海");hashSet1.add("天津");HashSet<String> hashSet2 = new HashSet<String>();hashSet2.add("广州");hashSet2.add("北京");hashSet2.add("深圳");HashSet<String> hashSet3 = new HashSet<String>();hashSet3.add("成都");hashSet3.add("上海");hashSet3.add("杭州");HashSet<String> hashSet4 = new HashSet<String>();hashSet4.add("上海");hashSet4.add("天津");HashSet<String> hashSet5 = new HashSet<String>();hashSet5.add("杭州");hashSet5.add("大连");//加入到mapbroadcasts.put("K1", hashSet1);broadcasts.put("K2", hashSet2);broadcasts.put("K3", hashSet3);broadcasts.put("K4", hashSet4);broadcasts.put("K5", hashSet5);//allAreas 存放所有的地区HashSet<String> allAreas = new HashSet<String>();allAreas.add("北京");allAreas.add("上海");allAreas.add("天津");allAreas.add("广州");allAreas.add("深圳");allAreas.add("成都");allAreas.add("杭州");allAreas.add("大连");//创建ArrayList, 存放选择的电台集合ArrayList<String> selects = new ArrayList<String>();//定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集//还没覆盖的地区即图解中的allAreas，最初是全部，即均需要被覆盖，随着有地区被覆盖，allAreas逐渐变小HashSet<String> tempSet = new HashSet<String>();//定义给maxKey ， 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key//如果maxKey 不为null , 则会加入到 selectsString maxKey = null;while(allAreas.size() != 0) { // 如果allAreas 不为0, 则表示还没有覆盖到所有的地区//每进行一次while,需要maxKey = null;//遍历 broadcasts, 取出对应keyfor(String key : broadcasts.keySet()) {//每进行一次fortempSet.clear();//当前这个key能够覆盖的地区HashSet<String> areas = broadcasts.get(key);tempSet.addAll(areas);//求出tempSet和allAreas 集合的交集, 交集会赋给 tempSettempSet.retainAll(allAreas);//如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多//就需要重置maxKey// tempSet.size() >broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的if(tempSet.size() > 0 && (maxKey == null || tempSet.size() >broadcasts.get(maxKey).size())){maxKey = key;}}//maxKey != null, 就应该将maxKey 加入selectsif(maxKey != null) {selects.add(maxKey);//将maxKey指向的广播电台覆盖的地区，从 allAreas 去掉allAreas.removeAll(broadcasts.get(maxKey));}		}System.out.println("得到的选择结果是" + selects);//[K1,K2,K3,K5]		}
}

输出：

得到的选择结果是[K1, K2, K3, K5]

六、普利姆算法

1、介绍

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

2、案例

在这里插入图片描述

有胜利乡有7 个村庄(A, B, C, D, E, F, G) ，现在需要修路把 7 个村庄连通
各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
思路: 将 10 条边，连接即可，但是总的里程数不是最小.
正确的思路，就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少.

在这里插入图片描述

3、实现

设 G=(V,E)是连通网，T=(U,D)是最小生成树，V,U 是顶点集合，E,D 是边的集合
若从顶点 u 开始构造最小生成树，则从集合 V 中取出顶点 u 放入集合 U 中，标记顶点v 的visited[u]=1
若集合 U 中顶点 ui 与集合 V-U 中的顶点 vj 之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将
顶点 vj 加入集合 U 中，将边（ui,vj）加入集合 D 中，标记 visited[vj]=1
重复步骤②，直到 U 与 V 相等，即所有顶点都被标记为访问过，此时D 中有 n-1 条边
提示: 单独看步骤很难理解，我们通过代码来讲解，比较好理解.
图解普利姆算法

4、代码实现

package com.atguigu.prim;import java.util.Arrays;public class PrimAlgorithm {public static void main(String[] args) {//测试看看图是否创建okchar[] data = new char[]{'A','B','C','D','E','F','G'};int verxs = data.length;//邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通int [][]weight=new int[][]{{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 graph = new MGraph(verxs);//创建一个MinTree对象MinTree minTree = new MinTree();minTree.createGraph(graph, verxs, data, weight);//输出minTree.showGraph(graph);//测试普利姆算法minTree.prim(graph, 1);// }}//创建最小生成树->村庄的图
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];}}}//显示图的邻接矩阵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) {//visited[] 标记结点(顶点)是否被访问过int visited[] = new int[graph.verxs];//visited[] 默认元素的值都是0, 表示没有访问过
//		for(int i =0; i <graph.verxs; i++) {
//			visited[i] = 0;
//		}//把当前这个结点标记为已访问visited[v] = 1;//h1 和 h2 记录两个顶点的下标int h1 = -1;int h2 = -1;int minWeight = 10000; //将 minWeight 初始成一个大数，后面在遍历过程中，会被替换for(int k = 1; k < graph.verxs; k++) {//因为有 graph.verxs顶点，普利姆算法结束后，有 graph.verxs-1边//这个是确定每一次生成的子图 ，和哪个结点的距离最近for(int i = 0; i < graph.verxs; i++) {// i结点表示被访问过的结点for(int j = 0; j< graph.verxs;j++) {//j结点表示还没有访问过的结点if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {//替换minWeight(寻找已经访问过的结点和未访问过的结点间的权值最小的边)minWeight = graph.weight[i][j];h1 = i;h2 = j;}}}//找到一条边是最小System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);//将当前这个结点标记为已经访问visited[h2] = 1;//minWeight 重新设置为最大值 10000minWeight = 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];}
}