算法之广度优先,深度优先,拓扑,贪心,并查集

2024-06-22 16:58

本文主要是介绍算法之广度优先,深度优先,拓扑,贪心,并查集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1 图算法
    • 1.1 广度优先搜索
    • 1.2 深度优先搜索
    • 1.3 拓扑排序
    • 1.4 贪心算法
      • 1.4.1 定义
      • 1.4.2 示例
    • 1.5 并查集(不相交集合数据结构)
      • 1.5.1 并查集讲解
      • 1.5.2 Kruskal算法
      • 1.5.3 Prim算法
    • 1.8 Bellman-Ford算法

1 图算法

地图数据常常可以用图(Graph)这类数据结构表示,那么在图结构中常用的搜索算法也可以应用到路径规划中。

首先是两种针对无权图的基本图搜索算法:深度优先搜索(Depth First Search, DFS)、广度优先搜索(Breadth First Search, BFS)。它们的区别在于openlist(后面介绍)所选用的数据结构类型不同,前者使用栈,后者使用队列;之后引入一种启发式搜索算法:贪婪最佳优先算法(Greedy Best First Search, GBFS),用来提高搜索效率,但是不能确保找到最优路径;最后介绍两种在路径规划中非常经典的算法:Dijkstra算法A*算法,前者是广度优先算法(BFS)在带权图中的扩展,后者则是在前者中加入启发函数得到的算法,兼顾效率和完备性
https://zhuanlan.zhihu.com/p/346666812?utm_medium=social&utm_oi=1096915858005323776

1.1 广度优先搜索

广度优先搜索算法(Breadth-First Search,BFS)是一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验法则算法。

广度优先搜索算法的基本算法之一,是用来保存多对多的关系的数据结构,相对于树一对多的关系更为复杂,所以难度也会比树结构难一点,图的存储一般有连接表表示跟链接矩阵表示,相比来说链接矩阵的方式更为常用,也就是用数组来存储。而广度优先搜索算法其实就是图的遍历过程,数组的遍历大家都会,数组的遍历按照下标的顺序来遍历的,而图的遍历也有自己的方式,图是多对多的关系,我们可以按照各个节点直接的关联关系来遍历他们,这样便衍生出来深度优先跟广度优先,广度优先是先访问与跟当前节点相关联的所有节点,而深度优先则是按照关联关系一层层的遍历。如下图:
在这里插入图片描述

