1.
Introduction
2.
Example
3.
Algorithm Used
3.1.
Implementation in C++
3.1.1.
Output:
3.2.
Implementation in Java
3.2.1.
Output:
4.
Complexities Analysis
5.
5.1.
Best First Search uses which data structure?
5.2.
What is the advantage of the best first search?
5.3.
Is Informed Search Complete?
5.4.
Why is A * better than Best First Search?
5.5.
What is Graph?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Best First Search or Informed Search

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

## Introduction

This article will discuss a famous Data Structure (Graph) Problem, i.e., Best First Search or Informed Search.

Best First Search or Informed Search is a traversal technique of a tree traversal that uses an evaluation function to decide the most promising adjacent to be visited next and then explored.

It is different from BFS and DFS Algorithm because, in both, we can consider any of the adjacent as the next node without considering any cost function.

Let's see an example to better understand Best First Search or Informed Search.

## Example

Suppose we start from source "A" to goal "J" in this example.

Considering the given cost and the Best First Search.

The PriorityQueue initially contains A.

We remove A from the PriorityQueue and process the unvisited neighbours of A to PriorityQueue.

Now, the PriorityQueue contains {B,D,C}. Here D is put before C as D has the lesser cost.

We remove B and process the unvisited neighbours of B to PriorityQueue.

Now, the PriorityQueue contains {D,C,F,E}.

We remove D and process the unvisited neighbours of C to PriorityQueue.

Now, the PriorityQueue contains {C,I,F,E}.

We remove C from the PriorityQueue and process the unvisited neighbours of B to PriorityQueue.

Now, the PriorityQueue contains {I,F,E,G,H}.

Now, We remove I from the PriorityQueue.

Since our goal is "J" and J is the neighbour of I.

Therefore, we return.

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 Used

The algorithm used is similar to that of the BFS Search. The only difference is to use PriorityQueue instead of Queue to store the costs of nodes with the lowest evaluation function value.

The first is to create an empty PriorityQueue, Suppose, PriorityQueue pq;

Then Insert "element" in pq, pq.insert(element) and until the PriorityQueue is empty, we do u = PriorityQueue.DeleteMin and

Run an if-else statement where

If u is the goal, then we exit.

else

For each neighbour v of u

If v = "Unvisited"

Then Mark v = "Visited"

And do pq.insert(v)

and Mark u "Examined".

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
vector<vector<pi>> graph;
// Function to add edges to a graph
void addedge(int x, int y, int cost)
{
graph[x].push_back(make_pair(cost, y));
graph[y].push_back(make_pair(cost, x));
}

//Driver Code
int main()
{
//Number of Nodes
int v = 14;
graph.resize(v);

int source = 0;
int target = 7;
int n=v;

vector<bool> visited(n, false);
// Priority Queue is sorted by the first value of the pair.
priority_queue<pi, vector<pi>, greater<pi> > pq;
pq.push(make_pair(0, source));
int s = source;
visited[s] = true;
while (!pq.empty()) {
int x = pq.top().second;
// Displaying the path having the lowest cost.
cout << x << " ";
pq.pop();
if (x == target)
break;

for (int i = 0; i < graph[x].size(); i++) {
if (!visited[graph[x][i].second]) {
visited[graph[x][i].second] = true;
pq.push(make_pair(graph[x][i].first,graph[x][i].second));
}
}
}
return 0;
}``````

#### Output:

``0 1 3 2 8 9 11 13 10 12 5 4 6 7 ``

### Implementation in Java

``````import java.util.ArrayList;
import java.util.PriorityQueue;

class CodingNinjas
{
static ArrayList<ArrayList<edge> > adj = new ArrayList<>();
// Function for adding the edges to a graph
static class edge implements Comparable<edge>
{
int v, cost;
edge(int v, int cost)
{
this.v = v;
this.cost = cost;
}
@Override public int compareTo(edge o)
{
if (o.cost < cost) {
return 1;
}
else
return -1;
}
}

public CodingNinjas(int v)
{
for (int i = 0; i < v; i++) {
}
}

//Function to apply Best- First Search
static void best_first_search(int source, int target, int v){
PriorityQueue<edge> pq = new PriorityQueue<>();
boolean visited[] = new boolean[v];
visited = true;
while (!pq.isEmpty()) {
int x = pq.poll().v;
//Displaying the path having the lowest cost.
System.out.print(x + " ");
if (target == x) {
break;
}
}
}
}
}
void addedge(int u, int v, int cost)
{
}

// Driver Code
public static void main(String args[])
{
int v = 14;
CodingNinjas graph = new CodingNinjas(v);

int source = 0;
int target = 9;
best_first_search(source, target, v);
}
}``````

#### Output:

``0 1 3 2 8 9``

## Complexities Analysis

Time Complexity- The worst-case time complexity is O(b^d+1), where b is the branching factor and d is the depth of a tree. In the worst case, we may have to visit all nodes before we reach the goal.

Space  Complexity- The worst-case space complexity is O(b^d), where b is the branching factor and d is the depth of a tree.

Let's see some FAQs related to the Best First Search or Informed Search.

### Best First Search uses which data structure?

Priority Queue is used for the best first search as Priority Queue maintains the fringe in ascending order of f values.

### What is the advantage of the best first search?

Best-first search allows us to take advantage of both algorithms. With the help of the best-first search, we can choose the most promising node at each step.

### Is Informed Search Complete?

It may or may not be complete as Informed Search is also known as Heuristic Search.

### Why is A * better than Best First Search?

A* achieves better performance by using heuristics to guide its search and combines the advantages of Best-first Search and Uniform Cost Search.

### What is Graph?

A graph is a non-linear data structure having a finite number of nodes or vertices and the edges that connect them.

## Conclusion

This article discusses the problem of Best First Search or Informed Search with their examples and implementation. We had also seen some FAQs related to them.

After reading about the above problem, Best First Search or Informed Search, are you not feeling excited to read/explore more articles on Data Structures and Algorithms? Don't worry; Coding Ninjas has you covered. See GraphBinary TreeBFS vs DFSCheck for Balanced Parentheses in an Expression, and Stack to learn.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more!

Happy Learning!

Live masterclass