рекурсивный вызов в цикле списка

Question

Я пытаюсь зациклить список пользователей, чтобы найти человека. У каждого человека есть список друзей. Поэтому я использую рекурсивный вызов, чтобы проверить, находится ли человек в списке друзей someones.

тест Мой Junit это выглядеть

@Test 
    public void IsInFriendsCicle() throws UserAlreadyInFriendListException, NoFriendFoundException, UsersNotConnectedException { 
     User one = new UserImpl("John","Snow"); 
     User two = new UserImpl("Richard","Gerns"); 
     User three = new UserImpl("Natalie","Portman"); 
     User four = new UserImpl("Brad","Pitt"); 
     User five = new UserImpl("Angelina","Jolie"); 
     one.addFriend(two); 
     two.addFriend(three); 
     three.addFriend(four); 
     four.addFriend(five); 
     assertTrue(one.isInFriendsCycle(five, one.getFriends(), new Stack())); 

    } 

Так как это можно увидеть здесь, я хочу знать, если Анджелина находится в списке друзей сортире. Поэтому он должен вернуть истину. Ответственный метод для этого:

public boolean isInFriendsCycle(User userToFind, ArrayList<User> list, Stack stack){ 
    Stack s = stack; 
    ArrayList<User> groupList = list; 
    if(groupList.contains(userToFind)){ 
     return true; 
    }else{ 
     for (User user : groupList) { 
      if(!s.contains(user)){ 
       s.push(user); 
       if(user.getFriends().contains(userToFind)){ 
        return true; 
       }else{ 
        return isInFriendsCycle(userToFind, user.getFriends(), s); 
       } 
       } 
     }  
    } 
    return false; 
} 

Так как класс:

public class UserImpl implements User{ 

    private String name; 
    private String surname; 
    private static int count = 0; 
    private int id; 
    private ArrayList<User> friends; 
    private ArrayList<Message> messagebox; 
    final static Logger logger = Logger.getLogger(UserImpl.class); 

    public UserImpl(String name, String surname) { 

     this.name = name; 
     this.surname = surname; 
     this.id = ++count; 
     this.friends = new ArrayList<User>(); 
     this.messagebox = new ArrayList<Message>(); 
    } 
@Override 
    public User addFriend(User person) throws UserAlreadyInFriendListException,IllegalArgumentException{ 
     if(this.getFriends().contains(person)){ 
      throw new UserAlreadyInFriendListException("user is already in the friendlist"); 
     }else if(person == null || this.equals(person)){ 
      throw new IllegalArgumentException("parameter is null or user trying to add himself as friend");  
     }else{ 
      this.getFriends().add(person); 
      person.getFriends().add(this); 
      logger.debug(this.name + " added the user "+person.getName()); 
      return person; 
     } 

    } 
@Override 
    public boolean equals(Object obj) { 
     if (obj == null) { 
      return false; 
     } 
     if (getClass() != obj.getClass()) { 
      return false; 
     } 
     final UserImpl other = (UserImpl) obj; 

     if (this.id != other.id) { 
      return false; 
     } 
     return true; 
    } 
} 

Существует проблема со стеком каким-то образом. Я использую его, чтобы отметить людей, поэтому я не попадаю в бесконечный цикл. Существует причина для передачи user.getFriends(), поэтому он должен оставаться таким образом. Любая помощь будет оценена!

Answer 1

заменить

return isInFriendsCycle(userToFind, user.getFriends(), s); 

с

if (isInFriendsCycle(userToFind, user.getFriends(), s)) return true; 

Как у вас есть, вы преждевременно выходите, если вы не сделали найдите его в первой ветке рекурсивного вызова. Вы не хотите этого - вы хотите продолжить, пока не найдете его, или вам нечего искать.

Как в стороне - ваш юнит-тест не помог вам, так как вы сделали слишком много гнездования. Если у вас было несколько юнит-тестов, сначала проверяя друга-друга, потом друга-друга-друга и т. Д., Вы бы начали видеть, где это происходит.

Кроме того, как другая сторона: я бы не использовать Stack (это legacy class) использует вместо Deque, который является Java 6+ замены. Однако в этом случае я бы использовал Set<User> в форме HashSet<User>, так как он подходит для вашего прецедента и probably performance requirements. Я бы также сделал типы переменных списка List<User> не ArrayList<User> внутри вашего класса UserImpl и isInFriendsCycle, просто чтобы сосредоточиться на контрактах, а не на реализации.

Answer 2

Я бы реализовать его следующим образом:

private Set<User> friends = new HashSet<User>(); 

public void addFriend(User friend) { 
    friends.add(friend); 
} 

public boolean isImmediateFriend(User user) { 
    return friends.contains(user); 
} 

public boolean isInFriendNetwork(User user) { 
    Set<User> visited = new HashSet<>(); 
    List<User> stack = new LinkedList<>(); 

    stack.push(this); 

    while (!stack.isEmpty()) { 
     User current = stack.removeFirst(); 
     if (current.isImmediateFriend(user)) { 
      return true; 
     } 
     visited.add(current); 

     for (User friend : current.getFriends()) { 
      // never visit the same user twice 
      if (!visited.contains(friend)) { 
      stack.addLast(friend); 
      } 
     } 
    } 
    return false; 
} 

Answer 3

псевдокод для рекурсивного алгоритма с маркировкой:

IsFriendOf(A, B): 
    if A == B: 
     return True 

    B.Marked= True 
    for all C in B.Friends: 
     if not C.Marked and IsFriendOf(A, C): 
      B.Marked= False 
      return True 

    B.Marked= False 
    return False