Chapter4Solutions.java 文件源码

/**
 * Route Between Nodes: Modified - Find whether there is a path between two nodes (A->B) in a bidirectional graph.
 *
 * Assumptions:
 *
 * Time complexity: O(n) where n is numer of nodes
 * Space complexity: O(n)
 */
public static boolean pathExistsBidirectional(IntNode a, IntNode b) {
  // BFS on both nodes at the same time
  Queue<IntNode> queueA = Queues.newArrayDeque();
  Queue<IntNode> queueB = Queues.newArrayDeque();
  Set<IntNode> visitedA = Sets.newHashSet();
  Set<IntNode> visitedB = Sets.newHashSet();

  visitedA.add(a);
  visitedB.add(b);
  queueA.add(a);
  queueB.add(b);

  while (!queueA.isEmpty() && !queueB.isEmpty()) {
    if (pathExistsBidirectionalHelper(queueA, visitedA, visitedB)) {
      return true;
    }
    if (pathExistsBidirectionalHelper(queueB, visitedB, visitedA)) {
      return true;
    }
  }

  return false;
}