Graph Traversal Algorithms in Python: BFS and DFS Implementations Explained

Breadth-First Search (BFS) and Depth-First Search (DFS) in the TheAlgorithms/Python repository use queue-based and stack-based approaches respectively, with BFS excelling at shortest-path discovery in unweighted graphs and DFS optimized for deep exploration and cycle detection.

The TheAlgorithms/Python repository provides clean, self-contained implementations of fundamental graph traversal algorithms that illustrate core computer science concepts while remaining easy to read and test. These implementations demonstrate production-ready Python code for exploring graph structures without encountering recursion limits or performance bottlenecks. Understanding these graph traversal algorithms is essential for solving connectivity problems, pathfinding challenges, and dependency resolution tasks in real-world applications.

BFS Implementation: Queue-Based Level-Order Traversal

The Breadth-First Search implementation resides in graphs/breadth_first_search.py and provides a complete Graph class wrapper around the traversal logic.

Source Code Architecture

In graphs/breadth_first_search.py, the Graph class maintains an adjacency list via self.vertices: dict[int, list[int]]. Vertices are added using the add_edge method, which builds the graph structure before traversal begins.

The bfs(start_vertex) method performs the actual traversal using a FIFO queue from Python's standard queue module. The algorithm initializes a visited: set[int] to track processed vertices and prevent infinite loops in cyclic graphs. Starting from start_vertex, the method enqueues the initial node, then iteratively dequeues vertices, marks them as visited, and enqueues their unvisited neighbors until the queue empties.

This implementation returns a set[int] containing all vertex IDs reachable from the starting position, guaranteeing each vertex is processed exactly once.

Why Use BFS?

BFS is the optimal choice for shortest-path discovery in unweighted graphs because it explores vertices by increasing distance from the source. The algorithm naturally supports level-order processing, making it ideal for finding all nodes within k hops of a starting point or modeling spreading phenomena across network layers.

DFS Implementation: Stack-Based Deep Exploration

The Depth-First Search implementation in graphs/depth_first_search.py takes a different approach, using an explicit stack to avoid Python's recursion depth limitations.

Source Code Architecture

The depth_first_search(graph, start) function receives a plain adjacency-list dictionary and implements a non-recursive traversal using a LIFO stack. The function maintains an explored: set[str] collection to track visited vertices and a stack: list that mimics recursive call behavior.

The algorithm pushes the start vertex onto the stack, then enters a loop where it pops the last element (depth-first behavior), marks it as explored, and pushes its unvisited neighbors onto the stack. For deterministic traversal order, the implementation reverses the neighbor list before pushing to the stack.

This stack-based approach avoids Python's recursion-depth limits, making it safe for processing large or deeply nested graphs that would crash a recursive implementation.

Why Use DFS?

DFS excels at topological sorting, cycle detection, and finding connected components in directed and undirected graphs. The algorithm naturally fits problems requiring exhaustive search with backtracking, such as solving puzzles, maze navigation, or enumerating all possible paths between nodes. Because DFS explores as far as possible along each branch before backtracking, it minimizes memory usage by storing only the current path rather than the entire frontier.

Practical Code Examples

Below are runnable implementations using the TheAlgorithms/Python source files.

Running BFS

from graphs.breadth_first_search import Graph

g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

visited = g.bfs(start_vertex=2)
print("BFS visited:", sorted(visited))   # → [0, 1, 2, 3]

Running DFS

from graphs.depth_first_search import depth_first_search

graph = {
    "A": ["B", "C", "D"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B", "D"],
    "E": ["B", "F"],
    "F": ["C", "E", "G"],
    "G": ["F"]
}

visited = depth_first_search(graph, start="A")
print("DFS visited:", visited)   # → {'A', 'B', 'C', 'D', 'E', 'F', 'G'}

BFS vs DFS: Selecting the Right Algorithm

Choose the appropriate graph traversal algorithm based on your specific computational requirements:

• Shortest path in unweighted graphs: Use BFS because it visits nodes in order of distance from the source, guaranteeing the first path found is the shortest.
• Cycle detection in directed graphs: Use DFS (with explicit stack tracking) to identify back-edges that indicate cycles.
• Topological ordering of DAGs: Use DFS with post-order traversal; reversing the finish times yields a valid topological sort.
• Finding nodes within k hops: Use BFS and limit traversal to k levels, leveraging its level-order expansion.
• Puzzle solving and backtracking: Use DFS to explore deep solution branches before trying alternatives, minimizing memory overhead.

Summary

• graphs/breadth_first_search.py implements BFS using a Graph class with bfs(start_vertex) method, utilizing queue.Queue for FIFO processing and set[int] for visited tracking.
• graphs/depth_first_search.py provides a non-recursive depth_first_search(graph, start) function using a Python list as a LIFO stack, avoiding recursion limits while handling adjacency-list dictionaries.
• BFS finds shortest paths in unweighted graphs and processes nodes by levels, making it ideal for proximity searches.
• DFS supports topological sorting, cycle detection, and deep exploration with minimal memory footprint, suitable for exhaustive search problems.
• Both implementations include doctests and require only Python's standard library.

Frequently Asked Questions

What is the main difference between BFS and DFS implementation in the TheAlgorithms/Python repository?

BFS uses a Graph class with an explicit queue.Queue to process vertices in FIFO order, while DFS uses a standalone function with a Python list as a LIFO stack. The BFS implementation in graphs/breadth_first_search.py tracks visited nodes using integer sets, whereas the DFS implementation in graphs/depth_first_search.py handles string keys and reverses neighbor lists for deterministic traversal order.

Why does the DFS implementation use an explicit stack instead of recursion?

The depth_first_search function avoids Python's recursion-depth limit by using a list as an explicit stack, making it safe for large graphs or deep traversal paths that would trigger a RecursionError in recursive implementations. This approach also provides better memory predictability and allows manual control over the traversal order by reversing neighbor lists before pushing to the stack.

When should I use BFS over DFS for graph traversal problems?

Use BFS when you need the shortest path in an unweighted graph or must process nodes by their distance from a source (level-order traversal). BFS is also preferred for finding all nodes within k hops or when the solution is likely to be close to the starting vertex. Use DFS for cycle detection, topological sorting, or when you need to explore complete paths before backtracking, such as in puzzle solvers or maze generators.

How do these implementations handle cycles and prevent infinite loops?

Both implementations use set-based tracking to prevent revisiting nodes. The BFS bfs() method maintains a visited: set[int] that checks membership before enqueuing neighbors, while the DFS depth_first_search() function uses an explored: set[str] to skip already-processed vertices before pushing them onto the stack. This ensures each vertex is processed exactly once even in cyclic graph structures.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}