> For the complete documentation index, see [llms.txt](https://www.pranaypourkar.co.in/the-programmers-guide/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.pranaypourkar.co.in/the-programmers-guide/algorithm/data-structure-implementation/custom-graph/bidirectional-search.md).

# 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)**

```java
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**

```java
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**

```java
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.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://www.pranaypourkar.co.in/the-programmers-guide/algorithm/data-structure-implementation/custom-graph/bidirectional-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.