Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Algorithm
3.1.
Implementation in Java
3.1.1.
Complexity Analysis
4.
BFS vs. Bidirectional Search
5.
Frequently Asked Questions
5.1.
Give an algorithm for postorder traversal in a Binary Tree.
5.2.
List some disadvantages of using a graph data structure.
5.3.
Mention a few real-life applications of a graph data structure.
5.4.
How many ways are there to represent a graph? Name them.
6.
Conclusion
Last Updated: Mar 27, 2024
Hard

Bidirectional Search in Graph

Author Rupal Saluja
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will understand a very interesting problem based on Graph data structure. The problem examines how bidirectional search works in a graph data structure. Searching in Graph is very popular and has many applications. Potential applications of graph search include employee recruitment, shopping filters, marketing, online dating, job searches, and many more.

Representation of Graph

Through this problem, we will learn how to find the shortest path between two vertices using a bidirectional search. Firstly, we will examine the problem statement, learn about the Binary Search tree data structure, and decide on the optimum approach. Then we will proceed toward the implementation in the programming languages.

Notion of Programming

What is a Graph?

A graph is one of the most used data structures. It contains a finite set of vertices and a set of edges that connect those vertices. Any edge pair, say (4,3), denotes that vertex 4 is connected to 3 through this edge.

A Graph

There are two types of graphs, directed and undirected.

Directed graphs are those whose vertices are connected by directed edges, marked using arrows. On the other hand, undirected graphs are those whose vertices are connected by undirected edges. The one in the image above is the undirected graph.

Also, there are two kinds of representations in which we present a graph, Adjacency List and Adjacency Matrix. We can get an idea of their forms using their names.

The adjacency list is an array of lists. The array size is equal to the number of nodes in a graph. Adjacency Matrix is a two-dimensional array of order n*n in which ‘n’ is the number of nodes in a graph. 

Read also: Application of graph data structure

What is Bidirectional Search?

Bidirectional Search is a Graph Search Algorithm that tends to find the shortest path between two vertices of a graph. Two BFS traversals are performed simultaneously, one from the start vertex and the other from the end vertex. Two subtrees replace one single tree, and the search is stopped at that particular point when both subtrees intersect. Thus, it is faster and reduces the time and exploration requirements. 

Problem Statement

We are given a graph that has n nodes. We must find if any path exists or not between two of its vertices. The implementation will output the confirmation, intersection point, and path if any path exists.
If no path exists, the implementation will directly output that path does not exist. Here, we assume that all the nodes’ values are positive. 

Let us understand this with the help of a few examples. We will use the same graph.

Sample Examples

🍀 Example 1: When the graph is well connected.

Explanation:

The graph in the above example seems properly connected. There are fewer chances that the given edges will not connect any node. Suppose we want to check if any path exists between vertex 4 and vertex 7. Two searches will be initiated, one from vertex 4 and the other from vertex 7. The vertices start exploring their neighbor nodes to find the most suitable one. By suitable one, we mean that vertex that offers the minimum cost of traveling when looking for a path connecting two vertices. Both the searches meet at vertex 5. 

The path from Vertex 4: 4>1>5
The path from Vertex 7: 7>6>5
Complete Path: 4>1>5>6>7 

 

We know we have found a path and will stop the search.


We will take one more case. Now, we want to check if any path exists between vertex 0 and vertex 10. Again, two searches will be initiated, one from vertex 0 and the other from vertex 10. The vertices start exploring their neighbor nodes to find the most suitable one. By suitable one, we mean that vertex that offers the minimum cost of traveling when looking for a path connecting two vertices. Both the searches meet at a vertex 6.

The path from Vertex 0: 0>1>5>6
The path from Vertex 10: 10>9>7>6
Complete Path: 0>1>5>6>7>9>10

 

We know we have found a path and will stop the search. It would be best if you observed that unnecessary exploration had been avoided and we got the shortest path.


🍀 Example 2: When the graph is not properly connected

Explanation:

We have taken a disconnected graph in this example. There are comparatively more chances that edges will connect every mode present. We will use two contrary cases. Suppose we want to check if any path exists between vertex 4 and vertex 7. Two searches will be initiated, one from vertex 4 and the other from vertex 7. The vertices start exploring their neighbor nodes to find the most suitable one. Both the searches will never meet because they didn’t find any suitable node. The output has to be ‘the path doesn’t exist’. Similarly, if we check if any path exists between vertex 0 and vertex 14 or not, we will get the same output.

But, if we check for some other two vertices, say vertex 3 and vertex 10, both the searches will meet at vertex 7. Then, we will search.

The path from Vertex 3: 3>6>7
The path from Vertex 10: 10>9>7
Complete Path: 3>6>7>9>10
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.


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!

Previous article
Maximum Bipartite Matching in Graph
Next article
Introduction and Properties of Minimum Spanning Tree
Live masterclass