如何使用递归方法替换内部的Foreach循环

我有点卡在创建一种通用方法，该方法可以通过有向图循环来获取基于最大深度数的所有可能路径，例如：如何使用递归方法替换内部的Foreach循环

从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 
    } 
]

我的客栈呃循环，固定四次是以下内容，其中start将是“A”，end将是“C”，int停止值应该确定递归量，而不是硬编码循环。任何对正确方向的帮助或指导都会大大降低。

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

来源

2015-09-25 hamid

你知道如何编写递归代码吗？如果没有，那么堆栈溢出并不是真正适合你获得这种教育的地方;足以回答这方面问题的全面解释将过于宽泛。如果你知道如何编写递归代码，那么请提供[一个很好的，_minimal_，_complete_代码示例]（https://stackoverflow.com/help/mcve），它清楚地显示了你迄今为止所尝试的内容，以及一个详细解释代码的作用以及与你想要的不同。 –

请注意，基本思想是，您将在递归方法中包含一个参数，指定还有多少“跳”要遍历。在每次递归调用中，您都会传递一个比传递给当前调用的值小1的值。 –

你需要一个'if-else'来检查递归调用的次数（'if（stops> 0）'），这个数字是'int stops'。在每次调用中，“stops”必须递减。在if'块内部放置一个循环，调用方法本身并在'else'块内放置最后应该做的事情。您可能需要发送更多像查询这样的参数，以便您知道每次调用的位置。 –

请尝试以下解决方案：

下面的类模型图中的两个节点之间的链接：

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

来源

2015-09-25 20:52:21

您忘记了distance属性：P –

它与'max_length'参数相同;） –

@YacoubMassad - 谢谢，请试试看。现在我可以通过不减少最大值来查看出错位置。 – hamid

这是我使用递归最终落实。

  private List<string> GetRouteMap(string start, int max) 
    { 
     var startNode = GetNode(start); 
     List<string> selectedRoutes = new List<string>(); 

     //safety check 
     if(max == 0) 
     { 
      selectedRoutes.Add(start.ToString()); 
      return selectedRoutes; 
     } 

     Edge[] possibleRoutes = GetRoutes(startNode); 
     foreach(Edge edge in possibleRoutes) 
     { 
      //recursive call until max==0 
      List<string> routeMap= GetRouteMap(edge.To.Name, max - 1, exact); 

      foreach(string route in routeMap) 
      { 
       selectedRoutes.Add(startNode.Name + route); 
      } 
     } 

     return selectedRoutes; 
    }

这将返回两个节点之间的所有可能的路由，其中包含n个停止位，如int max参数所指定的。

来源

2015-09-26 11:47:29 hamid

如何使用递归方法替换内部的Foreach循环

回答

相关问题