## 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.

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.

**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.

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