Depth-First Search (DFS) and Breadth-First Search (BFS) are two fundamental graph traversal algorithms used in computer science. They help in exploring all the vertices and edges of a graph systematically.

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack data structure to keep track of the nodes to be visited.

Key Points of DFS:

  • Visits nodes in a depth-first manner.
  • Uses a stack to store the nodes.
  • Can be used to find connected components, detect cycles, and perform topological sorting.

Example:

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

Breadth-First Search (BFS)

BFS explores all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at the same level before moving to the next level.

Key Points of BFS:

  • Visits nodes in a breadth-first manner.
  • Uses a queue data structure to store the nodes.
  • Can be used to find the shortest path between two nodes in an unweighted graph.

Example:

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(graph[vertex] - visited)
    return visited

Differences between DFS and BFS

  • Traversal Order: DFS visits nodes in a depth-first manner, while BFS visits nodes in a breadth-first manner.
  • Data Structure: DFS uses a stack, while BFS uses a queue.
  • Use Cases: DFS is useful for finding connected components, detecting cycles, and performing topological sorting, whereas BFS is useful for finding the shortest path between two nodes in an unweighted graph.

For more information on graph traversal algorithms, you can visit our Graph Traversal Algorithms tutorial.