1.贪心算法
1.电台覆盖区域求最优解问题
题目：假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号
| 广播台 | 覆盖地区 |
|---|---|
| K1 | “北京”, “上海”, “天津” |
| K2 | “广州”, “北京”, “深圳” |
| K3 | “成都”, “上海”, “杭州” |
| K4 | “上海”, “天津” |
| K5 | “杭州”, “大连” |
/**
* @author 缪广亮
* @version 1.0
*/
public class GreedyAlgorithm {
public static void main(String[] args) {
// 创建广播电台map
HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
// 将各个电台放入到broadcasts
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("大连");
// 将各电台放入map
broadcasts.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<>();
for (HashSet<String> areas : broadcasts.values())
// broadcasts.values()返回的是values的一个集合，而每一个value都是一个集合用addAll
allAreas.addAll(areas);
// 存放选择的电台集合
ArrayList<String> selects = new ArrayList<>();
// 临时的集合，在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
HashSet<String> tempSet = new HashSet<>();
// 定义maxKey，保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
// 如果maxKey不为null，则就会加入到selects
String maxKey = null;
while (allAreas.size() > 0) {//allAreas不为0，则表示还没有覆盖到所有地区
// 每次while将maxKey置空
maxKey=null;
for (String key : broadcasts.keySet()) {
// 每次for将tempSet清空
tempSet.clear();
// 当前这个key能够覆盖的地区
HashSet<String> areas = broadcasts.get(key);
tempSet.addAll(areas);
// retainAll方法是求出tempSet和allAreas集合的交集，交集会赋给tempSet
tempSet.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不为空，就应该将maxKey加入到selects
if (maxKey!=null){
selects.add(maxKey);
// 将maxKey指向的广播电台覆盖的地区，从allAreas移除
allAreas.removeAll(broadcasts.get(maxKey));
}
}
System.out.println("选择的结果："+selects);
}
}
2.普利姆算法（prim）
应用场景-修路问题
最小生成树
修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称 MST。 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
- N 个顶点，一定有 N-1 条边
- 包含全部顶点
- N-1 条边都在图中
- 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法
普利姆算法的图解分析：
1.从A顶点开始处理<A,G>
A-C[7] A-G[2] A-B[5]=>
2.<A,G>开始，将A和G 顶点和他们相邻的还没有访问的顶点进行处理=》<A,G,B> A-C[7] A-B[5] G-B[3] G-E[4] G-F[6]
3.<A,G,B>开始，将A,G,B顶点和他们相邻的还没有访问的顶点进行处理=<A,G,B,E> A-CI7] G-E[4] G-F[6] B-D[9]
......
4.{A,G,B,E}->F//第4次大循环 ，对应边<E,F>权值:5
5.{A,G,B,E,F}->D//第5次大循环，对应边<F,D>权值: 4
6.[A,G,B,E,F,D}->C//第6次大循环，对应边<A,C权值: 7
/**
* @author 缪广亮
* @version 1.0
*/
public class PrimAlgorithm {
public static void main(String[] args) {
char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
int vertex = 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 graph = new MGraph(vertex);
MinTree minTree = new MinTree();
minTree.createGraph(graph, vertex, data, weight);
minTree.showGraph(graph);
minTree.prim(graph,0);
}
}
//创建最小成树
class MinTree {
// 创建邻接矩阵
/**
* @param graph 图对象
* @param vertex 顶点个数
* @param data 各个顶点的值
* @param weight 邻接矩阵
*/
public void createGraph(MGraph graph, int vertex, char[] data, int[][] weight) {
for (int i = 0; i < vertex; i++) {
graph.data[i] = data[i];
for (int j = 0; j < vertex; j++) {
graph.weight[i][j] = weight[i][j];
}
}
}
// prim算法
/**
* @param graph 图
* @param v 从第几个顶点开始
*/
public void prim(MGraph graph, int v) {
// 标记顶点是否已经被访问过
int[] isVisited = new int[graph.vertex];
// 将该数组初始化
// 将当前这个顶点标记为已访问
isVisited[v] = 1;
// h1和h2记录两个顶点的下标
int h1 = -1;
int h2 = -1;
int minWeight = 10000;//先将该值初始化成大值，在后面遍历会被替换
for (int k = 1; k < graph.vertex; k++) {//k从1开始，因为prim算法是graph.vertex-1条边
// 这个是确定每一次生成的子图，哪个顶点和这次遍历的结点距离最近
for (int i = 0; i < graph.vertex; i++) {//i结点表示被访问过的结点
for (int j = 0; j < graph.vertex; j++) {//j结点表示还没有访问过的结点
if (isVisited[i] == 1 && isVisited[j] == 0 && graph.weight[i][j] < minWeight) {
// 替换minWeight(寻找已经访问过的结点和未访问过的节点间的权值最小的边 )
minWeight = graph.weight[i][j];
//记录最小值的下标i、j
h1 = i;
h2 = j;
}
}
}
// 找到一条边是最小
System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值：" + minWeight);
// 将当前这个结点标记为已访问
isVisited[h2] = 1;
// minWeight重置
minWeight = 10000;
}
}
// 显示邻接矩阵
public void showGraph(MGraph graph) {
for (int[] link : graph.weight) {
System.out.println(Arrays.toString(link));
}
}
}
class MGraph {
int vertex;
char[] data;//存放结点的数组
int[][] weight;//存放边，邻接矩阵
public MGraph(int vertex) {
this.vertex = vertex;
data = new char[vertex];
weight = new int[vertex][vertex];
}
}
3.克鲁斯卡尔(kruskal)
基本介绍
克鲁斯卡尔（Kruskal）算法，求加权连通图最小生成树的算法
基本思想：按权值从小到大顺序选择n-1条边，保证n-1条边不够成回路
具体做法：先构造一个只有n顶点的森林，然后按权值从小到大连通网中选择边加入森林中，保证森林不产生回路，直到森林变为一棵树为止
/**
* @author 缪广亮
* @version 1.0
*/
@SuppressWarnings({"all"})
public class KruskalCase {
private int edgeNum;
private char[] vertex;
private int[][] matrix;
// 使用INF表示两个顶点不能联通
private static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
char[] vertex = new char[]{'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 kruskalCase = new KruskalCase(vertex, matrix);
kruskalCase.printMatrix();
EData[] edges = kruskalCase.getEdges();
kruskalCase.sortEdges(edges);
System.out.println(Arrays.toString(edges));
kruskalCase.kruskal();
}
public KruskalCase(char[] vertex, int[][] matrix) {
// 初始化顶点和边的个数
int vLen = vertex.length;
// 初始化顶点，复制拷贝的方式
this.vertex = new char[vLen];
for (int i = 0; i < vLen; i++) {
this.vertex[i] = vertex[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 printMatrix() {
System.out.println("邻接矩阵为：\n");
for (int i = 0; i < vertex.length; i++) {
for (int j = 0; j < vertex.length; j++) {
System.out.printf("%12d", matrix[i][j]);
}
System.out.println();
}
}
public void kruskal(){
int index=0;//表示最后结果数组的索引
// 用于保存“已有最小生成树”中每个顶点在最小生成树中的终点
int[] ends=new int[edgeNum];
// 创建结果数组，保存最后的最小生成树
EData[] res = new EData[edgeNum];
// 获取图中所有的边集合
EData[] edges = getEdges();
// 按照边的权值大小进行排序
sortEdges(edges);
// 遍历edges数组，将边添加到最小生成树中时，判断准备加入的边是否形成了回路
for (int i = 0; i < edgeNum; i++) {
// 获取到第i条边的第一个顶点（起点）
int p1=getPosition(edges[i].start);//p1=4
// 获取到第i条边的第二个顶点（终点）
int p2=getPosition(edges[i].end);//p2=5
// 获取p1这个顶点在已有最小生成树中的终点
int m=getEnd(ends,p1);//m=4
// 获取p2这个顶点在已有最小生成树中的终点
int n=getEnd(ends,p2);//n=5
// 是否构成回路
if (m!=n) {//没有构成回路
ends[m] = n;//设置m在“已有最小生成树”中的终点
res[index++] = edges[i];//有一条边加入到res数组
}
}
// 统计并打印最小生成树，输出res
System.out.println("最小生成树为");
for (int i = 0; i < index; i++) {
System.out.print(res[i]+" ");
}
}
/**
* 对边进行排序处理，冒泡排序
*
* @param edges 边的集合
*/
public 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 顶点的值，比如'A'
* @return 返回ch顶点对应的下标，否则-1
*/
public int getPosition(char ch) {
for (int i = 0; i < vertex.length; i++) {
if (vertex[i] == ch)
return i;
}
return -1;
}
/**
* 获取图中的边，放到EData[]数组中，后面我们需要遍历该数组
* 通过matrix邻接矩阵来获取
*
* @return EData[]类型的数组
*/
public EData[] getEdges() {
int index = 0;
EData[] edges = new EData[edgeNum];
for (int i = 0; i < vertex.length; i++) {
for (int j = i + 1; j < vertex.length; j++) {
if (matrix[i][j] != INF)
edges[index++] = new EData(vertex[i], vertex[j], matrix[i][j]);
}
}
return edges;
}
/**
* 获取下标为i的顶点的终点，用于后面判断两个顶点的终点是否相同
* @param ends：数组就是记录了各个顶点对应的终点是哪个，ends数组是在遍历过程中，逐步形成
* @param i：表示传入的顶点对应的下标
* @return 返回的就是下标为i的这个顶点对应的终点的下标
*/
public int getEnd(int[] ends,int i){
while (ends[i]!=0)
i=ends[i];
return i;
}
}
//创建类EData，他的对象实例就表示一条边
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 "EData{" +
"start=" + start +
", end=" + end +
", weight=" + weight +
'}';
}
}