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)