二叉树
图
图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。结点也可以称为顶点。如图：
为什么要有图
1)线性表局限于一个直接前驱和一个直接后继的关系
2)树也只能有一个直接前驱也就是父节点
3)当我们需要表示多对多的关系时， 这里我们就用到了图
常用概念
1)顶点(vertex)
2)边(edge)
3)路径
4)无向图（如下图）
5)有向图
6)带权图
图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。
邻接矩阵
邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1….n个点。
0表示没直接连通，1表示直接连通
代码实现
分析 (1) 存储顶点String 使用 ArrayList (2) 保存矩阵 int[][] edges
public class Graph {/*** 存储顶点结合*/private ArrayList<String> vertexList;/*** 存储图对应的邻接矩阵*/private int[][] edges;/*** 表示边的数目*/private int numOfEdges;public Graph(int n) {edges = new int[n][n];vertexList = new ArrayList<>(n);numOfEdges = 0;}/*** 插入顶点* @param vertex*/public void insertVertex(String vertex){vertexList.add(vertex);}/*** 添加边* @param v1 表示点的下标,即第几个顶点，“A”-“B” “A”->0 "B" -> 1* @param v2 表示第二个顶点的下标* @param weight 0 or 1，0表示不直连，1表示直连*/public void insertEdge(int v1,int v2,int weight){edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}/*** 返回节点的数目* @return*/public int getNumOfVertex(){return vertexList.size();}/*** 返回边的数目* @return*/public int getNumOfEdges(){return numOfEdges;}/*** 返回节点i(下标)对应的数据0->"A" 1->"B"* @param i* @return*/public String getValueByIndex(int i){return vertexList.get(i);}/**** @param v1* @param v2* @return 返回v1和v2的权值*/public int getWeight(int v1,int v2){return edges[v1][v2];}/*** 显示图*/public void showGrap(){for(int[] link:edges){System.out.println(Arrays.toString(link));}}public static void main(String[] args) {// 测试一把图是否创建okint n = 5;String[] vertexValue = {"A","B","C","D","E"};//创建图对象Graph graph = new Graph(n);// 循环添加节点for(String vertex:vertexValue){graph.insertVertex(vertex);}//添加边//A-B A-C B-C B-D B-Egraph.insertEdge(0,1,1);graph.insertEdge(0,2,1);graph.insertEdge(1,2,1);graph.insertEdge(1,3,1);graph.insertEdge(1,4,1);//显示一把邻接矩阵graph.showGrap();}}// 显示结果[0, 1, 1, 0, 0][1, 0, 1, 1, 1][1, 1, 0, 0, 0][0, 1, 0, 0, 0][0, 1, 0, 0, 0]
邻接表
1）邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失.
2）邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成
图的遍历
深度优先(Depth First Search)
1)深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
2)我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
3)显然，深度优先搜索是一个递归的过程
步骤
1)访问初始结点v，并标记结点v为已访问。
2)查找结点v的第一个邻接结点w。
3)若w存在，则继续执行4，如果w不存在，则回到第1步，将从访问过的且仍有未被访问的邻接点开始(回溯)。
4)若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
5)查找结点w邻接结点的下一个邻接结点，转到步骤3。
package com.yj.graph;
import java.util.ArrayList;
import java.util.Arrays;
/**
* @Package: com.yj.graph
* @ClassName: Graph
* @Author: kyj
* @Description:
* @Date: 2021/6/6 21:14
*/
public class Graph {
/**
* 存储顶点结合
*/
private ArrayList<String> vertexList;
/**
* 存储图对应的邻接矩阵
*/
private int[][] edges;
/**
* 表示边的数目
*/
private int numOfEdges;
/**
* 定义节点是否被访问的数组
*/
private boolean[] isVisited ;
public static void main(String[] args) {
// 测试一把图是否创建ok
int n = 5;
String[] vertexValue = {"A","B","C","D","E"};
//创建图对象
Graph graph = new Graph(n);
// 循环添加节点
for(String vertex:vertexValue){
graph.insertVertex(vertex);
}
//添加边
//A-B A-C B-C B-D B-E
graph.insertEdge(0,1,1);
graph.insertEdge(0,2,1);
graph.insertEdge(1,2,1);
graph.insertEdge(1,3,1);
graph.insertEdge(1,4,1);
//显示一把邻接矩阵
graph.showGrap();
//深度优先遍历
System.out.println("深度优先遍历");
graph.dfs();
}
public Graph(int n) {
edges = new int[n][n];
vertexList = new ArrayList<>(n);
numOfEdges = 0;
isVisited = new boolean[n];
}
/**
* 插入顶点
* @param vertex
*/
public void insertVertex(String vertex){
vertexList.add(vertex);
}
/**
* 添加边
* @param v1 表示点的下标,即第几个顶点，“A”-“B” “A”->0 "B" -> 1
* @param v2 表示第二个顶点的下标
* @param weight 0 or 1，0表示不直连，1表示直连
*/
public void insertEdge(int v1,int v2,int weight){
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
/**
* 得到第一个邻接结点的下标
* @param index
* @return 如果存在就返回对应的下标，否则返回-1
*/
public int getFirstNeighbor(int index){
for(int j=0;j<vertexList.size();j++){
if(edges[index][j]>0){
return j;
}
}
return -1;
}
/**
* 上一结点深度遍历完了，从下一个结点开始：根据前一个邻接结点的下标来获取下一个邻接结点
* @return 如果存在就返回对应的下标，否则返回-1
*/
public int getNextNeighbor(int v1,int v2){
for(int j=v2+1;j<vertexList.size();j++){
if(edges[v1][j]>0){
return j;
}
}
return -1;
}
/**
* 深度优先遍历算法，遍历连通图
*/
public void dfs(boolean[] isVisited,int i){
//首先我们访问该结点,输出
System.out.println(getValueByIndex(i)+"->");
//将结点设置为已经访问
isVisited[i] = true;
int w = getFirstNeighbor(i);
//说明有
while (w !=-1){
if(!isVisited[w]){
dfs(isVisited,w);
}
//如果w节点已经被访问过了
w= getNextNeighbor(i,w);
}
}
// 对dfs进行一个重载，因为存在非连通图，遍历我们所有的结点，并进行dfs
public void dfs(){
// 遍历所有的结点，进行dfs
for(int i=0;i<getNumOfVertex();i++){
if(!isVisited[i]){
dfs(isVisited,i);
}
}
}
/**
* 返回节点的数目
* @return
*/
public int getNumOfVertex(){
return vertexList.size();
}
/**
* 返回边的数目
* @return
*/
public int getNumOfEdges(){
return numOfEdges;
}
/**
* 返回节点i(下标)对应的数据0->"A" 1->"B"
* @param i
* @return
*/
public String getValueByIndex(int i){
return vertexList.get(i);
}
/**
*
* @param v1
* @param v2
* @return 返回v1和v2的权值
*/
public int getWeight(int v1,int v2){
return edges[v1][v2];
}
/**
* 显示图
*/
public void showGrap(){
for(int[] link:edges){
System.out.println(Arrays.toString(link));
}
}
}
广度优先
类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点
步骤
1)访问初始结点v并标记结点v为已访问。
2)结点v入队列
3)当队列非空时，继续执行，否则算法结束。
4)出队列，取得队头结点u。
5)查找结点u的第一个邻接结点w。
6)若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
6.1 若结点w尚未被访问，则访问结点w并标记为已访问。
6.2 结点w入队列
6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。
//对一个结点进行广度优先遍历的算法
private void bfs(boolean[] isVisited,int i){
int u ; // 表示队列的头结点对应下标
int w ; //邻接结点
//队列，记录结点访问的顺序
LinkedList queue = new LinkedList();
//访问结点，输出结点信息
System.out.print(getValueByIndex(i)+"=>");
//标记为已访问
isVisited[i] = true;
//将结点加入队列
queue.addLast(i);
while (!queue.isEmpty()){
//取出队列的头结点下标
u = (Integer) queue.removeFirst();
//得到第一个邻接点的下标w
w = getFirstNeighbor(u);
while (w!=-1){
if(!isVisited[w]){
System.out.print(getValueByIndex(w)+"=>");
//标记已经访问
isVisited[w] = true;
//入队
queue.addLast(w);
}
// 以u为前驱点，找w后面的下一个邻接点
w = getNextNeighbor(u,w);
}
}
}
//遍历所有的结点，都进行广度优先
public void bfs(){
for(int i=0;i<getNumOfVertex();i++){
if(!isVisited[i]){
bfs(isVisited,i);
}
}
}
分治算法
分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
步骤
分治法在每一层递归上都有三个步骤：
1)分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
2)解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题尚硅谷Java数据结构和算法
3)合并：将各个子问题的解合并为原问题的解。
例题
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
思路分析:
如果是有一个盘， A->C
如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘
先把 最上面的盘 A->B
把最下边的盘 A->C
把B塔的所有盘 从 B->C
public class Hanoitower {
public static void main(String[] args) {
hanoiTower(3,'A','B','C');
}
//汉诺塔的移动方法
//使用分治算法
//题目是要把a柱子上所有盘移动到c柱
public static void hanoiTower(int num,char a,char b,char c){
//如果只有一个盘
if(num == 1){
System.out.println("第1个盘从"+a+"->"+c);
}else{
//如果我们有n>=2情况，我们总是可以看做是两个盘 1.最下面的盘 2.上面的盘
// 1.先把最上面的盘A->B,移动过程会使用c
hanoiTower(num-1,a,c,b);
// 2.把最下边的盘A->C
System.out.println("第"+num+"个盘从"+a+"->"+c);
// 把B盘的所有盘从B->C, 移动过程使用到a塔
hanoiTower(num-1,b,a,c);
}
}
}
动态规划
1)动态规划(DynamicProgramming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
2)动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
3)与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
4)动态规划可以通过填表的方式来逐步推进，得到最优解.
背包问题思路分析
算法的主要思想，利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们有下面的结果：
(1) v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是0<br /> (2) 当w[i]> j 时：v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略<br /> (3) 当j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} <br />
KMP算法
暴力匹配
1)如果当前字符匹配成功（即str1[i] == str2[j]），则i++，j++，继续匹配下一个字符
2)如果失配（即str1[i]! = str2[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。
3)用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间。(不可行!)
4)暴力匹配算法实现.
package com.yj.kmp;
/**
* @Package: com.yj.kmp
* @ClassName: ViolenceMatch
* @Author: kyj
* @Description:
* @Date: 2021/6/9 19:07
*/
public class ViolenceMatch {
public static void main(String[] args) {
String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
String str2 = "尚硅谷你尚硅你";
System.out.println(violenceMatch(str1,str2));
System.out.println(str1.indexOf(str2));
}
// 暴力匹配算法,返回开始时的下标，不匹配返回-1
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索引指向s1
int j = 0; // j指向s2
while (i < s1Len && j < s2Len) {
if (s1[i] == s2[j]) { //匹配ok
i++;
j++;
} else {
//匹配失败
i = i - j +1;
j = 0;
}
}
//判断是否匹配成功
if(j == s2Len){
return i-j;
}
return -1;
}
}
KMP算法
1)KMP是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法
2)Knuth-Morris-Pratt字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法.
3)KMP方法算法就利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间
4)参考资料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
KMP的算法流程：
假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
- 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。”
我们发现如果某个字符匹配成功，模式串首字符的位置保持不动，仅仅是i++、j++；如果匹配失配，i 不变（即 i 不回溯），模式串会跳过匹配过的next [j]个字符。整个算法最坏的情况是，当模式串首字符位于i - j的位置时才匹配成功，算法结束。
所以，如果文本串的长度为n，模式串的长度为m，那么匹配过程的时间复杂度为O(n)，算上计算next的O(m)时间，KMP的整体时间复杂度为O(m + n)。//优化过后的next 数组求法 void GetNextval(char* p, int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while (j < pLen - 1) { //p[k]表示前缀，p[j]表示后缀 if (k == -1 || p[j] == p[k]) { ++j; ++k; //较之前next数组求法，改动在下面4行 if (p[j] != p[k]) next[j] = k; //之前只有这一行 else //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]] next[j] = next[k]; } else { k = next[k]; } } }贪心算法
1)贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法
2)贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
案例
假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让所有的地区都可以接收到信号
| 广播台 | 覆盖地区 |
|---|---|
| K1 | “北京”, “上海”, “天津” |
| K2 | “广州”, “北京”, “深圳” |
| K3 | “成都”, “上海”, “杭州” |
| K4 | “上海”, “天津” |
| K5 | “杭州”, “大连” |
思路分析:
如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有
2ⁿ -1个,假设每秒可以计算10个子集， 如图:
| 广播台数量n | 子集总数2ⁿ | 需要的时间 |
|---|---|---|
| 5 | 32 | 3.2秒 |
| 10 | 1024 | 102.4秒 |
| 32 | 4294967296 | 13.6年 |
| 100 | 1.26*100³º | 4x10²³年 |
使用贪婪算法，效率高:
目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合:
1)遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系）
2)将这个电台加入到一个集合中(比如ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉（整个集合中都去掉）。
3)重复第1步直到覆盖了全部的地区
package com.yj.greedy;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
/**
* @Package: com.yj.greedy
* @ClassName: GreedyAlgorithm
* @Author: kyj
* @Description:
* @Date: 2021/6/9 20:38
*/
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<>(){{
add("广州");
add("北京");
add("深圳");
}};
HashSet<String> hashSet3= new HashSet<>(){{
add("成都");
add("上海");
add("杭州");
}};
HashSet<String> hashSet4= new HashSet<>(){{
add("上海");
add("天津");
}};
HashSet<String> hashSet5= new HashSet<>(){{
add("杭州");
add("大连");
}};
//加入到map
broadcasts.put("K1",hashSet1);
broadcasts.put("K2",hashSet2);
broadcasts.put("K3",hashSet3);
broadcasts.put("K4",hashSet4);
broadcasts.put("K5",hashSet5);
//adllAreas 存放所有的地区
HashSet<String> allAreas = new HashSet<>(){
{
add("北京");
add("上海");
add("天津");
add("广州");
add("深圳");
add("成都");
add("杭州");
add("大连");
}
};
//创建ArrayList,存放选择的电台集合
ArrayList<String> selects = new ArrayList<>();
//定义一个临时的集合，在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
HashSet<String> tempSet = new HashSet<>();
//定义maxKey,保存在一次遍历过程中，能够覆盖最多未覆盖的地区对应的电台key
//如果maxKey 不为null,则会加入到selects
String maxKey = null;
//arrAreas !=0 表示未覆盖掉所有区域
while (allAreas.size()!=0){
// 每进行一次while,需要
maxKey = null;
//遍历broadCasts,取出对应key
for(String key : broadcasts.keySet()){
tempSet.clear();
//当前这个key能够覆盖的区域
HashSet<String> areas = broadcasts.get(key);
tempSet.addAll(areas);
//求出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 != null ,就应该将maxKey 加入selects
if(maxKey !=null){
selects.add(maxKey);
// 将maxKey指向的广播电台覆盖的地区，从allAreas 去掉
allAreas.removeAll(broadcasts.get(maxKey));
}
}
System.out.println("得到的选择结果是："+selects.toString());
}
}
得到的选择结果是：[K1, K2, K3, K5]
回溯算法
使用深度优先遍历的方式，然后进行剪枝操作。
例题
1.给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(candidates,path,0,0,target,res);
return res;
}
private void dfs(int[] candidates,List<Integer> path,int start,int total,int target,List<List<Integer>> res){
if(total == target){
res.add(new ArrayList(path));
return;
}else if(total > target){ //剪枝
return;
}
for(int i=start;i<candidates.length;i++){
path.add(candidates[i]);
dfs(candidates,path,i,total+candidates[i],target,res);
path.remove(path.size()-1);
}
}
}
2.给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
List<Integer> path = new ArrayList<>();
dfs(root,0,targetSum,path,res);
return res;
}
private void dfs(TreeNode root,int cur,int targetSum,List<Integer> path,List<List<Integer>> res){
if(root == null) {
return;
}
path.add(root.val);
if(cur+root.val == targetSum&&root.left == null && root.right == null){
res.add(new ArrayList<>(path));
path.remove(path.size()-1);
return; //这里删除最后一个元素是因为避免下面两个迭代
}
dfs(root.left,cur+root.val,targetSum,path,res);
dfs(root.right,cur+root.val,targetSum,path,res);
path.remove(path.size()-1);
}
}
普里姆算法（Prim）
适合稠密网的最小生成树的算法，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图。
最小生成树
最小生成树(Minimum Cost Spanning Tree)，简称MST。
1)给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
2)N个顶点，一定有N-1条边
3)包含全部顶点
4)N-1条边都在图中
5)举例说明(如图:)
6)求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法
算法步骤
(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条边
package com.yj.prim;
import java.util.Arrays;
/**
* @Package: com.yj.prim
* @ClassName: PrimAlgorithm
* @Author: kyj
* @Description:
* @Date: 2021/6/10 20:55
*/
public class PrimAlgorithm {
public static void main(String[] args) {
//测试图是否创建成功
char[] 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 mGraph = new MGraph(verxs);
// 创建一个MinTree对象
MinTree minTree = new MinTree();
minTree.createGraph(mGraph, verxs, data, weight);
// 输出
minTree.showGraph(mGraph);
minTree.prim(mGraph,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 表示顶点是否被访问过,默认为0，表示未访问过
int[] visited = new int[graph.verxs];
//把当前结点标记为已访问
visited[v] = 1;
// h1 和 h2记录两个顶点的坐标
int h1 = -1;
int h2 = -1;
//将 minWeight 初始为一个大数，后面遍历过程中会被替换
int minWeight = 10000;
//生成n-1条边
for (int k = 1; k < graph.verxs; k++) {
// 确定每一次生成的子图，和哪个结点的距离最近
// i 表示被访问过的结点
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，寻找权值最小的边且未被访问的边
minWeight = graph.weight[i][j];
h1 = i;
h2 = j;
}
}
}
//找到一条边边是最小的且未被访问的
System.out.println("边<"+graph.data[h1]+","+graph.data[h2]+"> 权值："+minWeight);
// 将当前这个结点标记为已经访问
visited[h2] = 1;
// minWeight 重新设置为大数
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];
}
}
克鲁斯卡尔Kruskal算法
迪杰斯特拉Dijkstra算法
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
算法过程
设置出发顶点为v，顶点集合V{v1,v2,vi…}，v到V中各顶点的距离构成距离集合Dis，Dis{d1,d2,di…}，Dis集合记录着v到图中各顶点的距离(到自身可以看作0，v到vi距离对应为di)，另外为一个visited数组和前驱结点数组。
1)从Dis中选择值最小的di并移出Dis集合，同时移出V集合中对应的顶点vi，此时的v到vi即为最短路径
2)更新Dis集合，更新规则为：比较v到V集合中顶点的距离值，与v通过vi到V集合中顶点的距离值，保留值较小的一个(同时也应该更新顶点的前驱节点为vi，表明是通过vi到达的)
3)重复执行两步骤，直到最短路径顶点为目标顶点即可结束
场景题
迪杰斯特拉(Dijkstra)算法最佳应用-最短路径
1)战争时期，胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从G点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄
2)各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里
3)问：如何计算出G村庄到 其它各个村庄的最短距离?
4)如果从其它点出发到各个点的最短距离又是多少?
package com.yj.dijkstra;
import com.yj.graph.Graph;
import java.util.Arrays;
/**
* @Package: com.yj.dijkstra
* @ClassName: DijkstraAlgorithm
* @Author: kyj
* @Description:
* @Date: 2021/6/19 19:40
*/
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};
// 创建
MGraph graph = new MGraph(vertex,matrix);
//测试图的邻接矩阵是否ok
graph.showGraph();
graph.dsj(6);
graph.showDijkstraResult();
}
}
class VisitedVertex{
// 记录各个顶点是否访问过 1表示访问过，0未访问，会动态更新
public int[] already_arr;
// 每个下标对应的值为前一个顶点下标，会动态更新
public int[] pre_visited;
// 记录出发顶点到其他所有顶点的距离，比如G为出发点，就会记录G到其它顶点的距离，会动态更新
// 求的最短距离会存放到dis
public int[] dis;
/**
*
* @param length 顶点的个数
* @param index 出发顶点下标
*/
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);
dis[index] = 0; // 设置出发顶点到自己的距离为0
already_arr[index] = 1; //设置出发结点被访问过
}
/**
* 判断index顶点是否被访问过
* @param index
* @return 如果访问过，返回true
*/
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();
for(int i: pre_visited){
System.out.print(i + " ");
}
System.out.println();
for (int i: dis){
System.out.print(i+" ");
}
System.out.println();
}
}
class MGraph{
private char[] vertex; // 顶点数组
private int[][] matrix; //邻接矩阵
private VisitedVertex vv; //已经访问的顶点的集合
public MGraph(char[] vertex,int[][] matrix){
this.vertex = vertex;
this.matrix = matrix;
}
public void showGraph(){
for(int[] link: matrix){
System.out.println(Arrays.toString(link));
}
}
public void showDijkstraResult(){
vv.show();
}
/**
* dijkstra算法实现
* @param index
*/
public void dsj(int index){
vv = new VisitedVertex(vertex.length,index);
update(index);
for(int j=1;j<vertex.length;j++){
index = vv.updateArr();//选择并返回新的返回顶点
update(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比原先要小，则更新
if(!vv.in(j) && len < vv.getDis(j)){
vv.updatePre(j,index);
vv.updateDis(j,len);
}
}
}
}
弗洛伊德Floyd算法
1)和Dijkstra算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名
2)弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径
3)迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径。
4)弗洛伊德算法VS迪杰斯特拉算法：迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点的最短路径；弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。
分治法在每一层递分治法在每一层递归上都有三个步骤：1)分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题2)解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
尚硅谷Java数据结构和算法更多Java–大数据–前端–python人工智能-区块链资料下载，可访问百度：尚硅谷官网第355页3)合并：将各个子问题的解合并为原问题的解。归上都有三个步骤：1)分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题2)解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
尚硅谷Java数据结构和算法更多Java–大数据–前端–python人工智能-区块链资料下载，可访问百度：尚硅谷官网第355页3)合并：将各个子问题的解合并为原问题的解。分治法在每一层递归上都有三个步骤：1)分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题2)解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
尚硅谷Java数据结构和算法更多Java–大数据–前端–python人工智能-区块链资料下载，可访问百度：尚硅谷官网第355页3)合并：将各个子问题的解合并为原问题的解。分治法在每一层递归上都有三个步骤：1)分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题2)解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
尚硅谷Java数据结构和算法更多Java–大数据–前端–python人工智能-区块链资料下载，可访问百度：尚硅谷官网第355页3)合并：将各个子问题的解合并为原问题的解。
分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
若有收获，就点个赞吧
0 人点赞
