双向bfs

双向bfs的两个搜索方向各自维护，除了queue队列待扩展它的邻居节点、还有个enqueued映射记录当前方向已遇到哪些节点（不要用toVisit、visited这样容易混淆的命名），这样在一个方向搜索时就能知道另一个方向是否遇到过当前节点。queue和enqueued都是关于PathNode类型的，PathNode要在遍历时记录路径链表：{ personId, previous: PathNode }，因此跟bfs遍历相关的BFSData是：{ queue: queue, enqueued: map<personId, PathNode> }。双向bfs就是每个方向轮流地，搜索一层并看搜索的这层中有没有已被另一方向遇到过的节点。若有“碰撞节点”，就能合并两个搜索方向的路径。参见ctci p375，例子中有着Person类型和personId=>Person的映射，这里改成PathNode中存personId。

// srcData、destData指BFSData
while (!srcData.queue.isEmpty() && !destData.queue.isEmpty()) {
  Integer collision = searchOneLevel(srcData, destData, mapFromIdToPerson); // srcData搜索一层
  if (collision != null) return mergePaths(srcData, destData, collision);
  collision = searchOneLevel(destData, srcData, mapFromIdToPerson); // destData搜索一层
  if (collision != null) return mergePaths(srcData, destData, collision);  
}
return null;

Integer searchOneLevel(BFSData first, BFSData second, HasMap<Integer, Person> mapFromIdToPerson) {
  int count = first.queue.size(); // 只搜索一层
  for (int i = 0; i < count; i++) {
    PathNode node = first.queue.poll();
    int personId = node.getPersonId();
    if (second.enqueued.containsKey(personId)) { // 节点有碰撞
      return personId;
    }
    // 处理当前节点
    Person person = mapFromIdToPerson.get(personId);
    ArrayList<Integer> friendIds = person.getFriendIds();
    for (int friendId : friendIds) {
      if (!first.enqueued.containsKey(friendId)) {
        PathNode next = new PathNode(friendId, node);
        first.enqueued.put(friendId, next);
        first.queue.add(next);
      }
    }
  }
  return null;
}

另一例子见ctci p607，其中PathNode：{ word, previous: PathNode }，BFSData：{ queue: queue, enqueued: map<word, PathNode> }。