How do BFS and DFS work in graph traversal?

Can you explain how BFS and DFS work in graph traversal?

Sure! BFS (Breadth-First Search) explores all neighbors at the present depth prior to moving on to nodes at the next depth level. DFS (Depth-First Search), on the other hand, explores as far as possible along each branch before backtracking.

How can I visualize these algorithms?

You can visualize BFS and DFS using graphs. For BFS, you can use a queue to keep track of nodes to explore, while for DFS, a stack is used. There are many online tools and libraries that can help you create these visualizations.

Are there any specific use cases for BFS and DFS?

Yes! BFS is often used in finding the shortest path in unweighted graphs, while DFS is useful for topological sorting and solving puzzles like mazes.

Can you show me a code example for both algorithms?

Absolutely! Here’s a simple Python example for BFS:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)
    return visited

And for DFS:

def dfs(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited