常用算法

文章目录

拓扑排序

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

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

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

换一种表示方式就是：

// 模块：{依赖模块}
A: {B, C, D}
B: {C, E }
C: {D, E}
D: {E}
E: {}

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

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