递归树搜索返回错误的结果

本文关键字：结果 错误 返回 搜索 递归 | 更新日期: 2023-09-27 18:00:14

我有一个树递归函数的实现。它获取从A到D的所有可能路径。

递归函数为：

private static List<Path> GetPath(int depth, Path path)
{
    if (depth == nodes.Length) 
    {
        return new List<Path> { path };
    }
    else 
    {
        var result = new List<Path>();
        foreach(var link in nodes[depth].Links)
        {
            Node node = new Node { Name = nodes[depth].Name, Links = new[] { link } };
            path.Add(node);
            result.AddRange(
                GetPath(
                    depth+1, path));
        }
        return result;
    }
}

预期结果应为：

A1-B2->C3->D4
A1-B5->C3->D4

但是，返回的路径是相同的，并且它们包括两次所有可能的节点。

这个函数出了什么问题？

递归树搜索返回错误的结果

foreach(var link in nodes[depth].Links)
{
    Node node = new Node { Name = nodes[depth].Name, Links = new[] { link } };
    path.Add(node);

在附加下一个节点之前，您可能打算为此处找到的每个节点创建一个新路径（它是path的副本）。

正如@moreON的建议，我将克隆函数添加到类Path中，并修改循环，在循环中我复制到路径的新实例：

public class Path : List<Node>
{
    public override string ToString()
    {
        String s = "";
        foreach (var node in this)
        {
            s += node.Name + node.Links[0] + "->";
        }
        return s;
    }
    public Path Clone()
    {
        var newPath = new Path();
        ForEach(x => newPath.Add(new Node {Name = x.Name, Links = new int[] {x.Links[0]}}));
        return newPath;
    }
}
    private static List<Path> GetPath(int depth, Path path)
    {
        if (depth == nodes.Length)
        {
            return new List<Path> { path };
        }
        else
        {
            var result = new List<Path>();
            foreach (var link in nodes[depth].Links)
            {
                Node node = new Node { Name = nodes[depth].Name, Links = new[] { link } };
                var currentPath = path.Clone();
                currentPath.Add(node);
                result.AddRange(GetPath(depth + 1, currentPath));
            }
            return result;
        }
    }

希望得到帮助。

相关文章：