文章目录
  1. 1. 拓扑排序
    1. 1.1. JavasCript中的模块依赖关系
    2. 1.2. 直接遍历对应的图
    3. 1.3. 拓扑排序
  2. 2. 堆数据结构

拓扑排序

刚听到「拓扑排序」这个概念的时候,我直接懵了,脑袋中过滤一遍,完全没有发现跟这个概念相关的知识。本科的时候学过图的算法,但主要集中于图的连通性,生成树,深搜,广搜等内容,似乎并没有什么「拓扑排序」。

当我了解到它的基本内容以及应用场景之后,才发现原来的确是有这个东西,只不过是没有明确的认识到这个概念和它的重要性。

JavasCript中的模块依赖关系

在写JavaScript的时候,我们应该都遇到过标题中的概念,比如有一个模块A,它依赖于模块B, C, D; 模块B又依赖于 C, E, F;模块C依赖于D, E, F, G。

换一种表示方式就是:

1
2
3
4
5
6
// 模块: {依赖模块}
A: {B, C, D}
B: {C, E }
C: {D, E}
D: {E}
E: {}

如果要求用程序计算出存在依赖的模块系统中,每一个模块的依赖,最终输出的结果如图所示,那么该如何去考虑?

直接遍历对应的图

很明显的一点是需要把模块依赖关系转换成图数据结构,在了解到拓扑排序的概念之前,我下意识的想法是图建立起来之后,直接选取一个点,比如A点,开始循环遍历,将A能到达的路径都加入进来,然和合并成一个A的依赖关系。可以用dfs或者bfs优化。

拓扑排序

直接参考拓扑排序(Topological Sorting)

堆数据结构

文章目录
  1. 1. 拓扑排序
    1. 1.1. JavasCript中的模块依赖关系
    2. 1.2. 直接遍历对应的图
    3. 1.3. 拓扑排序
  2. 2. 堆数据结构