*BFS :*

It stands for

**Breadth First Search**.It is a traversal algorithm which uses

**level order traversal**which means all nodes of the same level are traversed first before moving on to the next level nodes.It uses

**Queue**for it's implementation(First In First Out/FIFO) instead of Stack to find the shortest path.BFS covers all of it's

**neighbors**while traversing.It is widely preferred in programming over DFS as it is

**better**than using recursion in some cases.It is optimal as it covers

**shallowest**nodes first and chances of missing the shortest path are less.It’s precisely the space complexity that makes BFS

**impractical**even though it’s complete and optimal in the cases where DFS isn’t.It can require a lot of space and will prove to be

**inefficient**if the branching factor is too large or the goal is deep.

```
Example:
1 //levels
/ \
2 4
/ / \
3 5 6
Output : 1 2 4 3 5 6 as it follows Level Order Traversing
1 -> 1
--------------
/ \
2 -> 2 4
---------------
/ / \
3 -> 3 5 6
```

*DFS :*

It stands for

**Depth First Search.**It is a traversal algorithm which uses

**stack**data structure which works on the**LIFO**(Last In First Out) principle.In DFS, all nodes are traversed in a

**depth-ward manner**and then**backtracking**is performed to get back to the root.It uses

**Stack**for it's implementation instead of Queue to find the shortest path.DFS is better when target is

**far**from sourceIt reaches

**deep nodes faster**than BFS.It uses

**recursion**to get to the end with base conditions.DFS isn’t an optimal algorithm.

It's time complexity is high as compared to DFS.

DFS discovers a

**longer path**first to reach to the goal.BFS is impractical because of the high order of its space complexity. That is why DFS is

**used more often**.

```
Example:
1 //depth
/ \
2 4
/ / \
3 5 6
Output : 1 2 3 4 5 6
.
1 -> 1.
/. \ .
2 -> 2 . 4.
/ . /. \ .
3 -> 3 . 5. 6.
. . .
```

You should know recursion, stack ,queue, priority queue, 0 and 1 based indexing before moving on to solve BFS and DFS questions.

## Commenti