[广度优先搜索(BFS)与深度优先搜索(DFS)

柔情只为你懂 2024-04-28 13:04 99阅读 0赞

## 广度优先搜索(BFS)与深度优先搜索(DFS)详解 ##

### 深度优先搜索 ###

深搜，顾名思义，是深入其中、直取结果的一种搜索方法。
    
        如果深搜是一个人，那么他的性格一定倔得像头牛！他从一点出发去旅游，只朝着一个方向走，除非路断了，他绝不改变方向！除非四个方向全都不通或遇到终点，他绝不后退一步！因此，他的姐姐广搜总是嘲笑他，说他是个一根筋、不撞南墙不回头的家伙。
    
    　　深搜很讨厌他姐姐的嘲笑，但又不想跟自己的亲姐姐闹矛盾，于是他决定给姐姐讲述自己旅途中的经历，来改善姐姐对他的看法。他成功了，而且只讲了一次。从那以后他姐姐不仅再没有嘲笑过他，而且连看他的眼神都充满了赞赏。他以为是自己路上的各种英勇征服了姐姐，但他不知道，其实另有原因……
    
    　　深搜是这样跟姐姐讲的：关于旅行呢，我并不把目的地的风光放在第一位，而是更注重于沿路的风景，所以我不会去追求最短路，而是把所有能通向终点的路都走一遍。可是我并不知道往哪走能到达目的地，于是我只能每到一个地方，就向当地的人请教各个方向的道路情况。为了避免重复向别人问同一个方向，我就给自己规定：先问北，如果有路，那就往北走，到达下一个地方的时候就在执行此规定，如果往北不通，我就再问西，其次是南、东，要是这四个方向都不通或者抵达了终点，那我回到上一个地方，继续探索其他没去过的方向。我还要求自己要记住那些帮过他的人，但是那些给我帮倒忙的、让我白费力气的人，要忘记他们。有了这些规定之后，我就可以大胆的往前走了，既不用担心到不了不目的地，也不用担心重复走以前的路。哈哈哈……

### 深搜优缺点 ###

优点
        1、能找出所有解决方案
        2、优先搜索一棵子树，然后是另一棵，所以和广搜对比，有着内存需要相对较少的优点缺点
        3、要多次遍历，搜索所有可能路径，标识做了之后还要取消。
        4、在深度很大的情况下效率不高

### 广度优先搜索 ###

广搜，顾名思义，是多管齐下、广撒网的一种搜索方法
    
    　　如果广搜是一个人，那么她一定很贪心，而且喜新厌旧！她从一点出发去旅游，先把与起点相邻的地方全部游览一遍，然后再把与她刚游览过的景点相邻的景点全都游览一边……一直这样，直至所有的景点都游览一遍。
    
    　　广搜属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。类似树的按层遍历，其过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2…Vit，并均标记为已访问过，然后再按照Vi1、Vi2…Vit 的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。

### 广搜优缺点 ###

优点
        1、对于解决最短或最少问题特别有效，而且寻找深度小
        2、每个结点只访问一遍，结点总是以最短路径被访问，所以第二次路径确定不会比第一次短缺点
        1、内存耗费量大（需要开大量的数组单元用来存储状态）

### 用二叉树来进行深度优先搜索和广度优先搜索 ###

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA6ZSL54Gr6L-e5aSp_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

深度优先搜索的步骤为：
    
    （1）、首先节点 1 进栈，节点1在栈顶；
    
    （2）、然后节点1出栈，访问节点1，节点1的孩子节点3进栈，节点2进栈；
    
    （3）、节点2在栈顶，然后节点2出栈，访问节点2
    
    （4）、节点2的孩子节点5进栈，节点4进栈
    
    （5）、节点4在栈顶，节点4出栈，访问节点4，
    
    （6）、节点4左右孩子为空，然后节点5在栈顶，节点5出栈，访问节点5；
    
    （7）、节点5左右孩子为空，然后节点3在站顶，节点3出栈，访问节点3；
    
    （8）、节点3的孩子节点7进栈，节点6进栈
    
    （9）、节点6在栈顶，节点6出栈，访问节点6；
    
    （10）、节点6的孩子为空，这个时候节点7在栈顶，节点7出栈，访问节点7
    
    （11）、节点7的左右孩子为空，此时栈为空，遍历结束。

[广度优先遍历]：
    广度优先遍历是连通图的一种遍历策略，因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域故得名。
    
    根据广度优先遍历的特点我们利用Java数据结构队列Queue来实现。
    
    广度优先搜索的步骤为：
    
    （1）、节点1进队，节点1出队，访问节点1
    
    （2）、节点1的孩子节点2进队，节点3进队。
    
    （3）、节点2出队，访问节点2，节点2的孩子节点4进队，节点5进队；
    
    （4）、节点3出队，访问节点3，节点3的孩子节点6进队，节点7进队；
    
    （5）、节点4出队，访问节点4，节点4没有孩子节点。
    
    （6）、节点5出队，访问节点5，节点5没有孩子节点。
    
    （7）、节点6出队，访问节点6，节点6没有孩子节点。
    
    （8）、节点7出队，访问节点7，节点7没有孩子节点，结束。

#### Java**代码** 具体实现 ####

[二叉树][Link 1]的基础代码：

package com.深度遍历;
    
    /**
     * 二叉树数据结构
     */
    public class TreeNode {
        
        int data;
        TreeNode leftNode;
        TreeNode rightNode;
        public TreeNode() {
        
    
        }
        public TreeNode(int d) {
        
            data=d;
        }
    
        public TreeNode(TreeNode left,TreeNode right,int d) {
        
            leftNode=left;
            rightNode=right;
            data=d;
        }
    }

广度优先和深度优先遍历算法实现代码：

package com.深度遍历;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    /**
     * 深度优先遍历
     *
     * 进栈 push()
     * 入栈：在栈顶（数组的尾部）添加指定的元素，并返回新数组的长度。
     * 出栈 pop()
     * 出栈：删除栈顶（数组的尾部）的一个元素，并返回删除的元素。
     *
     * poll：将首个元素从队列中弹出，如果队列是空的，就返回null
     *
     */
    public class DeepFirstSort {
        
    
        public static void main(String[] args) {
        
    
    //      构建二叉树
            TreeNode head = binaryTree();
            System.out.print("深度优先遍历结果：");
    
            new DeepFirstSort().depthFirstSearch(head);
            System.out.print("广度优先遍历结果：");
            new DeepFirstSort().BroadFirstSearch(head);
            System.out.println();
    
        }
    
        //深度优先遍历
        public void depthFirstSearch(TreeNode nodeHead) {
        
            if (nodeHead == null) {
        
                return;
            }
            Stack<TreeNode> myStack = new Stack<>();
            myStack.add(nodeHead);
            while (!myStack.isEmpty()) {
        
                TreeNode node = myStack.pop();    //弹出栈顶元素
                System.out.print(node.data + " ");
                if (node.rightNode != null) {
        
                    myStack.push(node.rightNode);    //深度优先遍历，先遍历左边，后遍历右边,栈先进后出
                }
                if (node.leftNode != null) {
        
                    myStack.push(node.leftNode);
                }
            }
    
        }
    
        //广度优先遍历是使用队列实现的
        public void BroadFirstSearch(TreeNode nodeHead) {
        
            if (nodeHead == null) {
        
                return;
            }
            Queue<TreeNode> myQueue = new LinkedList<>();
            myQueue.add(nodeHead);
            while (!myQueue.isEmpty()) {
        
                TreeNode node = myQueue.poll();
                System.out.print(node.data + " ");
                if (null != node.leftNode) {
        
                    myQueue.add(node.leftNode);    //深度优先遍历，我们在这里采用每一行从左到右遍历
                }
                if (null != node.rightNode) {
        
                    myQueue.add(node.rightNode);
                }
            }
        }
    
    
        /**
         * 构建二叉树
         *
         * @return
         */
        public static TreeNode binaryTree() {
        
    
            TreeNode head = new TreeNode(1);
    
            TreeNode second = new TreeNode(2);
    
            TreeNode three = new TreeNode(3);
    
            TreeNode four = new TreeNode(4);
    
            TreeNode five = new TreeNode(5);
    
            TreeNode six = new TreeNode(6);
    
            TreeNode seven = new TreeNode(7);
    
            head.rightNode = three;
    
            head.leftNode = second;
    
            second.rightNode = five;
    
            second.leftNode = four;
    
            three.rightNode = seven;
    
            three.leftNode = six;
    
            return head;
        }
    
    }
    
    
    输入结果为：
    
    
    深度优先遍历结果：1 2 4 5 3 6 7 
    广度优先遍历结果：1 2 3 4 5 6 7 
    
    Process finished with exit code 0

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA6ZSL54Gr6L-e5aSp_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/76fa7e39ae6b4ae99d4b4e2f1cf06d46.png
[Link 1]: https://so.csdn.net/so/search?q=%E4%BA%8C%E5%8F%89%E6%A0%91&spm=1001.2101.3001.7020