对于具有JS内依赖关系的可遍历树，可以使用什么方法？

Question

可能是最糟糕的头衔，因为我不知道该怎么说，但希望我能在这里解释得更好。请注意，这个问题中会出现大量错误的术语，我对此表示歉意。

我想尝试在节点中构建一个能够遍历依赖树的JS应用程序。通常使用jQuery遍历的普通树会很好，但我认为这比这要复杂一些。

我举这个图像为例：

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

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

在本例中，研究实验室是优先考虑的，但只要遵循这两种方式，任何订单都是可以的。

到目前为止，我还没有真正知道如何接近它。如果它是一个简单的树结构，没有多个依赖项，我就把它设置为树。

如果你知道怎么做的话，请随意提取一些小的例子。

Answer 1

依赖关系结构不是树，而是有向无圈图，或DAG：

• 指向:边从一个节点转到另一个节点，因此有方向；
• 无环:没有循环；
• 图:节点可以有多个传入的边缘(与树不同，树最多有一个父节点)。

(我之所以提到这一点，是因为DAG在各种应用程序中都是非常棒和有用的，包括这个应用程序。值得你花时间去了解它们。)

您要寻找的是来自“目标”节点的深度优先或宽度第一遍历。(在您的示例图像中，您将沿着边缘向后遍历。)

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