逐级打印好友连接

Question

我最近在一次采访中遇到了这个问题，而且做得很糟糕。

Setup:
Assume primitive Facebook. FB has Members.
class Member {
String name;
String email;
List<Member> friends;
}

问题： 代码打印社交图（成员 m）.m的直接朋友是1级朋友。 朋友的朋友是2级朋友.....等等 首先打印1级朋友。然后打印2级朋友....等等

void printSocialGraph (Member m){
//Your code here
}

我试图维护一个队列来存储每个级别的朋友，但我没有得到很远。知道我们如何在所有错误检查条件下解决它吗？

Answer 1

只需在搜索队列的末尾添加新的子项，直到没有更多子项。由于图形可以包含周期，因此还必须使用"访问"集来打破这些周期。

void printSocialGraph (Member m) {
  Queue<Member> queue = new LinkedList<>();
  Set<Member> visited = new HashSet<>();
  queue.add(m);
  while (!queue.isEmpty()) {
    Member member = queue.getFirst();
    if (!visited.contains(member)) {
      visited.add(member);
      System.out.println(member.name + ' ' + member.email);
      if (member.friends != null) {
        queue.addAll(member.friends);
      }  
    }
  }   
}

如果您还需要打印出成员所在的级别，那么最简单的方法可能是使用两个队列：一个用于当前级别，另一个用于下一个级别，在它们之间交换队列。