文档章节

可视化讲解 深度优先遍历(DFT)

ssthouse_hust
 ssthouse_hust
发布于 2018/09/16 12:15
字数 1297
阅读 429
收藏 8

可视化讲解 深度优先遍历(DFT)

深度优先遍历, 刷过题的朋友应该都很熟悉了,难是不难,但是理解起来还是要费一些功夫的. 深度优先遍历的实现方法有递归非递归两种, 这里我们用可视化的角度,讲解前一种: 递归的深度优先遍历.

为什么要以可视化的方式来讲解呢? 因为人是视觉的动物, 如果和你说 二叉树 , 相信大家脑中出现的都是下面的图形:

binary tree

stack

而不是下面的代码:

// binary tree
class Node {
  constructor(value, leftChild, rightChild) {
    this.value = value
    this.leftChild = leftChild
    this.rightChild = rightChild
  }
}

// stack
const stack = new Array()
stack.push(1)
var topItem = stack.pop()

所以说, 人是视觉动物, 以图形可视化的方式来讲解问题往往能讲解的更清楚, 这也就是我写本文的缘由.

效果展示

为了可视化的讲解 深度优先遍历算法, 笔者写了一个简单的网页, 实现的功能有:

  • 用户可编辑进行深度遍历的二叉树
  • 网页上给出了 JavaScript 版本的实现
  • 点击 Start DFT 按钮, 用户将看到算法中用到的 二叉树 都将动态 的展示在页面中,可以直观的看到代码运行过程中数据的变化

页面目前还在继续优化中, 让我们看看目前的效果:

在线demo:

https://ssthouse.github.io/visual-explain/#/list/dft

stack

可以看到,网页模拟了深度搜索时二叉树的动态变化过程:

  • 二叉树中当前遍历到的节点会变成红色;
  • 栈中压入 (push)的节点为灰色;
  • 栈中弹出 (pop) 的节点会变为红色, 然后消失;

其中页面左上角为初始遍历的二叉树数据, 用户可以修改二叉树数据后再次启动可视化深度优先遍历过程.

页面左下角为深度优先遍历的 javascript 实现版本,作为参考.

深度优先遍历简介

可视化分析之前,让我们先来简单看看实现深度优先搜索的代码:

export class Dft {
  constructor(rootNode, stepCallback) {
    this.rootNode = rootNode
    this.stepCallback = stepCallback
  }

  start() {
    if (!this.rootNode || !this.stepCallback) {
      return
    }
    const stack = [this.rootNode]
    while (stack.length !== 0) {
      const curNode = stack.pop()
      console.log(`current node: ${curNode.value}`)
      curNode.childrenNodes.forEach(element => {
        stack.push(element)
      })
    }
  }
}

export class Node {
  constructor(value, childrenNodes = []) {
    this.value = value
    this.childrenNodes = childrenNodes
  }
}

代码不长,让我们一步步看.

首先我们创建了一个栈 const stack = [this.rootNode] , 并将根节点放入栈中.

接下来是一个while语句, 跳出循环的条件是 栈为空, 也就是代表我们遍历完了整棵树.

在循环中, 我们先将栈顶的节点弹出, 并打印出来, 表示我们已经遍历过了该节点. 然后将该节点的所有子节点压入栈中, 这就保障了我们下一个遍历到的点就是该节点的子节点. 重复该循环, 最后我们就可以看到, 二叉树的每个节点都按照深度搜索的顺序被打印了出来:

current node: 1
current node: 4
current node: 7
current node: 6
current node: 2
current node: 5
current node: 3

如果是对栈的使用比较熟悉的同学, 可能看到这里就已经明白原理了.

但是, 如果是对栈使用不是很熟悉的同学, 估计对代码的执行过程还是没有一个直观的认识, 那么让我们以更直观的方式看看这段代码是怎么运行的.

可视化讲解

第一步, 将根节点压入栈中:

step1

接下来进入 while 循环, 每个循环都会将栈顶的节点弹出, 将其子节点压入栈中:

step2

可以看出, 深度优先遍历利用了栈先进后出的特性, 使得对于每个节点, 都将在遍历该节点后,下一步遍历他的子节点, 由此完成深度优先的遍历:

stack

最后

本文中的二叉树, 的可视化是笔者自己封装的 UI 组件, 只需简单的调用就可以将代码中数据结构以可视化的方式显示在页面中.

个人觉得这样的数据结构可视化可能会对代码的讲解有些帮助, 如果你也有这方面的需求的话, 不妨在下面留言告诉我, 我可以将这些 UI 组件封装一下方便有需要的人使用.

源码在这, 欢迎 fork & star

https://github.com/ssthouse/visual-explain

想继续了解 D3.js || 数据可视化 ?

这里是我的 D3.js数据可视化 的 github 地址, 欢迎 start & fork :tada:

