逐级打印好友连接

Question

我最近在一次采访中遇到了这个问题并且做得非常糟糕.

Setup:
Assume primitive Facebook. FB has Members.

class Member {
String name;
String email;
List<Member> friends;
}

问题:代码printSocialGraph(成员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);
      }  
    }
  }   
}

如果您还需要打印成员所在的级别,那么最简单的可能是使用两个队列:一个用于当前级别,另一个用于下一个队列,在两者之间交换队列.