public class BFS {  private LinkedList list=new LinkedList();  public void BFS(int[][] map){  boolean[] visited=new boolean[map.length];  for (int i = 0; i < visited.length; i++) {  if (!visited[i]) {  list.addLast(i);  while (!list.isEmpty()) {  //访问队列里面的第一个节点  int now=(Integer) list.removeFirst();  visited[now]=true;  // 将与该节点关联的且没有访问的节点加入到队列中。  for (int j = 0; j < visited.length; j++) {  if (map[now][j]==1&&!visited[j]) {  list.addLast(j);  }  }  }  }  }  }  
}  

1.2 深度优先搜索

说完广度优先搜索后,我们来看图的另一种遍历形式,深度优先搜索算法,深度优先总是对刚发现的节点的出发边进行探索,直到该节点的所有出发边都被发现为止。一旦所有的出发边都被发现,搜索就回溯到前驱结点,来搜索前驱结点的出发边。反复进行直到全部遍历。我们用递归两种方式进行实现,其实归根到底递归也是栈实现的。

递归实现:

public class DFS {  private boolean[] visited;  public void dfs(int[][]map){  visited=new boolean[map.length];  for (int i = 0; i < visited.length; i++) {  if (!visited[i]) {  core(map, i);  }  }  }  public void core(int[][]map,int node){  System.out.println(node);  visited[node]=true;  for (int i = 0; i < visited.length; i++) {  if (map[node][i]==1&&!visited[i]) {  core(map,i);  }  }  }  
}

栈实现:

private LinkedList list=new LinkedList();  private boolean[] visited;  public void dfs(int[][] map){  visited=new boolean[map.length];  for (int i = 0; i < visited.length; i++) {  if (!visited[i]) {  list.addLast(i);  while (!list.isEmpty()) {  int now=(Integer) list.getLast();  visited[now]=true;  System.out.println(now);  int link=getlink(map, now);  if (link!=-1) {  list.add(link);  }else {  list.removeLast();  }  }  }  }  }  public int getlink(int[][]map,int node){  for (int i = 0; i < map.length; i++) {  if (map[node][i]==1&&!visited[node]) {  return i;  }  }  return -1;  }  

1.3 拓扑排序

拓扑排序是图中所有节点的一种线性次序,首先拓扑排序是对有向无环图来说的,如果不满足这个条件则无法拓扑排序,拓扑排序就是遵循一定的规则对节点的排序,规则就是假设在图中有一条边是从a节点出发指向b节点,则在拓扑排序中b节点不可能排在a的前面。其实就是一直寻找入度为0的节点。我们也可以理解成b的完成必须依赖a的完成,a没有完成则b无法进行,其实这样理解的话我们先前说的线性规划也是一种拓扑排序,像我们平时的起床过程也是一种拓扑排序。
在这里插入图片描述
拓扑排序的实现:

public class TopoSort {        public void topsort(int[][]map){  int[] into=new int[map.length];  for (int i = 0; i < map.length; i++) {  for (int j = 0; j < map.length; j++) {  if (map[i][j]==1) {  into[j]++;  }  }  }  for (int i = 0; i < into.length; i++) {  int j=0;  while (into[j]!=0) {  j++;  if (j>into.length) {  return;  }  }  System.out.println(j);  into[j]=-1;  for (int k = 0; k < into.length; k++) {  if (map[j][k]==1) {  into[k]--;  }  }                            }                      }  

1.4 贪心算法

1.4.1 定义

贪心算法相比动态规划更简单,也更高效。它总是做出局部最优选择,希望这样可以得到全局的最优选择。所以这种方法不能保证得到最优解,但是很多问题却都可以用这种方法。

贪心算法是一种基于贪心策略的算法,它在每一步选择中都采取当前状态下最优选择,以期望最终得到全局最优解。贪心算法通常用于求解最优化问题,如最小生成树、最短路径、背包问题等。
贪心算法的基本思想是:每一步都选择当前最优解,不考虑未来的后果。这种贪心策略可能会导致局部最优解,但并不一定能得到全局最优解。因此,在使用贪心算法时,需要证明贪心策略的正确性,即证明每一步的最优解能够导致全局最优解。

以下是一个简单的贪心算法示例:
假设有一组硬币,面值分别为1、5、10、50、100元,现在需要用最少的硬币凑出总值为200元的钱数。使用贪心算法,每一步都选择当前面值最大的硬币,直到凑出总值为200元为止。
具体步骤如下:

  • 选择面值最大的硬币100元,剩余金额为100元;
  • 选择面值最大的硬币100元,剩余金额为0元;
  • 总共使用了2枚硬币,得到最优解。

在这个例子中,贪心算法得到了全局最优解,因为每一步选择的最优解都能够导致全局最优解。但是,对于其他问题,贪心算法可能会得到局部最优解,而不是全局最优解。因此,在使用贪心算法时,需要仔细分析问题,证明贪心策略的正确性。

1.4.2 示例

假设我们有n个活动,只有一个教室,求在这个教室中一天最多可以举办多少活动(同一时间只能举办一个活动)。下面给出的是活动的开始时间跟结束时间。
输入:按每个活动完成时间排序(升序),开始时间数组S,完成时间数组F
输出:表示最大活动数的数组{X1,X2,…Xn},其中Xi=0(没选择)或者1(选择)

活动序号(i)1234567891011
活动开始(Si)130535688212
活动结束(Fi)4567991011121416

动态规划:

public class DPActity {  public void actity(){  Scanner sc=new Scanner(System.in);  int[][] map=new int[25][25];  for (int i = 0; i < 11; i++) {  map[sc.nextInt()][sc.nextInt()]=1;  }  for(int i=1;i<map.length;i++){  for(int j=0;j<=i;j++){  if(map[j][i]==1){  map[0][i]=max(map[0][i-1], 1+map[0][j]);  }else{  map[0][i]=max(map[0][i-1],map[0][i]);  }  }  }  System.out.println(map[0][24]);  }  public int max(int a,int b){  if(a>b){  return a;  }else{  return b;  }  }  public static void main(String[] args) {  new DPActity().actity();  }  }  

虽然这样写的感觉代码也不多,但是如果我们用贪心的做法你会发现非常简单,而且好理解。因为我们的数值倒是按照结束时间排序的,所以一直选择结束时间最短的则获得最优解。在这里选择结束时间最早的活动就是我们的决策点。而贪心算法关键就是在选择决策点上。顺便一提像01背包问题不能用贪心算法来解但是分数 背包可以解决。

public void greedy(int[]s,int[]f){  int n=s.length;  int k=1;  for (int i = 2; i < n; i++) {  if (s[i]>=f[k]) {  k=i;  }  }  System.out.println(k);  }  

1.5 并查集(不相交集合数据结构)

1.5.1 并查集讲解

java中经典的数据结构基本都给实现好了,我们可以直接调用,但是并查集这种数据结构却没有很好的替代工具,在这里我们自己去实现并查集数据结构。首先我们先要去了解什么是并查集
并查集是一种非常经典常用的数据结构。像求连通子图跟我们下面要研究的最小生成树问题都会用到并查集。

