JavaScript 进阶实战课
石川
JavaScript Patterns and Anti-Patterns 等开源项目创建者,O'Reilly 技术评审
15066 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 47 讲
开篇词 (1讲)
JavaScript 进阶实战课
15
15
1.0x
00:00/00:00
登录|注册

19 | 通过树和图看如何在无序中找到路径和秩序

你好,我是石川。
在算法中,最常见的两个操作莫过于排序和搜索了。前面我们通过数组了解了在线性的数据结构中不同的排序算法。之后,我们又通过哈希算法了解了散列表这种比较特殊的线性表,了解了它是如何与链表结合,用空间换时间地支持索引和查找的。
在现实的生活中,我们可以看到信息并不总是有序的,我们在讲到函数式编程的时候有提到过,函数思想的一个维度就是如何处理未知和混沌。那么函数中的数据结构和算法呢,作为现实世界的映射,也要能处理这样复杂的情况。今天,我们来看两种支持我们处理这种未知和混沌的非线性的数据结构。一种是树,另外一种是图。
我们知道一些大的咨询公司如麦肯锡,经常用到“金字塔原理”来做解决方案。它的核心原理呢,讲的就是我们平时接收的信息是杂乱无章的网状结构的,而我们要做的是在杂乱无章的信息中梳理出“金字塔”式的树形信息结构,最后呢,再用线性的“讲故事”的方式讲述出来。这就像极了我们在算法中用到的各种数据结构。
今天我们就深入来看看图和树这两种数据结构。我们先从图说起,图就是一种非线性的数据结构。我们生活中有很多无序的网络组织都可以用图来表示,比如社交网络,我们的互联网通信、城市的道路、网站的链接。如果用我们前端开发的视角来看的话,不同依赖资源本身也可以被看做是无序的,而例如我们前端经常用到的 webpack 的模块加载功能就是一个在无序中建立秩序,帮助我们厘清资源之间相关依赖关系的工具,这种功能就可以通过拓扑排序来实现。我们可以先从图这种数据结构本身说起,来一步步看下它是怎么做到的。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文深入探讨了树和图这两种非线性数据结构的应用和实现方法。首先介绍了图的结构和类型,包括有向图、无向图、稀疏图和稠密图等概念,并讨论了图的存储方式和遍历方式。接着详细介绍了如何通过拓扑排序建立资源依赖,以及使用迪杰斯特拉算法找到最短路径。此外,还提及了字典树在建立Web API的路由中的应用。另外,文章还介绍了树的类型和结构,包括二叉树、二叉查找树、AVL树、红黑树以及堆的特点和应用。最后,对字符串的匹配算法进行了介绍,包括暴力算法、BM算法、KMP算法和RK算法,并对它们的复杂度进行了比较。整体而言,本文通过实际生活中的例子,结合算法和数据结构的知识,深入浅出地介绍了树和图这两种非线性数据结构的应用和实现方法。 文章通过介绍图和树这两种数据结构,展示了它们在解决实际问题中的重要性。从具体应用角度看,这些数据结构可以用于解决Web中的模块打包、路由等问题。而从抽象角度看,这些算法可以帮助我们在混沌和未知中建立秩序,寻找出路。此外,文章还提到了在分析复杂度问题时,需要考虑预处理、不同应用场景下的复杂度,拓展了读者的思考维度。 在技术方面,文章详细介绍了字典树在路由中的应用,以及不同的字符串匹配算法,为读者提供了丰富的技术知识。通过对不同算法的复杂度进行比较,读者可以更好地理解算法的选择和应用场景。 总的来说,本文通过丰富的例子和技术知识,帮助读者快速了解了树和图这两种非线性数据结构的应用和实现方法,为读者拓展了技术视野,提供了丰富的思考题目,引发读者的思考和讨论。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《JavaScript 进阶实战课》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(3)

  • 最新
  • 精选
  • 郭慧娟
    二叉搜索树的时间复杂度应该是 O(\log_{2}{(n)}) 吧。是不是写错了

    作者回复: 二叉搜索树的时间复杂度应该是 O(logn) , 非平衡二叉树是O(2)

    2022-11-09归属地:海南
  • AbyssKR
    后序遍历的顺序为左、右、根。原文为“它的遍历顺序是右、左、根”,图片没有问题
    2022-11-28归属地:辽宁
    2
  • 无咎
    建议标题修改:'通过树和图...' 改为'通过图和树...'
    2023-05-06归属地:北京
收起评论
显示
设置
留言
3
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部