回溯算法之广度优先遍历

这篇具有很好参考价值的文章主要介绍了回溯算法之广度优先遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

迷宫问题

N叉树的层序遍历

 腐烂的橘子

单词接龙

 最小基因变化

 打开转盘锁


迷宫问题

假设有一个迷宫,里面有障碍物,迷宫用二维矩阵表示,标记为0的地方表示可以通过,标记为1的地方表示障碍物,不能通过。现在给一个迷宫出口,让你判断是否可以从入口进来之后,走出迷宫,每次可以向任意方向走。

步骤:

1.创建

        1.创建队列

        2.创建book

        3.创建方向矩阵

2.开始位置

        1.开始位置标记遍历过

        2.把开始坐标放到队列中

3.遍历队列

        1.得到队首元素

        2.如果和出口元素相同,范湖true

        3.搜索新的位置

                1.得到位置

                2.判断位置是否合法

                3.如果没有遍历过是通路-->放入队列,标记为1

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author KYF
 * @create 2023-06-03
 */
class pair{
    public int x;
    public int y;
    public pair(int x,int y){
        this.x=x;
        this.y=y;
    }
}
//0可以通过,1有障碍
public class Test {

     public static boolean dfs(int[][] mat,int startx,int starty,int endx,int endy){
         //队列保存搜索到的位置
         Queue<pair> posQ=new LinkedList<>();
         posQ.offer(new pair(startx,starty));
         int row=mat.length;
         int col=mat[0].length;
         int[][] book=new int[row][col];
          book[startx][starty]=1;
          posQ.offer(new pair(startx,starty));
         int[][] next={{0,1},{0,-1},{-1,0},{1,0}};
          //搜索  -->要把队列中的所有元素都搜索完
         while(!posQ.isEmpty()){
             pair curPos=posQ.poll();
             if(curPos.x==endx && curPos.y==endy)
                 return true;
             //搜索新的位置
             for (int i = 0; i < 4; i++) {
                 int nx=curPos.x+next[i][0];
                 int ny=curPos.y+next[i][1];

                 if(nx<0 || nx>=row || ny<0 || ny>=col){
                     continue;
                 }
                 //保存新的位置
                 if(book[nx][ny]==0  && mat[nx][ny]==0){
                     posQ.offer(new pair(nx,ny));
                     book[nx][ny]=1;
                 }
             }
         }
         return false;

     }

    public static void main(String[] args) {
        int[][] mat= {{0, 0, 1, 0},
                      {1, 0, 0, 1},
                       {0,0,0,0},
                       {1,1,0,0}
        };
        while(true){
            System.out.println("输入开始位置和结束位置");
            Scanner sc=new Scanner(System.in);
            int startx=sc.nextInt();
            int starty=sc.nextInt();
            int endx=sc.nextInt();
            int endy=sc.nextInt();
            boolean a=dfs(mat,startx,starty,endx,endy);
            System.out.println(a);
        }

     }
}

N叉树的层序遍历

回溯算法之广度优先遍历

思路:创建链表和队列,遍历队列,把队列元素取出,值放入链表中,把元素的孩子放到对列中

步骤:

        1.创建队列  和链表

        2.把root结点放入队列

        3.遍历队列

                1.得到队列长度

                2.取出全部元素,一个一个遍历

                3.创建链表,把结点放入链表

                4.把结点的孩子放入队列中

        4.把新的链表存入大链表中

class Solution {
     public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> list=new ArrayList<>();
        Queue<Node> q=new LinkedList<>();
        if(root==null){
            return list;
        }
        q.offer(root);
        while(!q.isEmpty()){
            int size=q.size();
            List<Integer> newL=new ArrayList();
            while(size--!=0){
                Node cur=q.poll();
                newL.add(cur.val);
                for(Node n:cur.children){
                    q.offer(n);
                }
                
            }
            list.add(newL);
        }
        return list;
    }
}

 腐烂的橘子

回溯算法之广度优先遍历

  •  创建队列,用于深度遍历
  • 找到所有腐烂的(值为2),放入队列中
  • 创建step,用于记录步数
  • 遍历队列,直到队列为0,结束
    • 定义flag,用于记录是否当前是否蔓延到新的橘子
    • 得到当前队列的个数,保证当前这次的元素能全部遍历到
      • flag=1  说明有新的被蔓延,放入队列中
      • 遍历四个方向得到新的位置
      • 如果位置不合法或者不是新的橘子,continue
      • flag=1,当前位置标记为腐烂,放入队列中
    • 如果flag=1(这一层遍历完),step++
  • 遍历所以,如果还有新鲜橘子则返回-1
  • 返回step
