深度优先遍历和广度优先遍历[通俗易懂]

深度优先遍历和广度优先遍历[通俗易懂]深度优先遍历和广度优先遍历什么是深度/广度优先遍历?深度优先遍历简称DFS(DepthFirstSearch),广度优先遍历简称BFS(BreadthFirstSearch),它们是遍历图当中所有顶点的两种方式。这两种遍历方式有什么不同呢?我们来举个栗子:我们来到一个游乐场,游乐场里有11个景点。我们从景点0开始,要玩遍游乐场的所有景点,可以有什么…

大家好,又见面了,我是你们的朋友全栈君。

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

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

深度优先遍历简称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());

}

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130947.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 0-1多重背包(单调队列+多重背包)[通俗易懂]

    0-1多重背包(单调队列+多重背包)[通俗易懂]原题链接有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。输入格式第一行两个整数,N,V (0<N≤1000, 0<V≤20000),用空格隔开,分别表示物品种数和背包容积。接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。输出格式输出一个整数,表示最大价值。数据范围0<N≤1

  • decltype 使用

    decltype 使用功能decltype可以将给定的表达式或变量的类型推导出来,包含引用和指针。一般用于复杂表达式作为返回值的类型推导。可以用于补足c++11的auto缺陷.编译阶段的事情,不会任何执行,表达式也不会执行。类型规则规则一:声明类型,类型包含引用就有引用,没有引用也不会自行添加。规则二:返回值则根据返回值类型确定最终类型。规则三:表达式根据默认和重载得到的最终类型。不建议特别复杂的表达式。声明类型分析案例一intmain()..

  • servlet-Filter过滤器

    servlet-Filter过滤器Filter过滤器Filter过滤器是javaweb的三大组件之一,三大组件分别是:Servlet程序,Listener监听器,Filter过滤器Filter过滤器它是javaEE的规范,也就是接口Filter过滤器它的作用是拦截请求,过滤响应拦截请求常见的应用场景:权限检查日记操作事务管理等等原理package at.guitu.com.FIlter;import javax.servlet.FilterChain;import javax.servlet.Filte

  • flex垂直居中,最简单的方法之一

    flex垂直居中,最简单的方法之一display:flex;align-items:center;

  • build mdl app

    build mdl app

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号