广度优先遍历 订阅
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。 展开全文
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
信息
外文名
BFS
别    称
广度优先搜索
应用学科
计算机
中文名
宽度优先搜索算法
适用领域范围
计算机算法
宽度优先搜索概述
BFS,其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里,其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中(例如队列或是链表),而被检验过的节点则被放置在被称为 closed 的容器中。(open-closed表)
收起全文
精华内容
下载资源
问答
  • 广度优先遍历
    2021-11-12 14:38:53

    目录

    1. 广度优先遍历

    1.1 原理

    1.2 代码示例

    2. 深度优先遍历

    2.1 原理

    2.2 代码示例


    【写在前面】

    今天对广度优先遍历和深度优先遍历做了一些了解和汇总,这里做个学习笔记,便于后续深入学习。知识点和思路,参考文章如链接,可直接看原博文:树的广度优先遍历和深度优先遍历Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    1. 广度优先遍历

    1.1 原理

    英文缩写为BFS,即Breadth FirstSearch。

    是以广度为优先的,一层一层搜索下去的,就像病毒感染,扩散性的传播下去。其过程检验来说是对每一层节点依次访问,访问完一层进入下一层,而且每个节点只能访问一次。

    广度优先遍历树,需要用到队列(Queue)来存储节点对象, 队列的特点就是先进先出。

    先往队列中插入左节点,再插右节点,这样出队就是先左节点后右节点了。

    1.2 代码示例

    (1)树节点:TreeNode

    //树节点
    package MySearchMethod;
    
    public class TreeNode{
        Integer val;
        TreeNode left;
        TreeNode right;
    
        public TreeNode(Integer val){
            this.val = val;
            left = null;
            right = null;
        }
    }

    (2)二叉树:BinaryTree

    //构建二叉树
    package MySearchMethod;
    
    public class BinaryTree<T> {
        private TreeNode root;
        BinaryTree(){
            root = null;
        }
    
        public void insertTreeNode(Integer val){
            if(root == null){
                root = new TreeNode(val);
                return;
            }
            TreeNode currentNode = root;
            while(true){
                if(val.compareTo(currentNode.val) > 0){
                    if(currentNode.right == null){
                        currentNode.right = new TreeNode(val);
                        break;
                    }
                    currentNode = currentNode.right;
                }else {
                    if(currentNode.left == null){
                        currentNode.left = new TreeNode(val);
                        break;
                    }
                    currentNode = currentNode.left;
                }
            }
        }
        public TreeNode getRoot(){
            return root;
        }
    }
    

    (3)广度优先遍历:

    注:下方遍历方法应该也适用于其他树,不只二叉树。待研究。

    /**
     * 广度优先遍历,非递归
     */
    
    package MySearchMethod;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class BreadthFirstSearch {
    
        public static void main(String[] args){
            BinaryTree<Integer> tree = new BinaryTree<>();
            tree.insertTreeNode(35);
            tree.insertTreeNode(20);
            tree.insertTreeNode(15);
            tree.insertTreeNode(16);
            tree.insertTreeNode(29);
            tree.insertTreeNode(28);
            tree.insertTreeNode(30);
            tree.insertTreeNode(40);
            tree.insertTreeNode(50);
            tree.insertTreeNode(45);
            tree.insertTreeNode(55);
    
            System.out.println("广度优先算法(非递归):");
            breadthSearch(tree.getRoot());
    
        }
    
       public static void breadthSearch(TreeNode root){
           Queue<TreeNode> queue = new LinkedList<TreeNode>();
           queue.offer(root);
           TreeNode currentNode;
           while(!queue.isEmpty()){
               currentNode = queue.poll();
               System.out.print(currentNode.val + "  ");
    
               if(currentNode.left != null){
                   queue.offer(currentNode.left);
               }
               if(currentNode.right != queue){
                   queue.offer(currentNode.right);
               }
           }
       }
    }
    

    遍历结果:

    有一个空指针异常的报错,还没找到原因。待补。

    广度优先算法(非递归):
    35  20  40  15  29  50  16  28  30  45  55  Exception in thread "main" java.lang.NullPointerException
        at MySearchMethod.BreadthFirstSearch.breadthSearch(BreadthFirstSearch.java:37)
        at MySearchMethod.BreadthFirstSearch.main(BreadthFirstSearch.java:27)

    Process finished with exit code 1

    2. 深度优先遍历

    2.1 原理

    英文缩写为DFS,即Depth First Search。

    其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。

    深度优先遍历各个节点,需要使用到栈(Stack)这种数据结构。stack的特点是是先进后出。整个遍历过程如下:先往栈中压入右节点,再压左节点,这样出栈就是先左节点后右节点了。

    对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历。

    这里先演示先序遍历的情况。

    2.2 代码示例

    (1)树节点:TreeNode。 如上,略。

    (2)二叉树:BinaryTree。如上,略。

    (3)深度优先遍历:

    注:这里先演示先序遍历的情况。其他情况待补。

    /**
     * 深度优先遍历,非递归
     */
    package MySearchMethod;
    
    import java.util.Stack;
    
    public class DepthFirstSearch {
        public static void main(String[] args){
            BinaryTree<Integer> tree = new BinaryTree<>();
            tree.insertTreeNode(35);
            tree.insertTreeNode(20);
            tree.insertTreeNode(15);
            tree.insertTreeNode(16);
            tree.insertTreeNode(29);
            tree.insertTreeNode(28);
            tree.insertTreeNode(30);
            tree.insertTreeNode(40);
            tree.insertTreeNode(50);
            tree.insertTreeNode(45);
            tree.insertTreeNode(55);
    
            System.out.println("深度优先算法之先序遍历(非递归):");
            depthSearch(tree.getRoot());
        }
    
        public static void depthSearch(TreeNode root){
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            TreeNode currentNode;
            while (!stack.isEmpty()){
                currentNode = stack.pop();
                System.out.print(currentNode.val + "  ");
                if(currentNode.right != null){
                    stack.push(currentNode.right);
                }
                if(currentNode.left != null){
                    stack.push(currentNode.left);
                }
            }
        }
    }
    

    遍历结果:

    深度优先算法之先序遍历(非递归):
    35  20  15  16  29  28  30  40  50  45  55  
    Process finished with exit code 0
     

    更多相关内容
  • 主要介绍了JavaScript树的深度优先遍历和广度优先遍历算法,结合实例形式分析了JavaScript树的深度优先遍历、广度优先遍历递归与非递归相关实现技巧,需要的朋友可以参考下
  • 主要介绍了Java实现二叉树的深度优先遍历和广度优先遍历算法,结合实例形式详细分析了二叉树的定义、深度优先遍历与广度优先遍历算法原理与相关操作实现技巧,需要的朋友可以参考下
  • 那么广度遍历的顺序就是ABCDEF 从上到下,从左到右去访问 运用到格子游戏中,找寻某点到某点的路径 【假设只记录四方位(遍历顺序上左下右)】 向队列中存入起点,遍历该点周围的点,边界看做障碍,遍历到结束点返回...
  • 天津理工大学实验报告 学院系名称 计算机与通信工程学院 姓名 学号 专业 计算机科学与技术 班级 2009 级 1 班 实验项目 实验四 图的深度优先与广度优先遍历 课程名称 数据结构与算法 课程代码 实验时间 2011 年 5 月...
  • js代码-二叉树广度优先遍历
  • 本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个...
  • 天津理工大学实验报告 学院系名称 计算机与通信工程学院 姓名 学号 专业 计算机科学与技术 班级 2009 级 1 班 实验项目 实验四 图的深度优先与广度优先遍历 课程名称 数据结构与算法 课程代码 实验时间 2011 年 5 月...
  • 本程序方便的实现了图的深度、广度优先遍历,txt文档代码复制即可使用。
  • C++实现,数据结构,图的邻接矩阵表示,深度优先遍历,广度优先遍历,DFS,BFS,为什么要五十个字才能上传啊
  • 建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
  • 本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个...
  • - PAGE PAGE 2 欢迎下载 实验报告 学院系名称计算机与通信工程学院 姓名 学号 专业 计算机科学与技术 班级 实验项目 实验四图的深度优先与广度优先遍历 课程名称 数据结构与算法 课程代码 0661913 实验时间 2019年4...
  • 深度优先遍历和广度优先遍历

    万次阅读 多人点赞 2019-05-29 21:24:38
    深度优先遍历和广度优先遍历 什么是 深度/广度 优先遍历? 深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。 这两...

    深度优先遍历和广度优先遍历
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    什么是 深度/广度 优先遍历?

    深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。

    这两种遍历方式有什么不同呢?我们来举个栗子:

    我们来到一个游乐场,游乐场里有11个景点。我们从景点0开始,要玩遍游乐场的所有景点,可以有什么样的游玩次序呢?

    在这里插入图片描述
    第一种是一头扎到底的玩法。我们选择一条支路,尽可能不断地深入,如果遇到死路就往回退,回退过程中如果遇到没探索过的支路,就进入该支路继续深入。

    在图中,我们首先选择景点1的这条路,继续深入到景点7、景点8,终于发现走不动了(景点旁边的数字代表探索次序):
    在这里插入图片描述
    于是,我们退回到景点7,然后探索景点10,又走到了死胡同。于是,退回到景点1,探索景点9:
    在这里插入图片描述
    按照这个思路,我们再退回到景点0,后续依次探索景点2、3、5、4、6,终于玩遍了整个游乐场:
    在这里插入图片描述
    像这样先深入探索,走到头再回退寻找其他出路的遍历方式,就叫做深度优先遍历(DFS)。
    在这里插入图片描述
    在这里插入图片描述
    除了像深度优先遍历这样一头扎到底的玩法以外,我们还有另一种玩法:首先把起点相邻的几个景点玩遍,然后去玩距离起点稍远一些(隔一层)的景点,然后再去玩距离起点更远一些(隔两层)的景点…

    在图中,我们首先探索景点0的相邻景点1、2、3、4:
    在这里插入图片描述
    接着,我们探索与景点0相隔一层的景点7、9、5、6:
    在这里插入图片描述
    最后,我们探索与景点0相隔两层的景点8、10:
    在这里插入图片描述
    像这样一层一层由内而外的遍历方式,就叫做广度优先遍历(BFS)。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    深度优先遍历

    首先说说深度优先遍历的实现过程。这里所说的回溯是什么意思呢?回溯顾名思义,就是自后向前,追溯曾经走过的路径。

    我们把刚才游乐场的例子抽象成数据结构的图,假如我们依次访问了顶点0、1、7、8,发现无路可走了,这时候我们要从顶点8退回到顶点7。

    在这里插入图片描述
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20190529211147549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyMjE3MDE4MTAz,size_16,color_FFFFFF,t_70

    而后我们探索了顶点10,又无路可走了,这时候我们要从顶点10退回到顶点7,再退回到顶点1。
    在这里插入图片描述
    像这样的自后向前追溯曾经访问过的路径,就叫做回溯。

    要想实现回溯,可以利用栈的先入后出特性,也可以采用递归的方式(因为递归本身就是基于方法调用栈来实现)。

    下面我们来演示一下具体实现过程。

    首先访问顶点0、1、7、8,这四个顶点依次入栈,此时顶点8是栈顶:
    在这里插入图片描述
    从顶点8退回到顶点7,顶点8出栈:
    在这里插入图片描述
    接下来访问顶点10,顶点10入栈:
    在这里插入图片描述
    从顶点10退到顶点7,从顶点7退到顶点1,顶点10和顶点7出栈:
    在这里插入图片描述
    探索顶点9,顶点9入栈:
    在这里插入图片描述
    以此类推,利用这样一个临时栈来实现回溯,最终遍历完所有顶点。

    广度优先遍历

    接下来该说说广度优先遍历的实现过程了。刚才所说的重放是什么意思呢?似乎听起来和回溯差不多?其实,回溯与重放是完全相反的过程。

    仍然以刚才的图为例,按照广度优先遍历的思想,我们首先遍历顶点0,然后遍历了邻近顶点1、2、3、4:

    在这里插入图片描述
    接下来我们要遍历更外围的顶点,可是如何找到这些更外围的顶点呢?我们需要把刚才遍历过的顶点1、2、3、4按顺序重新回顾一遍,从顶点1发现邻近的顶点7、9;从顶点3发现邻近的顶点5、6。
    在这里插入图片描述
    像这样把遍历过的顶点按照之前的遍历顺序重新回顾,就叫做重放。同样的,要实现重放也需要额外的存储空间,可以利用队列的先入先出特性来实现。

    下面我们来演示一下具体实现过程。
    首先遍历起点顶点0,顶点0入队:
    在这里插入图片描述
    接下来顶点0出队,遍历顶点0的邻近顶点1、2、3、4,并且把它们入队:
    在这里插入图片描述
    然后顶点1出队,遍历顶点1的邻近顶点7、9,并且把它们入队:
    在这里插入图片描述
    然后顶点2出队,没有新的顶点可入队:
    在这里插入图片描述
    以此类推,利用这样一个队列来实现重放,最终遍历完所有顶点。

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

    图的顶点
    
    / private static class Vertex { int data; Vertex(int data) {    this.data = data; } } /*
    
    图(邻接表形式)
    
    / private static class Graph { private int size; private Vertex[] vertexes; private LinkedList adj[]; Graph(int size){    this.size = size;    //初始化顶点和邻接矩阵    vertexes = new Vertex[size];    adj = new LinkedList[size];    for(int i=0; i*
    
    深度优先遍历
    
    / public static void dfs(Graph graph, int start, boolean[] visited) { System.out.println(graph.vertexes[start].data); visited[start] = true; for(int index : graph.adj[start]){    if(!visited[index]){        dfs(graph, index, visited);    } } } /*
    
    广度优先遍历
    
    */
    
    public static void bfs(Graph graph, int start, boolean[] visited, LinkedList queue) {
    
    queue.offer(start);
    
    while (!queue.isEmpty()){
    
       int front = queue.poll();
    
       if(visited[front]){
    
           continue;
    
       }
    
       System.out.println(graph.vertexes[front].data);
    
       visited[front] = true;
    
       for(int index : graph.adj[front]){
    
           queue.offer(index);;
    
       }
    
    }
    
    }
    
    public static void main(String[] args) {
    
    Graph graph = new Graph(6);
    
    graph.adj[0].add(1);
    
    graph.adj[0].add(2);
    
    graph.adj[0].add(3);
    
    graph.adj[1].add(0);
    
    graph.adj[1].add(3);
    
    graph.adj[1].add(4);
    
    graph.adj[2].add(0);
    
    graph.adj[3].add(0);
    
    graph.adj[3].add(1);
    
    graph.adj[3].add(4);
    
    graph.adj[3].add(5);
    
    graph.adj[4].add(1);
    
    graph.adj[4].add(3);
    
    graph.adj[4].add(5);
    
    graph.adj[5].add(3);
    
    graph.adj[5].add(4);
    
    System.out.println("图的深度优先遍历:");
    
    dfs(graph, 0, new boolean[graph.size]);
    
    System.out.println("图的广度优先遍历:");
    
    bfs(graph, 0, new boolean[graph.size], new LinkedList());
    
    }
    

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

    展开全文
  • 广度优先遍历和深度优先遍历等js函数
  • 资源为数据结构之图形的两种存储形式的演示,包括邻接矩阵、邻接表,以及深度优先和广度优先遍历的两种实现,通过阅读可以提供对于图更加深刻的掌握
  • 深度优先遍历DFS 与树的先序遍历比较类似。 假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的...
  • javascript通过递归和栈实现树深度优先遍历和广度优先遍历
  • 主要介绍了python实现树的深度优先遍历与广度优先遍历,详细分析了树的深度优先遍历与广度优先遍历原理及Python相关实现技巧,需要的朋友可以参考下
  • 主要介绍了PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次),结合实例形式详细分析了php针对二叉树的深度优先遍历与广度优先遍历相关操作技巧与注意事项,需要的朋友可以参考下
  • 广度优先遍历 实例

    2016-08-02 15:17:20
    广度优先遍历作为一个初学者必备的技能,此资源免费,广度优先遍历是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始,辐射状地优先遍历其周围较广的区域,故得名
  • 程序设计任务: 设计一个程序,实现以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。基本要求:以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的...
  • 本资源是用C语言所写的,数据结构中图的创建及其相关的深度,广度遍历
  • 无向图建立、深度优先遍历和广度优先遍历实现算法[借鉴].pdf
  • 使用邻接表表示法创建无向图,然后使用非递归算法进行深度优先遍历和广度优先遍历
  • 广度优先遍历

    千次阅读 2022-03-20 21:25:27
    广度优先遍历,BFS,柔性数组

    首先来说一下广度优先遍历,看名称很高大上的样子,其实它的原理跟树的层次遍历几乎一模一样。那么我就以树的层次遍历简单说明一下原理。

    要实现层次遍历需要创建队列作为辅助。

    层次遍历收先将根结点入队,如下图:

    然后把A出队,把它的左右儿子入队:

    把B出队,将B的左右儿子入队,也就是谁出队就把谁的左右儿子入队:

    C出队,把C的左右儿子入队,依次循环下去.....,直到全部都输出,简单的来看一下,大家是否发现树的输出顺序是ABCDEF,也就是说一层一层的输出。这也是广度优先遍历的原理。 

    下面就直接将代码:

    大家先不要慌,先把我图中绿色方框去掉,那么代码变成在执行说明内容。大家先想想,其实你会的,并不难,想明白了就好理解了。

     不知道大家能不能看出来,除去绿色方框的代码,剩下的代码其实就是在创建邻接表

    那么我们就重点来分析绿色方框的代码就行了,没必要全部都要讲,浪费大家阅读其他文章的时间。

    ①、先上主函数,主函数就是在创建一个广度优先遍历的函数BFS,需要注意的是蓝色方框的内容,蓝色方框代码就是在定义从哪个顶点开始遍历,如果你的顶点名称是ABCDEF这几个字母,你可以选择ABCDEF其中一个字母作为整个遍历的开始,Findsub函数的作用顶点名称(ABCDEF)所在顶点表中的下标。Findsub函数代码内容也在下面了,很简单的一段代码

    ②、在对BFS函数讲解之前献给大家看一下队列结构:

    其中int* data和int* visited两者不是简单的指针,注意他是在结构体内的,他们是柔性数组结构,为什么要这样设计,有什么用。首先我就讲一点它的好处,具体在这里起到什么作用下面会讲到,柔性数组最大的特点是它是一个可以调整大小的数组,一般的数组大小都是固定的,当你想要在添加数据的时候就溢出了,这时你得重新去定义它的大小,是不是很麻烦呢。

    其他两个成员变量是用来遍历队列用的,先不管,继续往下。

     

    ③、这时就到了BFS函数了。

    还算是有点长的。但要成为大佬的你们不算什么。

                红色方框的代码作用是为队列开辟空间,聪明的你也许会发现我的代码开辟了三个空间,后面两个空间是给谁的呢,上面我们不是说到了柔性数组是可以调整大小的吗,就是给队列和辅助数组开辟的空间,这是你应该知道怎么使用柔性数组了吧,也知道它的强大了吧,它的大小会随着G->vernums大小的改变而改变,也就是根据你输入的顶点数的大小改变而改变,不需要担心数组溢出的问题。

                蓝色方框是将顶点入队,入队的顶点所在顶点数组下标要赋给辅助数组visited,也就是被访问过的顶点标记为1,没访问过的标记为0。

                    粉色方框代码是重点,需要点耗费点脑力,我还是用图来说明一下吧。因为表达有限,说明在下一张图,对应这粉色方框来看哦。辅助数组的作用也在最后了哦。

    ④、辅助数组:

    原来全是0,被访问过就赋值为1

    展开全文
  • 邻接表存储图深度优先广度优先遍历
  • 图的广度优先遍历与树的按层次遍历相似,遍历的思路是对图中的每个顶点进行访问且只访问一次.要遍历图。首先要把图采用某种存储结构存到内存之中.本文采用邻接表存储,并在此基础上进行广度优先遍历
  • 主要介绍了PHP实现二叉树的深度优先与广度优先遍历方法,涉及php针对二叉树进行遍历的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 59,199
精华内容 23,679
关键字:

广度优先遍历