递归lambda表达式通过有向图找到路径？-Java 学习之路

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

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

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

使这种复杂化的原因是节点可以引用回早期节点 . 例如，

A - > C - > E - > A.

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

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

有没有人有办法 Build 这个（或类似的东西）？我过去做过递归，但由于某种原因，我正在考虑这个问题 . 我的问题指定了一个lambda表达式，但不一定需要使用lambda . 我很感激任何解决方案 .

旁注：我从aku的优秀答案中提升了 class this recursion question . 虽然下面显示的优雅解决方案遍历树结构，但它似乎没有足够的灵活性来完成我需要的工作（例如，解除圆形路径和成功的轨道路径） .

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

Edit ：

根据以下评论和答案的输入，我在CodeProject中找到了一个很好的解决方案 . 它使用A *路径查找算法 . Here is the link.

3 回答

1

如果您的问题与寻路相关，您可能需要谷歌搜索"A star"或"A*" . 它是一种通用而有效的寻路算法 . 有关与您的问题直接相关的示例，请参阅this article .

您可能还想查看Dijsktra Algorithm

回复于 2024-05-02T13:09:20+08:00
5
我不确定您的预期输出是否是目标的所有路径，目标的最佳路径（通过某个指标，例如路径长度），或者只是目标的任何路径 .

假设后者，我将从递归策略开始，包括跟踪Brann概述的访问节点，并进行以下更改：
- 添加参数以表示所寻求的目标，成功路径的集合以及从一开始的当前路径 .
- 输入与目标匹配的节点时，将当前路径（加上当前节点）添加到成功路径列表中 .
- 使用当前节点扩展当前路径以创建在任何递归调用上传递的路径 .
- 使用空路径和成功路径的空列表调用初始 ExploreGraph 调用 .
完成后，您的算法将遍历整个图形，并且将捕获到目标的不同路径 .

这只是一个快速草图，但您应该能够根据您的特定需求进行充实 .
回复于 2024-05-02T13:09:20+08:00

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

示例：

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);
                }
            }
        }

回复于 2024-05-02T13:09:20+08:00

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

3 回答

相关问题