java - 循环列表中的递归调用

Question

我正在尝试循环用户列表以找到一个人。每个人都有一个 friend 列表。所以我正在使用递归调用来检查这个人是否在某人的 friend 列表中。

我的 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()));

    } 

所以在这里可以看到，我想知道 Angelina 是否在 john 的好友列表中。所以它应该回馈真实。负责的方法是:

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;

如您所见，如果您没有在递归调用的第一个分支中找到它，您就会提前退出。你不想要那个 - 你想继续直到找到它，或者没有任何东西可以搜索。

顺便说一句 - 您的单元测试没有帮助您，因为您的嵌套太深了。如果您进行一些单元测试，首先测试 friend - friend ，然后测试 friend - friend - friend ，等等，您就会开始看到哪里出了问题。

此外，另一方面:我不会使用 Stack(它是一个 legacy class)，而是使用 Deque ，它是 Java 6+ 的替代品。但是在这种情况下，我会使用 Set<User> 形式的 HashSet<User> ，因为它适合您的用例和 probably performance requirements 。我还会将列表变量类型设为 List<User> 而不是 ArrayList<User> 类和 UserImpl 方法中的 isInFriendsCycle，只是为了专注于契约而不是实现。