class pair{
    int x;
    int y;
    public pair(int x,int y){
        this.x=x;
        this.y=y;
    }
  
}
class Solution {
    public int orangesRotting(int[][] grid) {
        int row=grid.length;
        int col=grid[0].length;
        int[][] next={{0,1},{0,-1},{1,0},{-1,0}};
        Queue<pair> q=new LinkedList<>();
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==2){
                    q.offer(new pair(i,j));
                }
            }
        }
        int step=0;
        while(!q.isEmpty()){
            int size=q.size();
            int flag=0;
            while(size--!=0){
                pair cur=q.poll();
                
                for(int i=0;i<4;i++){
                    int nx=cur.x+next[i][0];
                    int ny=cur.y+next[i][1];

                    if(nx<0 || nx>=row || ny<0 || ny>=col || grid[nx][ny]!=1){
                        continue;
                    }
                    flag=1;
                    grid[nx][ny]=2;
                    q.offer(new pair(nx,ny));

                }
            }
            if(flag==1){
                step++;
            }
        }

        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){
                    return -1;
                }
            }
        }
        return step;
    }
}

单词接龙

回溯算法之广度优先遍历

计数有第一个,开始为1,如果有新的++ 

  •  创建两个set,一个存放字典,一个存遍历过的字符串,创建队列用于广度遍历
  • 把开始字符串放入队列中
  • 遍历队列
    • 得到队列长度,把当前层的都遍历到
      • 得到字符串
      • 如果和结束相等,返回step
      • 遍历字符串的字符分别替换成别的字母
      • 如果在字典中,没有遍历过,放入队列,标记为遍历过
    • step++
  • 还没有结束,返回0
  public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int step=1;//开始不包含在字典中
        Set<String> book=new HashSet<>();
        Set<String> dict=new HashSet<>();
        for(String str:wordList){
            dict.add(str);
        }
        Queue<String> q=new LinkedList<>();
        q.offer(beginWord);
        while(!q.isEmpty()){
            int n=q.size();
            while(n--!=0){
                String cur=q.poll();
                if(cur.contains(endWord)){
                    return step;
                }
                for(int i=0;i<cur.length();i++){
                    StringBuilder s=new StringBuilder(cur);
                    for(char ch='a';ch<='z';ch++){
                        s.setCharAt(i,ch);
                        String s1=s.toString();
                        if(dict.contains(s1) && !book.contains(s1) ){
                            q.offer(s1);
                            book.add(s1);

                        }
                    }
                }
            }
            step++;
        }
        return 0;
    }

 最小基因变化

回溯算法之广度优先遍历

 计数没有算第一个,开始为0,如果有新的在++

  •  创建两个set,一个存放字典,一个存遍历过的字符串,创建队列用于广度遍历
  • step==0
  • 把开始字符串放入队列中
  • 遍历队列
    • 得到队列长度,把当前层的都遍历到
      • 得到字符串
      • 如果和结束相等,返回step
      • 遍历字符串的字符分别替换成别的字母
      • 如果在字典中,没有遍历过,放入队列,标记为遍历过
    • step++
  • 还没有结束,返回0
public int minMutation(String startGene, String endGene, String[] bank) {
       int step=0;
       Set<String> book=new HashSet<>();
       Set<String> dict=new HashSet<>();
       Queue<String> q=new LinkedList<>();
       q.offer(startGene);
       for(String s:bank){
           dict.add(s);
       }
       char[] ch={'A','C','G','T'};
         while(!q.isEmpty()){
           int size=q.size();
           while(size--!=0){
               String cur=q.poll();
               if(cur.contains(endGene)){
                              return step;
                            }
               for(int i=0;i<cur.length();i++){
                   StringBuilder str1=new StringBuilder(cur);
                   for(int j=0;j<4;j++){
                       str1.setCharAt(i,ch[j]);
                       String s1=str1.toString();
                       if(dict.contains(s1) && !book.contains(s1)){
                           
                           q.offer(s1);
                           book.add(s1);
                       }
                   }
               }
           }
           step++;
       }
       return -1;
    }

 打开转盘锁

