专栏首页程序员小灰漫画:深度优先遍历 和 广度优先遍历

漫画:深度优先遍历 和 广度优先遍历

————— 第二天 —————

————————————

什么是 深度/广度 优先遍历?

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

而后我们探索了顶点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<Integer> adj[];


 Graph(int size){
 this.size = size;
 //初始化顶点和邻接矩阵
        vertexes = new Vertex[size];
        adj = new LinkedList[size];
 for(int i=0; i<size; i++){
            vertexes[i] = new Vertex(i);
            adj[i] = new LinkedList();
        }
    }
}
/**
 * 深度优先遍历
 */
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<Integer> 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<Integer>());
}

—————END—————

本文分享自微信公众号 - 程序员小灰(chengxuyuanxiaohui),作者:蠢萌的小灰

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:Dijkstra 算法的优化

    在上一篇漫画中,小灰介绍了单源最短路径算法 Dijkstra,没看过的小伙伴可以看下:

    小灰
  • 漫画:图的 “最短路径” 问题

    第1步,创建距离表。表中的Key是顶点名称,Value是从起点A到对应顶点的已知最短距离。但是,一开始我们并不知道A到其他顶点的最短距离是多少,Value默认是...

    小灰
  • 漫画:去掉一个数,如何让剩余的数乘积最大?

    我们删去元素-2,原本数组中的三个负数变成了两个,负负得正,而且保证了剩余元素的乘积最大。

    小灰
  • 公有云或将遭遇败退 这到底是真是假?

    大家在沉浸于新技术带来的便利时,有没有思考过与云计算服务相关的以下几个问题? ? 以规模化方式开发云应用会带来非常高昂的运营成本,但这部分成本到底会不会超出内部...

    静一
  • 【中国AI合伙人】助理来也胡一川、罗超专访(视频)

    新智元
  • Android 安全更新的发展与沿革

    此前,我们在 Google I/O 2018 开发者大会上举办了一场名为《Android 安全新亮点》的主题演讲,简要介绍了谷歌在 Android 安全更新方...

    Android 开发者
  • 使用局部标准差实现图像的局部对比度增强算法。

          图像的对比度增强算法在很多场合都有着重要的应用,特别是在医学图像上,这是因为在众多疾病的诊断中,医学图像的视觉检查时很有必要的。而医学图像由于本身及...

    用户1138785
  • 体素科技丁晓伟:国内智能医疗起步晚但发展迅速,产品普及还需更多临床数据与市场教育 | 镁客请讲

    镁客网
  • Flask入门

    本文参考博客:https://blog.csdn.net/xiaoyuan511?t=1

    py3study
  • Linux系统是由什么语言编写,安卓为什么是由Linux开发?

    从事软件开发多年,而且大多数情况都是在linux完成代码的编写,自从第一次接触linux之后就再也离不开了,目前linux系统主要用在服务器端以及开发者使用,针...

    程序员互动联盟

扫码关注云+社区

领取腾讯云代金券