javascript - 在 JS 中有依赖关系的可遍历树可以使用什么方法？

Question

可能是有史以来最糟糕的标题，因为我不确定如何表达它，但希望我能在这里解释得更好。请注意，这个问题中会出现大量错误的术语，对此我深表歉意。

我想尝试在 Node 中构建一个可以遍历依赖树的 JS 应用程序。通常使用 jQuery 遍历的普通树就可以了，但我认为这比那要复杂一点。

我以这张图片为例:

https://i.imgur.com/MQHWBDk.png (从以前的图像更新，因为在某些浏览器中它重定向到较小的分辨率)

我希望能够选择一个 Node 并让应用程序输出到该 Node 的最有效路径，包括所有依赖项。例如，如果我想进入 Shielding Technology 1，它会输出:研究实验室1 -> 研究实验室2 -> 研究实验室3 -> 研究实验室4 -> 研究实验室5 -> 研究实验室6 -> 能源技术1 -> 能源技术2 -> 能源技术3 -> 屏蔽技术1

在这个例子中，研究实验室是优先考虑的，但只要遵循这两条路径，任何顺序都可以。

到目前为止，我还不知道如何处理它。如果它是一个没有多个依赖项的简单树结构，我会把它设置为一棵树。

如果您知道如何做，请随意提取更小的示例。

Answer 1

依赖结构不是树，而是 directed acyclic graph , 或 DAG:

• 有向:边从一个 Node 到另一个 Node ，因此有方向；
• acyclic:没有循环；
• 图: Node 可以有多个入边(不像树，它们最多只有一个父 Node )。

(我提到这一点是因为 DAG 非常棒并且在各种应用程序中都很有用，包括这个应用程序。值得您花时间了解它们。)

您正在寻找的是 depth-first或 breadth-first从你的“目标” Node 遍历。 (在您的示例图像中，您将沿着边缘向后遍历。)

你想要哪一个？这取决于您想要确定的优先级:深度优先将倾向于首先完成链(例如 RL1 -> RL2 -> ... -> ET1 -> ET2 -> ... 如您建议的“路线”)，而广度优先将倾向于首先完成“级别”(例如 RL1 -> ET1 -> RL2 -> ET2 -> ...)