Bidirectional Search

About

Bidirectional search is an advanced graph search algorithm that runs two simultaneous searches:

• Forward Search: Starts from the initial node.

• Backward Search: Starts from the goal node.

• The search stops when both searches meet in the middle.

Implementation Strategy

To implement bidirectional search:

1. Use two queues for BFS traversal from the start and goal nodes.

2. Maintain two visited sets to track explored nodes.

3. Stop when the search frontiers meet.

Implementation of Bidirectional Search

Graph Representation (Adjacency List)

import java.util.*;

class Graph {
    private final Map<Integer, List<Integer>> adjList;

    public Graph() {
        this.adjList = new HashMap<>();
    }

    // Add edge in an undirected graph
    public void addEdge(int source, int destination) {
        adjList.putIfAbsent(source, new ArrayList<>());
        adjList.putIfAbsent(destination, new ArrayList<>());
        adjList.get(source).add(destination);
        adjList.get(destination).add(source);
    }

    // Returns the adjacency list
    public List<Integer> getNeighbors(int node) {
        return adjList.getOrDefault(node, new ArrayList<>());
    }

    // Print the graph
    public void printGraph() {
        for (var entry : adjList.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

Bidirectional Search Algorithm

class BidirectionalSearch {
    private final Graph graph;

    public BidirectionalSearch(Graph graph) {
        this.graph = graph;
    }

    public boolean search(int start, int goal) {
        if (start == goal) {
            System.out.println("Start is the same as goal.");
            return true;
        }

        // Queues for BFS from both directions
        Queue<Integer> forwardQueue = new LinkedList<>();
        Queue<Integer> backwardQueue = new LinkedList<>();

        // Visited sets
        Set<Integer> forwardVisited = new HashSet<>();
        Set<Integer> backwardVisited = new HashSet<>();

        // Initialize queues and visited sets
        forwardQueue.add(start);
        forwardVisited.add(start);

        backwardQueue.add(goal);
        backwardVisited.add(goal);

        while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty()) {
            // Expand one level from start
            if (bfsStep(forwardQueue, forwardVisited, backwardVisited)) {
                System.out.println("Path found!");
                return true;
            }

            // Expand one level from goal
            if (bfsStep(backwardQueue, backwardVisited, forwardVisited)) {
                System.out.println("Path found!");
                return true;
            }
        }

        System.out.println("No path found.");
        return false;
    }

    private boolean bfsStep(Queue<Integer> queue, Set<Integer> visited, Set<Integer> oppositeVisited) {
        if (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : graph.getNeighbors(node)) {
                if (oppositeVisited.contains(neighbor)) {
                    return true;  // The two searches meet
                }
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        return false;
    }
}

Testing the Algorithm

public class BidirectionalSearchTest {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);
        graph.addEdge(4, 6);
        graph.addEdge(5, 6);

        System.out.println("Graph representation:");
        graph.printGraph();

        BidirectionalSearch search = new BidirectionalSearch(graph);
        System.out.println("Finding path from 1 to 6:");
        boolean pathExists = search.search(1, 6);
        System.out.println("Path exists: " + pathExists);
        
        /* Output:
        Graph representation:
        1 -> [2, 3]
        2 -> [1, 4]
        3 -> [1, 5]
        4 -> [2, 6]
        5 -> [3, 6]
        6 -> [4, 5]
        
        Finding path from 1 to 6:
        Path found!
        Path exists: true
        */
    }
}

Time Complexity Analysis

Search Algorithm	Time Complexity
BFS (Single Direction)	O(b^d)
Bidirectional Search	O(b^{d/2})

Where:

• b = branching factor (average number of neighbors per node)

• d = depth of the shortest path

Why is Bidirectional Search Faster?

• BFS explores b^d nodes, but bidirectional search only explore 2xb^{d/2} nodes.

• This leads to an exponential reduction in search space.

For example, if b=10 and d=6:

• BFS explores 10^6 = 1,000,000 nodes.

• Bidirectional search explores 2 x 10^3 = 2,000 nodes, which is significantly smaller.