数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

43 | 拓扑排序:如何确定代码源文件的编译依赖关系?

王争 2019-01-04
从今天开始,我们就进入了专栏的高级篇。相对基础篇,高级篇涉及的知识点,都比较零散,不是太系统。所以,我会围绕一个实际软件开发的问题,在阐述具体解决方法的过程中,将涉及的知识点给你详细讲解出来。
所以,相较于基础篇“开篇问题 - 知识讲解 - 回答开篇 - 总结 - 课后思考”这样的文章结构,高级篇我稍作了些改变,大致分为这样几个部分:“问题阐述 - 算法解析 - 总结引申 - 课后思考”。
好了,现在,我们就进入高级篇的第一节,如何确定代码源文件的编译依赖关系?
我们知道,一个完整的项目往往会包含很多代码源文件。编译器在编译整个项目的时候,需要按照依赖关系,依次编译每个源文件。比如,A.cpp 依赖 B.cpp,那在编译的时候,编译器需要先编译 B.cpp,才能编译 A.cpp。
编译器通过分析源文件或者程序员事先写好的编译配置文件(比如 Makefile 文件),来获取这种局部的依赖关系。那编译器又该如何通过源文件两两之间的局部依赖关系,确定一个全局的编译顺序呢?

算法解析

这个问题的解决思路与“图”这种数据结构的一个经典算法“拓扑排序算法”有关。那什么是拓扑排序呢?这个概念很好理解,我们先来看一个生活中的拓扑排序的例子。
我们在穿衣服的时候都有一定的顺序,我们可以把这种顺序想成,衣服与衣服之间有一定的依赖关系。比如说,你必须先穿袜子才能穿鞋,先穿内裤才能穿秋裤。假设我们现在有八件衣服要穿,它们之间的两两依赖关系我们已经很清楚了,那如何安排一个穿衣序列,能够满足所有的两两之间的依赖关系?
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(45)

  • Jerry银银
    老师,这门专栏快结束了,突然有点新的想法:如果老师在讲解算法的时候,多讲点算法的由来,也就是背景,那就更好了。

    我想,如果能知道某个算法的创造者为什么会发明某个算法,怎么能够发明出某个算法,我想我们会掌握得更牢,学得应该也稍微轻松一点,关键是能跟随发明者回到原点,体会思考的过程

    编辑回复: 这个有意思,我们想想。

    2019-01-04
    4
    62
  • Jerry银银
    思考题:
    1. a先于b执行,也就说b依赖于a,b指向a,这样构建有向无环图时,要找到出度为0的顶点,然后删除

    2. BFS也能实现,因为遍历只是实现拓扑排序的一个“辅助手段”,本质上是帮助找到优先执行的顶点
    2019-01-04
    21
  • Handongyang
    @Jerry银银
    针对你提的算法的由来与背景的问题,我想我们完全可以通过维基百科查看,一般都有其背景以及算法应用的场景,甚至有些算法在维基百科上有相应的文献引用,这些都可以参考。

    作者回复: 银银同学要的显然不是这些

    这就好比我在跟大家讲古诗 登黄鹤楼。银银同学想知道的是 怎么才能站在黄鹤楼上 作出登黄鹤楼这么牛逼的诗 诗人的脑回路是咋样的

    而并不是想要历史性介绍 这首诗是谁谁谁 在某某年 某某地 历史背景下 做出来的

    不知道我理解的对不

    关于前者 我在讲解的时候已经尽量还原来龙去脉 但是可能学的并不明显 而且这本身就是很难说清楚的 说不定诗人自己都不知道自己咋写出这么牛逼的诗的

    2019-01-07
    16
  • 想当架构师
    我怎么觉得这个kahn算法其实就是BFS算法
    2019-01-26
    10
  • 纯洁的憎恶
    1.kahn算法找出度为0的节点删除。dfs算法直接用正邻接表即可。

    2. BFS也可以。其实与DFS一样,BFS也是从某个节点开始,找到所有与其相连通的节点。区别在于BFS是一层一层找(递归函数在for循环外),DFS是先一杆子插到底,再回来插第二条路、第三条路等等(递归函数在for循环内)。
    2019-01-04
    8
  • Aaron
    课后思考里“BFS 深度优先搜索算法”是否应该是“BFS 广度优先搜索算法”?BFS: Breadth-first Search
    2019-01-05
    5
  • 你有资格吗?
    老师,好像数据结构少了B+树的讲解啊,B+不准备讲吗?
    2019-01-07
    4
  • Edward
    老师你好。我在做一道动态规划题的时候,不借助其他启发性线索时,在纸上演算一遍后,发现自己如果不能直觉地从演算中推演出解答的关键,就会产生强烈的自我怀疑。会有一层对自己智力水平的怀疑,如果没有一定的智商,是不适合做这事情的。请问老师你有什么方法,可以克服这种自我的质疑?

    作者回复: 多练习 多思考 多总结 慢慢就好了 都有这么一个过程的

    2019-01-05
    3
  • NeverMore
    1、反过来的话计算的就不是入度了,可以用出度来判断;
    2、BFS的话,则需要记录上一个节点是哪个,可以实现,但是比DFS要麻烦些。
    还请老师指点。
    老师之后能不能给思考题一个答疑?

    作者回复: 专栏结束的时候吧 也算是一个回顾 现在年底忙 没啥时间写呢

    2019-01-04
    3
  • 不一样的烟火
    我常常陷入问题都看不懂的迷思中
    2019-08-14
    2
  • jueyoq
    老师什么时候再出课程呀。 按照咱们这销量,可以开始新专栏预告辣
    2019-02-12
    2
  • 蓝天
    刚解决完工作中类似的问题 老师的文章就来了,然后才知道那个算法叫kahn
    2019-01-07
    2
  • farFlight
    老师,我觉得这里BFS和Kahn算法基本可以说是一样的,本身Kahn贪婪算法运用queue实现的过程就是一个典型的BFS范式。采用BFS就应该按照入度一层一层遍历,一层遍历完了的同时把下一层的顶点push进入queue中。
    2019-01-04
    2
  • www.xnsms.com小鸟接码
    DFS 算法 ,里面的递归差点就被绕进去了,这个递归终止条件太隐蔽了……不仔细看代码,还以为没有终止条件会死循环……好巧妙,打算我也想不出这样写代码
    2019-01-08
    1
    1
  • Jerry银银
    如果 a 先于 b,我们画一条从 b 到 a 的有向边,表示 b 依赖 a

    我个人更喜欢这种构建图的方式,觉得这种更符合“惯性思维方式”
    2019-01-04
    1
  • Sid
    想起了spring Bean的生成,Bean之间循环依赖的检查就是图的深度优先遍历方式检测是否有环:。 假设
    A->B->C->A, 创建A时依赖B,把A放到正在创建集合中,再去创建B,把B放到正在创建集合中,B依赖C,把C放到正在创建集合中,C依赖A,发现A在正在创建中,说明存在循环依赖,就做个特殊处理暴露出bean。看来处处有算法,用而不知。
    2019-12-11
  • leowu
    kahn就是BFS算法
    2019-11-18
  • Geek_18b741
    DFS 算法的时间复杂度计算中,为什么每个顶点访问两次?每个顶点进入dfs是一次呀?

    作者回复: dfs是栈的思想,一进一出就被访问了两次

    2019-10-24
  • Edward
    课后思考
    1. Kahn 使用逆邻接表再使用原来逻辑即可;DFS 无需再转为逆邻接表了,可直接基于当前的邻接表求解。
    2. 单纯的 BFS 应该是不能实现,其实 Kahn 就是基于 BFS 的实现。
    2019-10-17
  • 康斯坦丁
    问题1
       kahn 算法 改成查找出度为0的数据. dfs 算法不在需要逆邻接表、而直接用邻接表.
    问题2
      BFS. 也可以,先查找一个入度为0的顶点,BFS 输出结果后. 再查找下一个入度为0的顶点,直至全部被访问.
    2019-10-15
收起评论
45
返回
顶部