Bidirectional Search in Graph

Algorithm

sq = Queue for BFS from start node

tq = Queue for BFS from end node

root[] = Array to store root of leaf nodes

visit[] = Array to store nodes that have been visited

while sq != empty and tq != empty
    perform next iteration for sq
    perform next iteration for tq
    save the root of a leaf node in the root array
    if we have visited the node of intersection
        save it
        break
   using node of intersection and root node, find the path

Implementation in Java

import java.io.*;
import java.util.*;
class graphc
{
    private int Nodes;
    private LinkedList<Integer>[] list;
    @SuppressWarnings("unchecked") public graphc(int y)
    {
        Nodes = y;
        list = new LinkedList[y];
        for (int l = 0; l < y; l++)
            list[l] = new LinkedList<Integer>();
    }
    public void Edge(int x, int y)
    {
        list[x].add(y);
        list[y].add(x);
    }
    public int Intersection(Boolean[] svisit, Boolean[] tvisit)
    {
        for (int l = 0; l < Nodes; l++)
        {
            if (svisit[l] && tvisit[l])
                return l;
        }
        return -1;
    }
    public void breadthfirst(Queue<Integer> q, Boolean[] visit, int[] root)
    {
        int present = q.poll();
        for (int l : list[present])
        {
            if (!visit[l])
            {
                root[l] = present;
                visit[l] = true;
                q.add(l);
            }
        }
    }
    public int intersect(int s, int t)
    {
        Boolean[] svisit = new Boolean[Nodes];
        Boolean[] tvisit = new Boolean[Nodes];
        int[] sroot = new int[Nodes];
        int[] troot = new int[Nodes];
        Queue<Integer> sq = new LinkedList<Integer>();
        Queue<Integer> tq = new LinkedList<Integer>();
        int intersectpoint = -1;
        for (int i = 0; i < Nodes; i++)
        {
            svisit[i] = false;
            tvisit[i] = false;
        }
        sq.add(s);
        svisit[s] = true;
        sroot[s] = -1;
        tq.add(t);
        tvisit[t] = true;
        troot[t] = -1;
        while (!sq.isEmpty() && !tq.isEmpty())
        {
            breadthfirst(sq, svisit, sroot);
            breadthfirst(tq, tvisit, troot);
            intersectpoint= Intersection(svisit, tvisit);
            if (intersectpoint != -1)
            {
                System.out.printf("Path exists \n");
                System.out.printf("Intersection point: %d\n", intersectpoint);
                print(sroot, troot, s, t, intersectpoint);
                System.exit(0);
            }
        }
        return -1;
    }
    public void print(int[] sroot, int[] troot, int s, int t, int Node)
    {
        LinkedList<Integer> way = new LinkedList<Integer>();
        way.add(Node);
        int l = Node;
        while (l != s)
        {
            way.add(sroot[l]);
            l = sroot[l];
        }
        Collections.reverse(way);
        l = Node;
        while (l != t)
        {
            way.add(troot[l]);
            l = troot[l];
        }
        for (int path : way)
            System.out.print(path + " ");
        System.out.println();
    }
}
public class Main
{
    public static void main(String[] args)
    {
        int n = 10, s = 0, t = 9;
        graphc graph = new graphc(n);
        graph.Edge(0, 1);
        graph.Edge(1, 2);
        graph.Edge(2, 2);
        graph.Edge(3, 4);
        graph.Edge(4, 7);
        graph.Edge(5, 7);
        graph.Edge(6, 0);
        graph.Edge(7, 5);
        graph.Edge(8, 9);
        if (graph.intersect(s, t) == -1)
            System.out.printf("Path doesn't exist");
    }
}

Output: Path doesn’t exist.

Complexity Analysis

🌊 Time Complexity

Let’s assume that the branching factor of the tree is bf and the distance between two vertices is len. The time complexity for bidirectional search would be O(bf^(len/2)).

🌊 Space Complexity

Since the space scales exponentially every time the branching is done. Also, we need to keep in mind there are two searches going on simultaneously which results in the division of length. Therefore, the space complexity would be O(bf^(len/2)).

BFS vs. Bidirectional Search

We will use the graph below to differentiate between Breadth First Search and Bidirectional Search. The start vertex is 2, and the end vertex is 10.

In Bidirectional Search, two searches will take place from two different directions, from Vertex 2 and Vertex 10. These vertices will start exploring their neighbor nodes to find the most suitable one to proceed. Vertex 2 will proceed towards 1 and Vertex 10 will move on to 9. Now Vertex 1 is given two options, Vertex 5 and Vertex 3. We observe that Vertex 3 seems more compatible. By suitable one, we mean that vertex that offers the minimum cost of traveling when looking for a path connecting two vertices.

Similarly, for Vertex 9, Vertex 7 seems more compatible. This way, exploration continues till an intersection point is received. We will trace back to find the complete path, which will be the shortest.

Path found: 2>1>3>6>7>9>10

You can refer to the image below to see the nodes approached while the Bidirectional Search is going on.

In BFS, the search starts from Vertex 2 and reaches Vertex 1 at the first iteration. The exploration starts, and each neighbor vertex consecutively explore their neighbors. This continues till the most suitable path is determined.

Path found: 2>1>3>6>7>9>10

You can refer to the image below to see the nodes approached while Breadth First Search is going on.

We can see that the exploration done in both cases differs to a recognizable extent. The iterations performed during BFS are more comparatively. This becomes more useful when the graphs used are large in saving traveling costs.

Frequently Asked Questions

Give an algorithm for postorder traversal in a Binary Tree.

Move to the node's left side (traverse left subtree).

Move to the node's right side (traverse right subtree).
Print the node's data.

List some disadvantages of using a graph data structure.

Some disadvantages of using a graph data structure are listed below.

The pointers used in graphs are complex to handle.

It may have huge memory complexity.

If represented using Adjacency Matrix, it does not allow parallel edges.

Difficult Multiplication

Mention a few real-life applications of a graph data structure.

A few real-life applications of a graph data structure are mentioned below.

Understanding, Visualizing, and Solving complex problems

Data Organization

Shortest Route Predictor

Circuits, Operating Systems, Networking sites, etc.

How many ways are there to represent a graph? Name them.

There are three ways in which we can represent a graph.

Set Representation

Sequential Representation

Linked Representation

Conclusion

To summarize the article, we looked at the problem statement, looked at every possible condition that could occur, understood the approach, went through the Algorithm, saw the implementation, tested the code against an example input, and did a time and space complexities analysis.

We hope the above discussion helped you understand and solve the problem better.

This will also help you learn how to approach any problem like this in the future.

For coders who want to solve more such questions, refer to the list below.

• Detect cycle in an undirected graph
• Number of Squareful Arrays
• Detect cycle in a directed graph
• Path with Maximum Probability
• Ninja and Flowers
• Shortest Path In Binary Matrix

Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can focus on interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help other ninjas grow.

Happy Coding!