我试图在Javascript一步一步的指南(想想任何宜家指南)建模1. 每一步都可以链接到一个或多个下一步，2. 一个步骤可以与之前的步骤有0或n个依赖关系3.总有最后一步。像这样:
o
/
o -> o o -> o
/
o -> o
首先想到的是一个有向图结构，但由于这个图具有所有节点都指向"前"的唯一性，我想知道是否有更好的方法。感觉它应该是某种树和图的混合体。
最终，我想使用这个结构来优化建议的执行计划。我不会太担心优化插入，删除，更新或查询，因为这些指南总是少于100个步骤。我只是在寻找一种数据结构，使编码"更容易"。
我要在这个结构中查询的内容:
- 关键路径是什么?
- 步骤X的依赖项/下一步是什么? 什么是最有效的方法来并行/序列化这些步骤的执行?
有向图应该是最简单的方法。在你阅读剩下的内容之前，请记住，我没有讨论数据结构的并行化，因为我不知道怎么做。无论如何，你不会处理很多数据，所以你不会有任何效率问题。
我们将为每个步骤存储两个数组:一个用于下一步，另一个用于依赖项。支持以下操作:
- Step insert in O(1):只需为它创建两个空数组
- 在O(1)中插入依赖项:只需在相关步骤的依赖项/下一步数组的末尾添加一个条目
- O(N)中的步骤删除:设S为要删除的步骤。迭代S的依赖数组，对于数组中的每个元素，到该元素的下一步数组，删除包含S的条目。然后迭代S的下一步数组，对于数组中的每个元素，到该元素的依赖数组，删除包含S的条目。然后删除与S 相关的两个数组。
- 在O(N)中删除依赖项:只需在依赖项/下一步数组中查找与要删除的依赖项相关的条目并删除它们
- 检查O(N)中步骤S的所有依赖项和后续步骤:只需迭代与步骤S相关的两个数组
- 在O(N+M)中找到关键路径，其中M是依赖项的总数:我们将运行一个动态规划算法，设f(v)为从顶点v开始的最长路径，如果v没有下一步，我们可以计算f(v) = 1，否则f(v) = max(f(u)+1)对于每个下一步u，每一步运行动态规划算法，关键路径是所有最长路径中的最大值。
请注意，使用bst或哈希表可以加快一些操作，但由于您将处理小数据，因此我尽量保持简单。