c# - 如何用递归方法替换内部 Foreach 循环

Question

我有点坚持创建一个通用的方法，该方法可以遍历有向图以根据最大深度获取所有可能的路线，例如:

所有来自 A 的最多 4 跳的路由返回以下串联路由:

ABCDC  
ABCDE  
ABCEB  
ADCDC  
ADCDE  
ADCEB  
ADEBC  
AEBCD  
AEBCE

路由数据是以下Json值:

"Routes": [
    {
      "From": "A",
      "To": "B",
      "Distance": 5
    },
    {
      "From": "A",
      "To": "D",
      "Distance": 5
    },
    {
      "From": "A",
      "To": "E",
      "Distance": 7
    },
    {
      "From": "B",
      "To": "C",
      "Distance": 4
    },
    {
      "From": "C",
      "To": "D",
      "Distance": 8
    },
    {
      "From": "C",
      "To": "E",
      "Distance": 2
    },
    {
      "From": "D",
      "To": "C",
      "Distance": 8
    },
    {
      "From": "D",
      "To": "E",
      "Distance": 6
    },
    {
      "From": "E",
      "To": "B",
      "Distance": 3
    }
]

我的内部循环，固定四次如下，开始是“A”，结束是“C”，int stops 值应该决定递归的数量，而不是硬编码循环。我们将不胜感激任何朝着正确方向提供的帮助或指导。

public void GetRoutes(string start, string end, int stops)
{
    var tempRoutes = graph.Routes;

    foreach(var route in tempRoutes.Where(x => x.From == start))
    {
        foreach(var innerRoute in tempRoutes.Where(x => x.From == route.To))
        {
            foreach(var innerRoute2 in tempRoutes.Where(x => x.From == innerRoute.To))
            {
                foreach(var innerRoute3 in tempRoutes.Where(x => x.From == innerRoute2.To))
                {
                    totalPath = start + route.To + innerRoute.To + innerRoute2.To + innerRoute3.To;

                    PathCounter.Add(totalPath, totalPath.Length);
                }
            }
        }
    }
}

Answer 1

尝试以下解决方案:

以下类模拟图中两个节点之间的链接:

public class NodeLink
{
    public string From { get; set; }
    public string To { get; set; }
}

下面的类可以递归地在图中搜索路径:

public class RouteFinder
{
    public IEnumerable<string> FindRoutes(NodeLink[] node_links, string start, string end, int max_length)
    {
        if (max_length == 0)
            yield break;

        if (start == end)
        {
            yield return start;
            yield break;
        }

        if (max_length == 1)
        {
            yield break;
        }

        foreach (var route in node_links.Where(x => x.From == start))
        {
            IEnumerable<string> sub_routes = FindRoutes(node_links, route.To, end, max_length - 1);

            foreach (string sub_route in sub_routes)
            {
                yield return start + sub_route;
            }
        }
    }
}

你可以这样使用它:

var node_links = new List<NodeLink>
{
    new NodeLink {From = "A", To = "B"},
    new NodeLink {From = "A", To = "C"},
    new NodeLink {From = "C", To = "D"},
    new NodeLink {From = "C", To = "E"},
    new NodeLink {From = "E", To = "F"},
    new NodeLink {From = "B", To = "F"}
};

RouteFinder finder = new RouteFinder();

foreach (string path in finder.FindRoutes(node_links.ToArray(), "A", "F", 4))
{
    Console.WriteLine(path);
}

这是我得到的输出:

ABF
ACEF