  • 并查集:就是能够实现 若干个不相交集合,较快的合并判断元素所在集合的操作。
  • 不相交集合:一个不相交集合维护了一个不相交动态集合{s1,s2,s3……}我们用一个代表标示每一个集合,他是这个集合的成员。我们不关心哪个成员作为代表,仅关心2次查询这个集合时放回结果应该相同(如果我们不修改集合)。

并查集主要就有三个方法:

  • make-set(x):建立一个新集合唯一元素就是x,因为是不相交集合所以x不会出现在其他集合中
  • union(x,y):将包含xy的2个动态集合合并成一个新集合。
  • find-set(x):返回一个指针,这个指针指向包含x集合代表

这样说是不是有点懵,我们来看一个图。
在这里插入图片描述
上图两棵树就是一个不相交集合,a数的代表就是a而e树代表就是e,我们在a树上查找b则返回a而查找c也返回a说明b与c在同一结合上,而查找f返回e,说明b与e是在两个结合上,他们两个是不相交的。而union操作就是将两颗树合并成一棵树。

我们先给出一个一般的实现,数组表示不相交集合保存的各个集合的元素。初始化时:
在这里插入图片描述

每个元素都指向自己的父节点也就是自己。这种方式每个节点都指向自己的上一节点。而只有代表节点指向的是自己。所以我们根据这个来搜索代表节点。

public class Ufsarry {  private int[] node;  private int max;  public void makeset(int n){  node=new int[n+1];  max=n;  //所有的节点都是不相交集合,代表节点都指向自己。  for (int i = 0; i < node.length; i++) {  node[i]=i;  }  }  public int findset(int x){  while (x!=node[x]) {  x=node[x];  }  return x;  }  public void union(int x,int y){  node[x]=y;  }  
}  

下面我们要说的就是并查集优化按秩合并路径压缩。听着好像很高深,其实很哄人的。两张图就可以解释。
在这里插入图片描述
在这里插入图片描述
第一张图就是路径压缩,我们之前都是指向的上一节点,而压缩则是直接指向代表节点。
按秩合并则是我们外加一个属性来记录集合的秩。而秩多的则说明树比较高,我们将矮的树嫁接在高的树上,这样总的高度较小。而如果高度相同,则只需要将一个树嫁接过去,给他的秩加一即可。

public class Ufs {        private int[] father;  private int[] rank;  public void makeset(int x){  father[x]=x;  rank[x]=0;  }  public int findset(int x){  if (father[x]!=x) {  father[x]=findset(father[x]);  }  return father[x];  }  public void union(int x,int y){  x=findset(x);  y=findset(y);  if (x==y) {  return;  }else {  if (rank[x]>rank[y]) {  father[y]=x;  }else{  if (rank[x]==rank[y]) {  rank[y]++;  }  father[x]=y;  }  }  }    
}  

优化后的代码并不比之前的代码复杂。我们这里是用的数组来实现的,当然也可以用链表来实现。我们下面要说的Kruskal算法的效率就要看,我们写的并查集的实现。而按秩合并与路径压缩是目前已知渐进时间最快的Kruskal算法实现方式。

1.5.2 Kruskal算法

说完并查集我们接着再来看这个Kruskal算法(克鲁斯卡尔算法)
什么是最小生成树呢,很形象的一个形容就是铺自来水管道,一个村庄有很多的农舍,其实这个村庄我们可以看成一个图,而农舍就是图上的每个节点,节点之间有很多的路径,而铺自来水管道目的就是为了让每家都能用上自来水,而至于自来水怎么铺就不关心了,而铺管子的人就会想如何才能最节省材料,那么最省材料的一条路径就是我们这个图的最小生成树。
而如何去构建一个最小生成树呢?这个就用到了我们之前说的贪心策略。 这里的觉得点就是一直寻找安全边,所以构建最小生成树的过程可以描述成, 循环一直寻找安全边加入到树中,直到树中包含所有节点

什么是安全边?

安全边的定义就是假设集合A是我们的最小生成树的子集,每一步都是选择一条边是A的还是最小生成树的子集,则那条边就是安全边

根据安全边选择策略不同有两种最短路径算法,分别是Kruskal算法prim算法。我们先来说Kruskal算法。首先我们先看一下图

在这里插入图片描述
在这里插入图片描述

大家可能已经看出来了,kruskal算法寻找安全边的方式,就是在所有的边中找最小的表,只要两个节点是两个不相交集合,就加入到最小生成树中,直到所有的节点都连接起来
大体伪代码描述:

