DEV Community

Karhik Suryadevara
Karhik Suryadevara

Posted on

3 2

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
image
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
Enter fullscreen mode Exit fullscreen mode

 

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
image
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
Enter fullscreen mode Exit fullscreen mode

 
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

Image of Datadog

The Essential Toolkit for Front-end Developers

Take a user-centric approach to front-end monitoring that evolves alongside increasingly complex frameworks and single-page applications.

Get The Kit

Top comments (0)

Image of Docusign

πŸ› οΈ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more