javascript - 图表 - 如何建模依赖资源？

Question

没有库，我正在尝试学习数据结构。

我有这些依赖

jquery.js->jqueryui.js

(underscores.js, jquery.js) -> backbone.js

基本上，jqueryui 依赖于 jquery。 Bacbkone 依赖于下划线和 jquery。 Jquery 和 underscore 没有关系。

我想创建一个依赖关系树，让您“阐明”这些关系。

我被告知这是如何在这个 posted question 上完成的.特别是这条评论。

As long as you don't have a circular dependency you can always build a dependency forest, which consists only of directed trees and/or sole nodes. On the trees you can simply use DFS. You then start by adding all roots or single nodes into a queue and add other resources to the queue when their dependency has been loaded. (note that if a resource has several dependencies you cannot model your dependencies as a forest, but it stays acyclic and you can use a similar approach). – Zeta

...所以我确实有多个依赖项的资源，所以我不能使用依赖项林。

...进一步的讨论提出了有向无环图。

A directed acyclic graph. Every path from the starting point can be done in parallel, however if a node has more than one incident edges you have to wait for all dependencies being loaded. By the way, I would represent example 3 as P:[U-underscore, U-jquery] S:[U-underscore, U-backbone-js] S:[U-jquery, U-backbone.js], showing the original dependency, but they are equivalent

我可以使用依赖树吗？如果不是，建议使用什么数据结构来模拟复杂的依赖关系……最后我该如何实现它？

Answer 1

我相信我已经解决了这个问题，尽管这是很久以前的事了。让依赖关系这样描述:

• 模块A
  • 模块十
  • 模块 Y
• 模块 B
  • 模块十
  • 模块A
• 模块 C
  • 模块A
  • 模块 B

这意味着模块 A 依赖于模块 X 和模块 Y - 等等。

遍历这个森林中的叶子，对于每个没有依赖关系的叶子(在底部查找)，将叶子放入加载队列并将其从森林中移除，所以首先通过产量:

• 模块A
• 模块 B
  • 模块A
• 模块 C
  • 模块A
  • 模块 B

队列:模块 X，模块 Y。

第二遍:

• 模块 B
• 模块 C
  • 模块 B

队列:模块 X、模块 Y、模块 A。

……等等。在同一遍中找到的模块可以并行加载，因此表示这一点的方法可以是:

[[Module X, Module Y], [Module A], [Module B], [Module C]]

这意味着模块 X 和模块 Y 应该首先加载，并且它们可以并行加载。其余部分必须顺序加载。

我对上述方法最大的担忧是它的复杂度为 O(n^2)。应该是可以改进的。使用查找图可以轻松检测周期。