  1. 循环所有的边;
  2. 构建一个最小优先队列;
  3. 构建一个并查集;
  4. 直到构建成最小生成树{ 从优先队列取出一个值,判断两个节点是不是不相交集合,是否加入到最小树中。 }
  5. 结束

javabean示例:

public class Bian implements Comparable<Bian>{  private int left;  private int right;  private int value;  public Bian(int i, int j, int k) {  this.left=i;  this.right=j;  this.value=k;  }此处省去getset方法@Override  public int compareTo(Bian o) {  if (this.getValue()>o.getValue()) {  return -1;  }  return 1;  }  
}  

并查集

class Ufs{  private int[] father;  private int[] rank;  public void makeset(int max) {  father = new int[max];  rank = new int[max];  for (int i = 0; i < father.length; i++) {  father[i] = i;  }  }  public void union(int x, int y) {  if (rank[x] > rank[y]) {  father[y] = x;  } else {  if (rank[x] == rank[y]) {  rank[y]++;  }  father[x] = y;  }  }  public int findset(int x) {  if (father[x] != x) {  father[x] = findset(father[x]);  }  return father[x];  }  
}  

核心代码其实就是一个循环过程,而之前的代码也全是在先前的准备工作

public void kruskal(int[][] map) {            Ufs ufs=new Ufs();  ufs.makeset(map.length);  ArrayList list=new ArrayList();  for (int i = 0; i < map.length; i++) {  for (int j = 0; j < map[i].length; j++) {  if(map[i][j]!=0){  Bian b=new Bian(i,j,map[i][j]);  list.add(b);  }  }  }  int max=0;  while(max<=map.length-1  && list.size()!=0 ){  Collections.sort(list);  Bian b=(Bian) list.remove(0);  int x=b.getLeft();  int y=b.getRight();  if(ufs.findset(x)!=ufs.findset(y)){  ufs.union(x, y);  System.out.println("连接"+x+","+y+"路径长度为"+b.getValue());  max++;  }  }  }

1.5.3 Prim算法

prim算法是另一种最小生成树算法。他的安全边选择策略跟kruskal略微不同,这点我们可以通过一张图先来了解一下。
在这里插入图片描述

prim算法的安全边是从与当前生成树 相连接 的边中选择一条最短的一条,并且该边是应是生成树与生成树外一点的连接
所以我们prim算法用汉字描述的过程应为:

  1. 初始化
  2. 构造最小优先队列,将所有节点都加入到最小优先队列中,所有节点的key设置为无穷大,开始节点设置成0
  3. 循环,直到队列为空
    {取出key值最小的节点加入到生成树中,变量与key相连接的边,看是否属于树中的节点相连,如果不是且key值比队列中节点的key值小则更新队列中该节点的key值,最小优先队列排序}
  4. 结束

下面的代码就是按照刚才的过程实现的,有很多需要优化的地方,当然算法还需要根据具体的题目,选择最好的写法,这里只是给出思想。

public class Prim {    private int MAX=1000;  private int NULL=-1;  public void prim(int[][]map){  Node[] nodes=new Node[map.length];  ArrayList list=new ArrayList();  for (int i = 1; i < map.length; i++) {  list.add(new Node(i, NULL, MAX));  }  list.add(new Node(0,NULL,0));  while(!list.isEmpty()){  Collections.sort(list);  Node n=(Node) list.remove(1);  System.out.println(n.getValue()+","+n.getLink()+","+n.getKey());  nodes[n.getValue()]=n;  for (int i = 0; i < map.length; i++) {  if(map[n.getValue()][i]!=0&&nodes[i]==null){  for (Object o : list) {  Node node=(Node) o;  if(node.getKey()==i&&map[n.getLink()][i]<node.getValue()){  node.setLink(n.getValue());  node.setKey(map[n.getLink()][i]);  }  }  }  }  }  }  
}  
class Node implements Comparable<Node>{  private int value;  private int link;  private int key;  省去getset方法public Node(int value, int link, int key) {  this.value = value;  this.link = link;  this.key = key;  }  @Override  public int compareTo(Node o) {  if (this.key>o.getKey()) {  return -1;  }  return 1;  }  }

1.8 Bellman-Ford算法

Bellman-Ford算法(音译贝尔曼福特算法),单源最短路径算法,它是图算法之一,前面说的贪心,图的遍历,动态规划都是它的基础,单源最短路径其实说的就是图中节点到节点的最短路径。就像我们使用百度地图从哪到哪一样,找出最近的距离,而单源最短路径问 题不只是两点之间的路径,他有很多的变形,像单目的地最短路径问题,单节点对最短路径问题,所有节点对最短路径问题,最短路径的最优子结构问题。

在介绍这类算法之前我们先规定节点的基本属性,我们规定节点都有一个key值key值记录的是 开始节点到本节点的最小距离,每个节点也都有一个p指针指向它的前驱节点。这里我们规定一个操作叫做松弛操作,我们的算法也是最终基于这个操作的。 松弛操作就是去更新key的值
在这里插入图片描述

节点Bkey值为8,表示从开始节点到B节点之前的最短估计距离是8,而节点Akey3,是说从开始节点到A节点最短估计是3,当我们发现这个边 时,从A到B的距离比较近,所以我们去更新B的key值,同时把B的前驱节点设置成A。这个过程就是松弛操作

我们说的Bellman-Ford算法是最简单的算法,就是从开始节点开始循环每一条边,对他进行松弛操作。最后得到的路径就是最短路径

public class BellmanFord {  private int[] rank;  private int max=1000;  public boolean bellmanford(int[][]map,int start,int end){  init(map.length, start);  for (int i = 0; i < map.length; i++) {  for (int j = 0; j < map[i].length; j++) {  if (map[i][j]!=0) {  relex(i,j,map[i][j]);  }  }  }  for (int i = 0; i < map.length; i++) {  for (int j = 0; j < map.length; j++) {  if (rank[j]>rank[i]+map[i][j]) {  return false;  }  }            }  return true;  }  public void init(int max,int start){  rank=new int[max];  for (int i = 0; i < rank.length; i++) {  rank[i]=max;  }  rank[start]=0;      }  public void relex(int s,int e,int length){  if(rank[e]>rank[s]+length){  rank[e]=rank[s]+length;  }          }  
}  

这篇关于算法之广度优先,深度优先,拓扑,贪心,并查集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1084874

相关文章

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Python与DeepSeek的深度融合实战

《Python与DeepSeek的深度融合实战》Python作为最受欢迎的编程语言之一,以其简洁易读的语法、丰富的库和广泛的应用场景,成为了无数开发者的首选,而DeepSeek,作为人工智能领域的新星... 目录一、python与DeepSeek的结合优势二、模型训练1. 数据准备2. 模型架构与参数设置3