开发者社区> ssthouse> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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

简介:
+关注继续查看

可视化讲解 深度优先遍历(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 按钮, 用户将看到算法中用到的 二叉树 都将动态 的展示在页面中,可以直观的看到代码运行过程中数据的变化

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

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 组件封装一下方便有需要的人使用.

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

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

D3-blog

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

github 主页

知乎专栏

掘金

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
树与图的深度优先遍历
复习acwing算法基础课的内容,本篇为讲解基础算法:树与图的深度优先遍历,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
25 0
【29. DFS深度优先】
# 概述 - DFS:深度优先遍历,从一条路径走到叶节点,然后回溯,继续遍历(不撞南墙不回头) - BFS:广度优先遍历,从根节点,一层一层的遍历,每一层把所有的节点都遍历完成。 ## 递归思想 - 递归在于不断调用自己的函数,层层深入,直到遇到递归终止条件后层层回溯,其思想与dfs的思想不谋而合;因此,可以使用递归来实现dfs。 - 递归的进入比较容易理解,但是递归的回溯是在计算机底层执行的,我们无法看到。因此这是理解递归的唯一一个难点。
18 0
深度优先搜索
深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
39 0
算法之深度优先搜索
算法之深度优先搜索
25 0
刘慈欣对话卡梅隆:《三体》的深度和广度,需要至少六部电影才能完美呈现
科幻电影适合原创剧本,而不适合改编。但当前国内科幻编剧太少了。
407 0
DFS(深度优先搜索)
深度优先搜索算法(Depth-First-Search),是搜索算法的一种。它沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。
829 0
《图论》——深度优先搜索算法(DFS)
十大算法之广度优先遍历: 深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过,在G中任选一个顶点i作为遍历的初始点,则深度优先搜索递归调用包含以下操作: (1)访问搜索到的未被访问的邻接点; (2)将此顶点的visited数组元素值置1; (3)搜索该顶点的未被访问的邻接点,若该邻接点存在,则从此邻接点开始进行同样的访问和搜索。
1082 0
深度优先和广度优先
首先要理解搜索步,一个完整的搜索步包括两个处理 a) 获得当前位置上,有几条路可供选择 b) 根据选择策略,选择其中一条路,并走到下个位置 相当于在漆黑的夜里,你只能看清你站的位置和你前面的路,但你不知道每条路能够通向哪里。
788 0
+关注
ssthouse
公众号: 前端夜谈 Data visualization / 数据可视化
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载