通过reccursion找到所有可能的路线

Question

因此，我一直在这方面努力，只是似乎无法解决这个问题。我有一个列有开始城市和目标城市的“道路”列表。通过递归，我必须找到所有可能的路线。我目前的代码只找到最长的路线。 我能做些什么来解决这个问题？

道路：

Colorado Springs,Denver 
Denver,Loveland 
Loveland,Fort Collins 
Loveland,Greeley 
Greeley,Fort Collins 
Fort Collins,Cheyenne 
Fort Collins,Laramie 
Laramie,Cheyenne 

电流输出：

All paths from Colorado Springs to Fort Collins are: 
1. [Colorado Springs, Denver, Loveland, Fort Collins] 
2. [Colorado Springs, Denver, Loveland, Greeley, Fort Collins] 
3. [Colorado Springs, Denver, Loveland, Greeley, Fort Collins, Loveland, Greeley, Fort Collins] 

编辑更新的代码： 现在我得到额外的输出...

public ArrayList<String> findPath2(String startCity, String goalCity, String oStartCity, ArrayList<String> route){ 

    //see if goal city possible 
    if(tester(goalCity) != true){ 
     return null; 
    } 

    ///Base Case//// 
    if(startCity.equals(goalCity)){ 
     route.add(goalCity); 
     String derp = route.toString(); 
     paths.add(derp); 
     System.out.println(derp); 
     //return route; 
    }else{ 
     for (int i = 0; i < theRoads.size(); i ++){ 
      if(theRoads.get(i).isFrom(startCity)){ 


       route.add(startCity); 
       findPath2(theRoads.get(i).endsAt(), goalCity, oStartCity, route); 

       //System.out.println(route); 
       //course = startCity + " -> " + course; 

       for (int l = i+1; l < theRoads.size(); l ++){ 
        if(theRoads.get(l).isFrom(startCity) && !(theRoads.get(l).startsAt().equals(goalCity))){ 
         System.out.println("SPLIT"); 

         route.remove(goalCity); 
         findPath2(theRoads.get(l).endsAt(), goalCity, oStartCity, route); 
         System.out.println("SPLIT RETURNING"); 

        } 
       } 

       //return route; 
      } 
     } 
    } 
    return route; 
} 

而且我所有的代码，如果任何人都有兴趣： http://pastebin.com/3yeBU2fn

2ND编辑：@Vandale

仍然不能得到它的工作，但这样的事情？

public ArrayList<String> findPath2(String startCity, String goalCity, ArrayList<String> route){ 

     ArrayList<String> course = new ArrayList<>(); 

     if(startCity.equals(goalCity)){ 
      course.add(startCity); 
     }else{ 
      route.add(startCity); 
      for (int i = 0; i < theRoads.size(); i ++){ 
       if(theRoads.get(i).isFrom(startCity)){ 

        for (int l = 0; l < route.size(); l ++){ 
         //check if city has already been visited && if its possible to get to goal city (not sure if this works) 
         if(!(route.get(l).equals(startCity)) && (findPath2(theRoads.get(l).endsAt(), goalCity, route).equals(goalCity))){ 

          course.add(startCity + "->" + findPath2(theRoads.get(l).endsAt(), goalCity, route)); 

         } 
        } 
       } 
      } 
      route.remove(startCity); 
     } 
     System.out.println(course); 
     return course; 
    } 

感谢您的帮助！

Answer 1

oStartCity在您的方法的主体中从未实际使用过，因此您可以摆脱它。

一种方式来做到这一点是因为遵循

Create empty list of paths 
if at target city 
    add current city to paths 
else 
    add current city to list of visited cities 
    for each city connected to this 
     if not already visited city and city has path to the target city 
      add current city + each one of connected cities paths to paths 
    remove current city from list of visited cities 
return paths 

为了保持跟踪你已经访问过的城市，你应该使用类似一个HashSet，应通过在作为参数传递给函数。

需要注意的一件事是，如果没有到目的地城市的路径，那么该函数将返回一个空列表，您可以使用它来检查是否有任何路径。如果你使用这个，你不需要打电话给测试人员。

Answer 2

所以我想通了，希望这有助于未来的人！

public void findAllPaths(String startCity, String goalCity){ 
     clearPaths(); 
     findPathHelps(startCity, goalCity, ""); 
    } 

    private void findPathHelps(String startCity, String goalCity, String path){ 
     //base 
     if(startCity.equals(goalCity)) 
      paths.add(path + goalCity); 
     //cycle through 
     for(Road road : this.roads) 
      if(road.isFrom(startCity)) 
       //recursion and stuff 
      findPathHelps(road.endsAt(), goalCity, path+startCity+"->"); 
    }