问题描述
没有库，我正在尝试学习数据结构。
With out libraries, I'm trying to learn data structures.
我有这些依赖关系
jquery.js->jqueryui.js
(underscores.js, jquery.js) -> backbone.js
基本上，jqueryui依赖于jquery。 Bacbkone依赖于下划线和jquery。 Jquery和下划线没有关联。
Bascially, jqueryui depends upon jquery. Bacbkone depends on both underscore and jquery. Jquery and underscore are not related.
我想创建一个依赖树，让你揭开这些关系。
I want to create a dependency tree have you to "shed light" on these relations.
我被告知这是如何在这个上完成的。特别是这个评论。
I was told this is how it is done on this posted question. Particularly this comment.
...所以我确实有多个依赖项的资源，所以我不能使用依赖项林。
... so I do have resources with multiple dependencies, so I can't use a dependency forest.
......进一步的讨论提出了有向无环图。
...further discussion has suggested a directed acyclic graph.
我可以使用依赖树吗？如果没有建议建立复杂依赖关系的数据结构......最后我该如何实现它？
Can I use a dependency tree? If not what data structure is suggested to model complex dependencies...and and finally how do I implement it?
推荐答案
我相信我已经解决了这个问题，尽管很久以前。让依赖关系描述如下：
I believe that I have solved this problem, albeit its a long time ago. Let the dependencies be described like this:
- 模块A
- 模块X
- 模块Y
- 模块X
- 模块A
- 模块A
- 模块B
这意味着模块A依赖于模块X和模块Y - 依此类推。
Which means that Module A depends on Module X and Module Y - and so forth.
迭代此林中的叶子以及没有依赖关系的每个叶子（查看基础），将叶子放入加载队列并将其从森林中移除，因此首先通过收益率：
Iterate over the leaves in this forest and for each leaf with no dependencies (look that up at the base), put the leaf in the load queue and remove it from the forest, so first pass yields:
- 模块A
- 模块B
- 模块A
- 模块A
- 模块B
队列：模块X，模块Y.
Queue: Module X, Module Y.
第二遍：
- 模块B
- 模块C
- 模块B
队列：模块X，模块Y，模块A。
Queue: Module X, Module Y, Module A.
......等等。在同一个传递中找到的模块可以并行加载，因此表示这个模块的方法可能是：
...and so forth. Modules found in the same pass can be loaded in parallel, so a way to represent this could be:
[[Module X, Module Y], [Module A], [Module B], [Module C]]这意味着什么应首先加载模块X和模块Y，并且可以并行加载它们。其余的必须按顺序加载。
Which means that Module X and Module Y should be loaded first and that they can be loaded in parallel. The rest must be loaded sequentially.
我对上述方法的最大顾虑是它具有复杂度O（n ^ 2）。应该可以改进。使用查找映射可以轻松完成检测周期。
My biggest concern with the approach above is that it has complexity O(n^2). It should be possible to improve. Detecting cycles can easily be done with a lookup map.
这篇关于图表 - 如何建模依赖资源？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！