Java 代表来自 Testdome 的社交网络的收集问题

Question

给定一个代表社交网络的数据结构，编写一个函数来查找一定程度的朋友。一级好友为会员的直系好友，二级好友为会员除一级好友外的好友等

这个问题url：https://www.testdome.com/questions/java/friends/331

如何编写 getFriendsOfDegree(Member member, int degree) 方法？

 import java.util.ArrayList;
    import java.util.Collection;
    import java.util.List;

class Member {
    private String email;
    private Collection<Member> friends;

    public Member(String email) {
        this(email, new ArrayList<Member>());
    }

    public Member(String email, Collection<Member> friends) {
        this.email = email;
        this.friends = friends;
    }

    public String getEmail() {
        return email;
    }

    public Collection<Member> getFriends() {
        return friends;
    }

    public void addFriends(Collection<Member> friends) {
        this.friends.addAll(friends);
    }

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

public class Friends {
    public static List<Member> getFriendsOfDegree(Member member, int degree) {
        throw new UnsupportedOperationException("Waiting to be implemented.");
    }

    public static void main(String[] args) {
        Member me = new Member("me@test.com");
        Member myFriend = new Member("my.friend@test.com");
        Member myFriendsFriend = new Member("my.friends.friend@test.com");

        me.addFriend(myFriend);
        myFriend.addFriend(myFriendsFriend);

        for (Member friend : getFriendsOfDegree(me, 2))
            System.out.println(friend.getEmail());
        // Correct output:
        // my.friends.friend@test.com
    }
}

Answer 1

我们可以实施广度优先搜索来找出成员的第 n 个好友。创建一个Queue来存储每一层的朋友，创建一个HashSet来存储访问过的朋友。图中可能存在循环，即有朋友的朋友作为朋友，因此我们必须跟踪集合中访问过的朋友。在每一层中，获取当前成员的好友，并将其加入到队列中。不要忘记检查它之前是否访问过。

在每一层中，增加变量deg。如果deg等于degree，那么return就是Queue中的元素。您可以在下面找到它的实现。

public static List<Member> getFriendsOfDegree(Member member, int degree) {
   int deg = 0;
   Queue<Member> q = new LinkedList<>();
   HashSet<Member> visited = new HashSet<Member>();

   q.add(member);
   visited.add(member);

   while(!q.isEmpty()) {
         if(deg == degree) {
             List<Member> friends = new ArrayList<Member>();
             while(!q.isEmpty()) friends.add(q.poll());
             return friends;
         }
         deg++;
         int size = q.size();
         for(int i=0; i<size; i++) {
             Member mem = q.poll();
             for(Member friend: mem.getFriends()) {
                 if(!visited.contains(friend)) {
                     q.add(friend);
                     visited.add(friend);
                 }
             }
         }
     }
     return new LinkedList<Member>();  // cover the edge cases
 }

为了在函数的最后覆盖边缘情况 here、return new LinkedList<Member>()。如果给定成员没有 n(th) 度朋友，它只是 return 是一个空的 LinkedList。

我在网站上运行时的输出

Simple cases: Correct answer
Complex cases: Correct answer
Edge cases: Correct answer
Performance test: Correct answer

如果您不熟悉图形算法，尤其是 BFS，您可以查看 this 教程。

Java 代表来自 Testdome 的社交网络的收集问题

Java collection question for representing a social network from Testdome

java

algorithm

collections

graph