页面启动中 . . .

BFS和DFS优先搜索算法

优先搜索 二叉树
算法
发布日期:   2023-10-05
更新日期:   2023-12-20
文章字数:   2k
阅读时长:   8 分
阅读次数:  

BFS和DFS优先搜索算法

前几天做了两道二叉树的问题，现在回头想想还是觉得不太熟练。二叉树是典型的搜索算法，常见的有BFS（层级遍历，但有区别）和DFS两种，下面就写一点自己的总结和看法

​

BFS(广度优先算法)

1. 基础介绍

BFS（广度优先搜索）是一种图遍历算法，它从一个起始点开始，逐层扩展搜索范围，直到找到目标节点为止。

  • 这种算法通常用于解决“最短路径”问题，比如在迷宫中找到从起点到终点的最短路径。

    1. 首先，你会从起点开始，检查所有与它相邻的位置，也就是距离起点为1的位置。
    2. 然后，你会继续向外扩展，检查所有距离起点为2的位置，以此类推，直到找到出口。

  • 在BFS中，你可以使用队列来存储待搜索的节点。起始点首先加入队列中，然后不断从队列中取出节点，检查它是否是目标节点。如果不是，就将它的所有未被访问过的邻居加入队列中。这样，队列中的节点总是按照它们距离起点的距离排序，先加入队列的节点总是先被取出来搜索。

  • 通过这种方式，BFS可以找到起点到目标节点的最短路径。在实际应用中，BFS还可以用于拓扑排序、连通性检测等问题的解决。

  • 遍历过程如下图：

    bfs

    ​

2. 层序遍历

层序遍历和广度优先算法还是存在区别的，虽然都是扁平进行搜索，同样是每层按顺序进行排列，但是他们的返回值不一样。

  • BFS 遍历使用队列数据结构,BFS 的遍历结果是一个一维数组，无法区分每一层。
  • 层序遍历要求我们区分每一层，也就是返回一个二维数组。
bfs和层序遍历

​

3. 具体代码

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val){
        this.val=val;
    }
}

public class BFSTraversal {
    //二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
             //在每一层遍历开始前，先记录队列中的结点数量n（也就是这一层的结点数量），然后一口气处理完这一层的n个结点。将当前层的所有结点出队列，再将下一层的所有结点入队列，这样就实现了层序遍历。
            List<Integer> levelNodes = new ArrayList<>();//每一层一个List数组
           
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelNodes.add(node.val);

                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            result.add(levelNodes);//[[,]]
        }

        return result;
    }

    // 二叉树的广度遍历
    public List<Integer> BfsBinary(TreeNode root){
        List<Integer> resultList = new ArrayList<>();
        if (root == null) return resultList;
        
        LinkedList<TreeNode> queue = new LinkedList<>();

        queue.add(root);//offer()比add()稍好，可以对异常处理有所调控,但一般刷题都行

        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            resultList.add(node.val);
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }

        return resultList;
    }

    public static void main(String[] args) {
        // 创建一棵二叉树示例
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 实例化BFSTraversal对象
        BFSTraversal traversal = new BFSTraversal();
        // 调用levelOrder方法进行广度优先遍历(但是是层序遍历)，区分每一层，返回二维数组
        List<List<Integer>> result = traversal.levelOrder(root);
        // 输出结果
        System.out.println("层序遍历输出："+result);
        //广度优先搜索，BFS 的遍历结果是一个一维数组，无法区分每一层
        BFSTraversal t=new BFSTraversal();
        List<Integer> result1=t.BfsBinary(root);
        System.out.println("Bfs遍历输出："+result1);
    }
}

  • 运行结果如图所示：

    result

    ​

DFS(深度优先搜索算法)

1. 基础介绍

DFS（深度优先搜索）是一种图遍历算法，它从一个起始点开始，一直往下走直到不能再走为止，然后返回到前一个节点，继续探索它的其他分支，直到找到目标节点为止。

  • 这种算法通常用于解决“遍历”问题，比如在树中查找所有的叶子节点。要理解DFS，也还可以想象自己在迷宫中寻找所有可行的路径。

    1. 首先，你会从起点开始，顺着一条路一直走，直到你走到一个死胡同
    2. 再返回到前一个节点，继续探索其他分支
    3. 在探索过程中，你可以使用栈来存储已经访问过的节点，以便后续回溯。

  • 在DFS中，你可以使用递归或栈来实现深度优先搜索。通过这种方式，DFS可以找到所有可行的路径，或者在树中查找所有的叶子节点。

  • 在实际应用中，DFS还可以用于拓扑排序、连通性检测等问题的解决。与BFS相比，DFS通常更适合处理深度优先的问题，而BFS更适合处理广度优先的问题。

    dfs

    ​

2. 具体代码

import java.util.*;

//dfs深度优先,以二叉树的前序遍历为例
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class PreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        dfs(root, result);
        return result;
    }

    private void dfs(TreeNode root, List<Integer> result) {//递归，隐含地调用系统的栈，递归地调用左右子树，最后将值存储在result序列中。
        if (root == null) return;

        result.add(root.val);
        dfs(root.left, result);
        dfs(root.right, result);
    }

    public static void main(String[] args) {
        // 创建一棵二叉树示例
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 实例化PreorderTraversal对象
        PreorderTraversal traversal = new PreorderTraversal();

        // 调用preorderTraversal方法进行前序遍历（dfs）
        List<Integer> result = traversal.preorderTraversal(root);

        // 输出结果
        System.out.println("DFS遍历输出："+result);
    }
}
  • 运行结果如图所示：
result2

​

3. DFS一道例题：

1. 题目说明：

给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

  • 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：

num1tree 
输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

​

2. 解答分析

  • 该如何计算路径中表示的数字呢？顺着子节点的指针路径向下遍历二叉树，每达到一个节点，相当于在路径表示的数字末尾添加一位数字。

  • 对于每次遍历都是path=path*10+root.val;仔细观察可以看出应该是典型的二叉树前序遍历，每个得出的数字都是计算当前节点的路径到头，最后再计算子节点的路径表示的数字。

  • 利用dfs实现的是递归调用，这里注意三部曲：

    • 找到最后递归的终止条件
    • 找到上一次递归的返回值
    • 找到本次递归的具体操作

    ​

3. 具体代码
class Solution{
	public int sumNumbers(TreeNode root){
   		return dfs(root,0);//输入的数和数字结果
	}
	private int dfs(){//每一次遍历到当前路径尽头
 		if(root==null){	//终止条件
            return 0;
        }
        //本次递归级的具体操作
        path=path*10+root.val;//当前递归中的每次数字的统计
        if(root.left==null && root.right==null){
            return path;
        }
        return dfs(root.left,path)+dfs(root.right,path);//上一级返回值
	}
}

​

​

BFS和DFS的动图比对

DFS AND BFS
End~
文章作者: XKJ
文章链接: https://shakeJ96.github.io/2023/10/05/bfs-he-dfs-you-xian-sou-suo-suan-fa/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 XKJ !
优先搜索 二叉树
赏
  目录