递归 lambda 表达式通过有向图查找路径？

Question

我需要在复杂的图形结构中找到一条或多条路径。 该图是使用类似以下内容构建的：

class Node
{
    public string Value { get; set;}
    public List<Node> Nodes { get; set;}

    public Node()
    {
        Nodes = new List<Node>();
    }
}

使事情变得复杂的是节点可以引用回较早的节点。 例如，

A-> C-> E->

我需要做的是获取一个堆栈列表，这些堆栈表示通过节点的路径，直到到达具有特定值的节点。 由于可能存在一些非常大的路径可用，因此我们可以尝试最多的节点。

List<Stack<Node>> paths = FindPaths(string ValueToFind, int MaxNumberNodes);

有谁有办法构建这个（或类似的东西）？ 我过去曾做过递归，但出于某种原因，我在思考这个问题时脑子里全是放屁。 我的问题指定了 lambda 表达式，但不一定需要使用 lambda。 我将不胜感激任何解决方案。

旁注：我从 aku 对这个递归的优秀答案中提升了课程。问题。 虽然他下面显示的优雅的解决方案遍历了树结构，但它似乎没有足够的灵活性来完成我需要的操作（例如，忽略圆形路径并跟踪成功的路径）。

Action<Node> traverse = null;
traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};
traverse(root);  // where root is the tree structure

编辑：

根据下面的评论和答案的输入，我在 CodeProject 中找到了一个出色的解决方案。 它使用A*寻路算法。 这是链接。

Answer 1

如果您的问题与寻路有关，您可能需要在 google 上搜索“A star”或“A*”。
它是一种常见且高效的寻路算法。 有关与您的问题直接相关的示例，请参阅本文。

您可能还想查看 Dijsktra 算法

Answer 2

我不确定您的预期输出是到达目标的所有路径、到达目标的最佳路径（通过某些指标，例如路径长度），还是只是 >任何实现目标的路径。

假设是后者，我将从递归策略开始，包括跟踪 Brann 概述的访问节点，并进行以下更改：

1. 添加参数来表示正在寻求的目标、成功路径的集合以及当前路径添加

2. 将当前路径（加上当前节点）添加到成功路径列表中。

3. 使用当前节点扩展当前路径，以创建在任何递归调用上传递的路径。

   使用当前节点扩展

4. 使用空路径和空的成功路径列表调用初始 ExploreGraph 调用。

完成后，您的算法将遍历整个图表，并且将捕获到达目标的不同路径。

这只是一个快速的草图，但您应该能够根据您的特定需求充实它。

Answer 3

我不知道你到底想要实现什么，但是这个循环引用问题通常是通过标记已经访问过的节点来解决的。
只需使用字典来跟踪已经访问过的节点，这样就不会循环。

例子 ：

  public void ExploreGraph(TreeNode tn, Dictionary<TreeNode, bool> visitednodes)
        {

            foreach (Treenode childnode in tn.Nodes)
            {
                if (!visitedNodes.ContainsKey(childnode))
                {
                    visitednodes.Add(childnode);
                    ExploreGraph(childnode, visitednodes);
                }
            }
        }