回溯算法之广度优先遍历

 文章来源地址https://www.toymoban.com/news/detail-482636.html

  1. 创建
    1. step=0 记录步数  计数没有包含第一个
    2. queue存放数据
    3. set book(是否遍历过) dead(存放死亡字符串)
  2. 把开始位置放入队列,和book中
  3. deadends放入dead中
  4. 遍历队列
    1. 得到队列长度,保证都遍历到
      1. 取出队首字符串
      2. 如果和目标数字相同,则返回步数
      3. 遍历字符串,每一个字符串的每个字符
      4. 两个int型变量记录当前位置,分别表示向上波动和向下波动
      5. 向上:如果是9.-->0,不是++ 向下:如果是0-->9,不是--
      6. 创建两个stringbuilder.把对应位置换掉
      7. 如果不和任何一个相同,没有遍历过
      8. 放入队列,book中
    2. step++
  5. return 0
 public int openLock(String[] deadends, String target) {
     //计数没有包含第一个
     int step=0;
     Set<String> book=new HashSet<>();
        Set<String> dead=new HashSet<>();
        for(String str:deadends){
            dead.add(str);
        }
        if(dead.contains("0000")){
            return -1;
        }
        Queue<String> q=new LinkedList<>();
        q.offer("0000");
        book.add("0000");
        while(!q.isEmpty()){
            int size=q.size();
            while(size--!=0){
                String cur=q.poll();
                if(cur.contains(target)){
                    return step;
                }
                //转动
                for(int i=0;i<4;i++){
                    char new1=cur.charAt(i);
                    char new2=cur.charAt(i);

                    //往上转
                    if(new1=='9'){
                        new1='0';
                    }else{
                        new1++;
                    }
                    //往下转
                    if(new2=='0'){
                        new2='9';
                    }else{
                        new2--;
                    }

                    //替换
                    StringBuilder str1=new StringBuilder(cur);
                    StringBuilder str2=new StringBuilder(cur);

                    str1.setCharAt(i,new1);
                    str2.setCharAt(i,new2);

                    String s1=str1.toString();
                    String s2=str2.toString();

                    //判断
                    if(!dead.contains(s1) && !book.contains(s1)){
                        q.offer(s1);
                        book.add(s1);
                    } 
                    if(!dead.contains(s2) && !book.contains(s2)){
                        q.offer(s2);
                        book.add(s2);
                    }

                }
}
         step++;
        }
        return -1;
    }

到了这里,关于回溯算法之广度优先遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】广度优先遍历 (BFS)

    (1) 广度优先遍历 (Breadth First Search) ,又称 宽度优先遍历 ,是最简便的图的搜索算法之一。 (2)已知图 G = (V, E) 和一个源顶点 start,宽度优先搜索以一种系统的方式探寻 G 的边,从而“发现” start 所能到达的所有顶点,并计算 start 到所有这些顶点的距离(最少边数),

    2024年02月08日
    浏览(39)
  • 二叉树层级遍历(深度优先、广度优先算法)

    中等难度 思路和算法 我们可以用广度优先搜索解决这个问题。 我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态,它表示某个节点和它所在的层数,每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类,分类的时

    2024年02月09日
    浏览(39)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(49)
  • 【数据结构与算法】图的深度优先和广度优先遍历

    😊😊作者简介😊😊 : 大家好,我是南瓜籽,一个在校大二学生,我将会持续分享Java相关知识。 🎉🎉个人主页🎉🎉 : 南瓜籽的主页 ✨✨座右铭✨✨ : 坚持到底,决不放弃,是成功的保证,只要你不放弃,你就有机会,只要放弃的人,他肯定是不会成功的人。 图是一

    2024年02月02日
    浏览(58)
  • 基于邻接矩阵的有向图的广度优先遍历(BFS)和深度优先遍历(DFS)算法

    概念: 广度优先遍历算法是图的另一种基本遍历算法,其基本思想是尽最大程度辐射能够覆盖的节点,并对其进行访问。 以迷宫为例,广度优先搜索则可以想象成一组人一起朝不同的方向走迷宫,当出现新的未走过的路的时候,可以理解成一个人有分身术,继续从不同的方

    2024年02月06日
    浏览(66)
  • 图论与算法(5)图的广度优先遍历应用

    树的广度优先遍历(Breadth-First Traversal),也称为层次遍历,是一种按层次顺序逐级访问树节点的遍历方式。在广度优先遍历中,先访问树的根节点,然后按照从上到下、从左到右的顺序逐层访问树的节点。 首先将树的根节点入队列,然后循环执行以下操作:出队列一个节点

    2024年02月08日
    浏览(46)
  • 【数据结构与算法】图的基本概念 | 邻接矩阵和邻接表 | 广度优先遍历和深度优先遍历

    🌠 作者:@ 阿亮joy. 🎆 专栏:《数据结构与算法要啸着学》 🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根 图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E) ,其中: 顶点集合V = {x|x属于某

    2024年02月04日
    浏览(73)
  • 数据结构学习笔记——图的遍历算法(深度优先搜索和广度优先搜索)

    图的遍历指从图中某一顶点出发(任意一个顶点都可以作为访问的起始顶点),按照某种遍历方法,对图中所有的顶点访问一次且只访问一次。图与树不一样,其中一个顶点可能与多个顶点相连,所以需记录已访问过的顶点,当访问一个顶点后,考虑如何选取下一个要访问的

    2024年02月05日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包