CODEWITHSUNDEEP
javaalgorithmrecursiongraphroutes
mary
mary

Reputation: 919

recursive search in java

I have the following problem: I have a hashset of Pairs. Pair is a pair of ints. the pair represents "likes". let's say my set is :<1,2>,<2,1>,<3,1>,<6,7>,<5,7>,<2,6> this means 1 likes 2 and 2 likes 1 and 3 likes 1 and so on...

What I'm requested to do is to look at those relations as a graph and given two numbers let's say 2 and 6 I have to find whether there is a route in a graph from 2 to 6 with at most 5 edges connecting between them...

how to write a short recursive method that calculates if the route exists? I wrote the following code:

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

the problem is that it won't continue going over the rest of the possibilities once one was found to be wrong. how can I change it to work?

this is the update:

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;

}

Upvotes: 0

Views: 344

Answers (2)

Daniel Fischer
Daniel Fischer

Reputation: 183878

Currently you return as soon as you find a pair where curr.likes == from. To explore also other paths, you mustn't immediately return in the while loop, but while you haven't yet found a path, check for further possibilities.

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

Re update: You are still returning in the loop. That's okay in the case where you found a path, but you absolutely must not return in the general case. If curr.likes == from and curr.liked != to, check that path and update the boolean, do not return. Return after the loop has finished.

Upvotes: 1

Tudor
Tudor

Reputation: 62439

To search for a path in a graph you can use Depth-First or Breadth-First search. Depth-first is traditionally recursive because it uses a stack. Have a look at the pseudocode here:

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

Upvotes: 1

Related Questions