循环列表中的递归调用

Question

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

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

所以 class 是：

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

我会按如下方式实现它：

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 2

带有标记的递归算法的伪代码：

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

Answer 3

替换

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

和

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

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

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

另外，换句话说：我不会使用 Stack（它是 legacy class) use Deque instead, which is the Java 6+ replacement. However in this case I would use a Set<User> in the form HashSet<User> as it fits your use case and probably performance requirements。我也会将列表变量类型设为 List<User> 而不是ArrayList<User> 在你的 UserImpl class 和 isInFriendsCycle 方法中，只是为了专注于合同而不是实施。

循环列表中的递归调用

recursive call in looping a list

java

algorithm

graph-algorithm