C# 数据结构以分层方式存储项目，一旦建立分支，它允许我检索它并将其添加为另一个分支的一部分

Question

我正在努力解决一个问题，我必须找到一种方法来存储程序可能遵循的所有可能路径。以此图像为例。

在该图像中，每个数字代表一个复杂的过程，该过程可能会调用其他过程来执行自身，描述您在图像中可以看到的所有路径。

所有实线表示流程必须遵循的路径，而虚线表示可选路径。

知道执行是从左到右，从上到下开始的，因此必须始终牢记，如果已经构建了一个分支，则必须重用它并且永远不要重新构建它。

例如，在此另一张图片中，黄线表示在执行流程编号 37 期间遵循的所有路径。

在其中您可以看到从进程 18 (18->17->16) 开始的路径是先前构建的，因此当到达进程 19 时不应重建它，因为所有这些进程都需要相当长的时间并且在已经知道它们产生的结果的情况下尝试再次构建它们是浪费时间。相反，如果发现之前构建了某个数字(例如进程 18)，则应将其复制/附加到调用它的进程(图中的进程 19)。所有这一切都是为了一个日志，我必须在其中存储所有完整的路径，这就是为什么我提到复制/重用分支的部分，因为我稍后必须查询该日志以显示所有这些路径。

为了执行所有这些过程，目前使用递归过程，但由于它不考虑它可以重用以前构建的路径，所以整个过程需要很长时间。

你知道有什么数据结构可以帮助我优化这个过程，这样如果一个过程已经执行过，它只会被重用。至于日志，正如我上面提到的，我需要存储完整的路径。

如有任何想法或资源，我们将不胜感激。

谢谢

编辑 1

----------------------------

可能我没有说得很清楚的一件事是，我需要创建的数据结构有两个目的:

1. 跟踪主进程(示例中的 37)在执行期间所遵循的所有路径，让我有机会随时判断某条路径是否已经存在随后，然后能够将该路径复制到应该调用它的节点(在示例中，复制整个分支:18->17->16 到进程 19。
2. 通过让我有机会判断路径是否已经在这个数据结构中，我可以避免执行已经执行过且结果已知的子流程，从而优化整个执行过程。<

编辑2

----------------------------

关于为什么我不考虑使用 Dictionary 的问题，一开始我有这个想法，但后来我找不到字典可以告诉我的方法，例如，以 18 (18->17->16) 开始的路径从进程 37 和 19 下降。你看，一个节点可以有一个或多个父节点。我怎么能用字典来表达呢？

Answer 1

我相信这就是您正在寻找的数据结构:

var paths = new Dictionary<int, HashSet<int>>()
{
    { 37, new HashSet<int>() { 18, 33, 34, 35, 36, } },
    { 18, new HashSet<int>() { 17, } },
    { 33, new HashSet<int>() { } },
    { 34, new HashSet<int>() { 19, 17, 15, } },
    { 35, new HashSet<int>() { 17, } },
    { 36, new HashSet<int>() { } },
    { 17, new HashSet<int>() { 16, } },
    { 19, new HashSet<int>() { 12, 18, } },
    { 15, new HashSet<int>() { 14, } },
    { 16, new HashSet<int>() { } },
    { 12, new HashSet<int>() { 11, } },
    { 14, new HashSet<int>() { } },
    { 11, new HashSet<int>() { } },
};

这是向路径添加路径的代码:

public bool TryAddPath(Dictionary<int, HashSet<int>> paths, int x, int y)
{
    if (!paths.ContainsKey(x))
    {
        paths[x] = new HashSet<int>() { };
    }

    if (!paths[x].Contains(y))
    {
        paths[x].Add(y);
        if (!paths.ContainsKey(y))
        {
            paths[y] = new HashSet<int>() { };
        }
        return true;
    }
    return false;
}

上面的数据结构可以通过以下方式构建:

var paths = new Dictionary<int, HashSet<int>>();
var results = new bool[]
{
    TryAddPath(paths, 37, 18),
    TryAddPath(paths, 37, 33),
    TryAddPath(paths, 37, 34),
    TryAddPath(paths, 37, 35),
    TryAddPath(paths, 37, 36),
    TryAddPath(paths, 18, 17),
    TryAddPath(paths, 17, 16),
    TryAddPath(paths, 34, 19),
    TryAddPath(paths, 34, 17),
    TryAddPath(paths, 34, 15),
    TryAddPath(paths, 19, 12),
    TryAddPath(paths, 19, 18),
    TryAddPath(paths, 12, 11),
    TryAddPath(paths, 18, 17),
    TryAddPath(paths, 17, 16),
    TryAddPath(paths, 17, 16),
    TryAddPath(paths, 15, 14),
    TryAddPath(paths, 35, 17),
    TryAddPath(paths, 17, 16),
};

这将返回数组 { true, true, true, true, true, true, true, true, true, true, true, true, true, false, false, false, true, true, false, }显示不需要处理的路径。

然后要找到回溯列表的方法，请执行以下操作:

ILookup<int?, int> parents =
    paths
        .Keys
        .AsEnumerable()
        .SelectMany(
            k => paths[k].Select(x => (int?)x).DefaultIfEmpty(),
            (k, v) => new { k, v })
        .ToLookup(x => x.v, x => x.k);

现在我可以问parents[17]我得到 { 18, 34, 35, }回。我什至可以做 parents[null]然后我回来{ 33, 36, 16, 14, 11, }它显示了叶子节点。