如何使用遞歸方法替換內部的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循環

回答

相關問題