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

Question

У меня следующая проблема: У меня есть хэш-сет пар. Пара - это пара целых. пара представляет «лайки». скажем, мой набор: <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;

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

Answer 2

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

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