问数据结构存储一步一步的指南

EN

有向图应该是最简单的方法。在阅读剩下的课文之前，请记住，我并没有谈论数据结构的并行化，因为我不知道如何做到这一点。无论如何，您将不会处理大量的数据，所以您将不会有任何效率问题。

我们将为每个步骤存储两个数组:一个用于下一个步骤，另一个用于依赖项。将支持下列行动：

1. 在O(1)中插入步骤:为它创建两个空数组
2. O(1)中的依赖项插入:只需在所涉步骤的依赖项/下一步数组的末尾添加一个条目即可
3. O(N)中的步骤删除:设S为要删除的步骤。迭代S的依赖数组，对于数组中的每个元素，转到该元素的下一步数组并删除包含S的条目，然后遍历S的下一步数组，对于数组中的每个元素，转到该元素的依赖数组并删除包含S的条目，然后删除与S相关的两个数组。
4. O(N)中的依赖项删除:只需在dependency/next步骤数组中查找与要删除的依赖项相关的条目，并删除它们
5. 检查O(N)中步骤S的所有依赖项和下一步步骤:只需迭代与步骤S相关的两个数组
6. 求O(N+M)中的临界路径，其中M是依赖关系的总数:我们将运行一个动态规划算法:设f( v )是从顶点v开始的最长路径，如果v没有下一步，我们可以计算f(v) =1，否则f(v) = max(f( u )+1)，对每一步运行动态规划算法，并且临界路径是所有最长路径中的最大值。

注意，有些操作可以使用BST或哈希表加速，但是由于要处理小数据，所以我尽量保持它的简单性。