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
  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