D3-blog

如果觉得不错的话, 不妨点击下面的链接关注一下 : )

github 主页

知乎专栏

掘金

想直接联系我 ?

邮箱: ssthouse@163.com

微信:

wechat

© 著作权归作者所有

共有 人打赏支持
ssthouse_hust
粉丝 9
博文 18
码字总数 30123
作品 0
武汉
私信 提问
加载中

评论(5)

ssthouse_hust
ssthouse_hust

引用来自“Tonemy”的评论

博主,动态图怎么制作的?
动态图是用的 D3.js 绘制的, 有兴趣的话可以看看源码: https://github.com/ssthouse/visual-explain

核心代码在这个目录: https://github.com/ssthouse/visual-explain/tree/master/src/components/depth-first-traversal
Tonemy
Tonemy
博主,动态图怎么制作的?
银杏卡卡
银杏卡卡

引用来自“节节草”的评论

博主辛苦!博主还可以把广度优先遍历也顺带讲解一下。

引用来自“ssthouse_hust”的评论

多谢反馈, 下一步正准备做广度优先遍历👍
博主大爱无疆!我也只是随便提一下,目前我对这些也没多大兴趣,哈哈哈
ssthouse_hust
ssthouse_hust

引用来自“节节草”的评论

博主辛苦!博主还可以把广度优先遍历也顺带讲解一下。
多谢反馈, 下一步正准备做广度优先遍历👍
银杏卡卡
银杏卡卡
博主辛苦!博主还可以把广度优先遍历也顺带讲解一下。
【算法研究】搜索算法-深度优先搜索

---------- 如果您觉得本文有用,可以在微博上关注我,每周我都会在微博上发布新博客发表的通知,我的微博 深度优先搜索 介绍 如果您觉得这篇文章排版不舒服,请到我的微盘下载pdf:搜索算法...

王选易
2013/12/13
0
3
二叉搜索树的简明实现(ES5 & ES6)

二叉树 & 二叉搜索树 二叉树(Binary Tree)是 n(n >= 0)个节点的有限集合,集合为空集时,叫作空二叉树;不为空时,由根节点及左子树、右子树组成,左子树、右子树也都是二叉树。 从这个描...

天方夜
2018/10/30
0
0
无向图----深度优先搜索

上一篇:无向图的实现 下一篇:深度优先遍历 根据描述,很容易实现图的深度优先搜索: 深度优先遍历标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比。 使用深度优先搜索查找图中路...

Superheros
2017/12/19
4
0
图的JS实现

图的定义 图就是由若干个顶点和边连接起来的一种结构。很多东西都可以用图来说明,例如人际关系,或者地图。 其中图还分为有向图和无向图。 如下就是有向图 图的数据结构 对于图这种关系,可...

光哥很霸气
2017/10/12
0
0
python分布式爬虫搜索引擎实战-2-深度优先和广度优先

深度优先和广度优先 目录: 网站的树结构 深度优先算法和实现 广度优先算法和实现 网站url树结构: 分层设计 子域名: bogbole.com 环路链接: 从首页到下面节点。 但是下面的链接节点又会有链...

天涯明月笙
2017/03/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周五乱弹 —— 姑娘馋的口水都留下来了。

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @且无需多言 :分享Fall Out Boy的单曲《Disloyal Order Of Water Buffaloes》 《Disloyal Order Of Water Buffaloes》- Fall Out Boy 手机党...

小小编辑
54分钟前
24
6
vue 对对象的属性进行修改时,不能渲染页面 vue.$set()

我在vue里的方法里给一个对象添加某个属性时,我console.log出来的是已经更改的object ,但是页面始终没有变化 原因如下: **受现代 JavaScript 的限制 (而且 Object.observe 也已经被废弃),...

Js_Mei
今天
2
0
开始看《Java学习笔记》

虽然书买了很久,但一直没看。这其中也写过一些Java程序,但都是基于IDE的帮助和对C#的理解来写的,感觉不踏实。 林信良的书写得蛮好的,能够帮助打好基础,看得出作者是比较用心的。 第1章概...

max佩恩
昨天
12
0
Redux 三大原则

1.单一数据源 在传统的MVC架构中,我们可以根据需要创建无数个Model,而Model之间可以互相监听、触发事件甚至循环或嵌套触发事件,这些在Redux中都是不被允许的。 因为在Redux的思想里,一个...

wenxingjun
昨天
9
0
跟我学Spring Cloud(Finchley版)-12-微服务容错三板斧

至此,我们已实现服务发现、负载均衡,同时,使用Feign也实现了良好的远程调用——我们的代码是可读、可维护的。理论上,我们现在已经能构建一个不错的分布式应用了,但微服务之间是通过网络...

周立_ITMuch
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部