рекурсивный поиск в java

Question

У меня проблема: У меня есть hashset of Pairs. Пара - пара ints. пара представляет «любит». скажем мой набор: < 1,2>, < 2,1>, < 3,1> < 6,7>, < 5,7>, < 2,6> это означает, что 1 любит 2 и 2 нравится 1 и 3 нравится 1 и так далее ...

То, что мне просят сделать, это посмотреть на эти отношения как на график и дать два числа, скажем, 2 и 6, я должен найти, есть ли маршрут в графике от 2 до 6 с не более чем 5 ребрами, соединяющими между собой ...

Как написать короткий рекурсивный метод, который вычисляет, существует ли маршрут? Я написал следующий код:

private boolean findPath(int from, int to, int count){ 
    System.out.println(from+" "+to+" "+count); 
    if(from==to && count<=5) 
     return true; 
    if(count>5) 
     return false; 
    Iterator<CookingParty.Pair> iter=likesSet.iterator(); 
    while(iter.hasNext()){ 
     Pair curr=iter.next(); 
     if(curr.likes==from && curr.liked==to){ 
      return true; 
     } 
     if(curr.likes==from) 
      return findPath(curr.liked, to, count+1); 

    } 

    return false; 
} 

проблема заключается в том, что он не будет продолжать идти по остальным возможностям когда один оказался неправ. Как я могу сменить его на работу?

это обновление:

private boolean findPath(int from, int to, int count){ 
System.out.println(from+" "+to+" "+count); 
    if(from==to && count<=5) 
     return true; 
    if(count>5) 
     return false; 
    Iterator<CookingParty.Pair> iter=likesSet.iterator(); 
    boolean found=false; 
    while(iter.hasNext() && !found){ 
     Pair curr=iter.next(); 
     if(curr.likes==from && curr.liked==to){ 
      found=true; 
      return found; 
     } 
     if(curr.likes==from) 
     return findPath(curr.liked, to, count+1); 

    } 

    return found; 

}

Answer 1

В настоящее время вы вернетесь, как только вы найдете пару, где curr.likes == from. Чтобы исследовать другие пути, вы не должны сразу возвращаться в цикл while, но пока вы еще не нашли путь, проверьте дополнительные возможности.

boolean found = false; 
while(iter.hasNext() && !found){ 
    // check a path 
} 
return found; 

Re update: Вы все еще возвращаетесь в цикле. Это нормально в случае, когда вы нашли путь, но вы абсолютно не должны возвращаться в общем случае. Если curr.likes == from и curr.liked != to, проверьте этот путь и обновите boolean, не возвращайтесь. Вернитесь после завершения цикла.

Answer 2

Для поиска пути в графе вы можете использовать в глубину или поиск в ширину. Глубина сначала традиционно рекурсивно, потому что она использует стек. Посмотрите на псевдокоде здесь:

http://en.wikipedia.org/wiki/Depth-first_search#Pseudocode