## 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);
addedge(0, 1, 2);
addedge(0, 2, 5);
addedge(0, 3, 4);
addedge(1, 4, 8);
addedge(1, 5, 7);
addedge(2, 6, 9);
addedge(2, 7, 10);
addedge(3, 8, 6);
addedge(8, 9, 3);
addedge(8, 10, 4);
addedge(9, 11, 1);
addedge(9, 12, 5);
addedge(9, 13, 2);
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++) {
adj.add(new ArrayList<>());
}
}
//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;
pq.add(new edge(source, -1));
while (!pq.isEmpty()) {
int x = pq.poll().v;
//Displaying the path having the lowest cost.
System.out.print(x + " ");
if (target == x) {
break;
}
for (edge adjacentNodeEdge : adj.get(x)) {
if (!visited[adjacentNodeEdge.v]) {
visited[adjacentNodeEdge.v] = true;
pq.add(adjacentNodeEdge);
}
}
}
}
void addedge(int u, int v, int cost)
{
adj.get(u).add(new edge(v, cost));
adj.get(v).add(new edge(u, cost));
}
// Driver Code
public static void main(String args[])
{
int v = 14;
CodingNinjas graph = new CodingNinjas(v);
graph.addedge(0, 1, 2);
graph.addedge(0, 2, 5);
graph.addedge(0, 3, 4);
graph.addedge(1, 4, 8);
graph.addedge(1, 5, 7);
graph.addedge(2, 6, 9);
graph.addedge(2, 7, 10);
graph.addedge(3, 8, 6);
graph.addedge(8, 9, 3);
graph.addedge(8, 10, 4);
graph.addedge(9, 11, 1);
graph.addedge(9, 12, 5);
graph.addedge(9, 13, 2);
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.

## Frequently Asked Questions

**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 __Graph__, __Binary Tree__, __BFS vs DFS__, __Check 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 Algorithms__, __Competitive Programming__, __JavaScript__, __System Design__, and many more!

Happy Learning!