Posted on

# DFS and BFS of a graph

### 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
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)
res.append(vertex)
while q:
currVertex = q.popleft()
for v in graph[currVertex]:
if v not in seen:
res.append(v)
q.append(v)

# main function
q = deque()
res = []
seen = set()
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