双方向BFSパターン

- 双方向BFSによる最短経路探索
public int bidirectionalBFS(Graph graph, int start, int end) {
    if (start == end) return 0;
    
    // 両方向からの訪問セットとキュー
    Set<Integer> visitedForward = new HashSet<>();
    Set<Integer> visitedBackward = new HashSet<>();
    Queue<Integer> queueForward = new LinkedList<>();
    Queue<Integer> queueBackward = new LinkedList<>();
    Map<Integer, Integer> distanceForward = new HashMap<>();
    Map<Integer, Integer> distanceBackward = new HashMap<>();
    
    // 初期化
    visitedForward.add(start);
    visitedBackward.add(end);
    queueForward.offer(start);
    queueBackward.offer(end);
    distanceForward.put(start, 0);
    distanceBackward.put(end, 0);
    
    // 両方向からBFSを実行
    while (!queueForward.isEmpty() && !queueBackward.isEmpty()) {
        // サイズが小さい方のキューから探索を進める
        if (queueForward.size() <= queueBackward.size()) {
            int shortestPath = expandFrontier(graph, queueForward, visitedForward, visitedBackward, distanceForward, distanceBackward);
            if (shortestPath != -1) return shortestPath;
        } else {
            int shortestPath = expandFrontier(graph, queueBackward, visitedBackward, visitedForward, distanceBackward, distanceForward);
            if (shortestPath != -1) return shortestPath;
        }
    }
    
    return -1; // 経路が見つからない場合
}

private int expandFrontier(Graph graph, Queue<Integer> queue, Set<Integer> visited, Set<Integer> visitedOpposite,
                          Map<Integer, Integer> distance, Map<Integer, Integer> distanceOpposite) {
    int node = queue.poll();
    int currentDistance = distance.get(node);
    
    for (int neighbor : graph.getNeighbors(node)) {
        if (!visited.contains(neighbor)) {
            visited.add(neighbor);
            queue.offer(neighbor);
            distance.put(neighbor, currentDistance + 1);
            
            // 反対側の探索と交わるかチェック
            if (visitedOpposite.contains(neighbor)) {
                return currentDistance + 1 + distanceOpposite.get(neighbor);
            }
        }
    }
    
    return -1; // この拡張では交差点が見つからなかった
}