### What is DFS(depth first search)?

It's an algorithm to traverse a graph in a depth first manner, i.e. going deep into one branch before backtracking and continuing the process until all vertices are visited.

**Example**

Pick vertex **0** traverse **1, 2** and then backtrack to **1** and traverse **2, 3, 4** and then backtrack to traverse **4**. So the final result would be **[0, 1, 2, 3, 4]**

**Note:** **[0, 4, 3, 2, 1]** is also correct.

To implement the algorithm, we need a **set** to keep track of visited nodes and an **array** to store the result

**Algorithm**

1) pick any vertex

2) if the vertex is not in the set, go to step 3

3) add the vertex to the set and the result array, and repeat the process for each vertex of the current vertex.

**Code**

```
def depth_first_search(graph, currVertex, seen, result):
if currVertex in seen: return
seen.add(currVertex)
result.append(currVertex)
for vertex in graph[currVertex]:
depth_first_search(graph, vertex, seen, result)
# main function
def dfs(v, graph):
result = []
seen = set()
depth_first_search(graph, 0, seen, result)
return result
```

### What is BFS(breadth first search)?

It's an algorithm to traverse a graph in breadth first manner, i.e. traversing all the vertices of a vertex and then moving to another vertex and repeat the process until all the vertices are visited.

**Example**

Pick vertex **0** traverse its vertices **1, 4** and then take vertex **1** and traverse its vertices **2, 3, 4**. So the final result would be **[0, 1, 4, 2, 3]**

**Note:** **[0, 4, 1, 3, 2]** is also correct.

we need a queue, set and an array to implement the algorithm

**Algorithm**

1) pick a vertex

2) add the vertex to the queue

3) while queue is not empty, pop the queue and traverse the vertices of popped vertex and do step 2 for each vertex of the vertices, if the vertex is not in the set

**Code**

```
from collections import deque
def bfs(graph, seen, q, vertex, res):
q.append(vertex)
seen.add(vertex)
res.append(vertex)
while q:
currVertex = q.popleft()
for v in graph[currVertex]:
if v not in seen:
seen.add(v)
res.append(v)
q.append(v)
# main function
def bfsOfGraph(v, adj):
q = deque()
res = []
seen = set()
bfs(adj, seen, q, 0, res)
return res
```

**Uses of BFS and DFS**

1) Using DFS we can find the path between vertex u, v and also check if the graph is strongly connected.

2) BFS can be used to find neighbors of a vertex

**Problems on BFS and DFS**

1) Implement DFS: geeks-for-geeks-link

2) Implement BFS: geeks-for-geeks-link

## Top comments (0)