# Graph Traversal Algorithms in Python: BFS and DFS Implementations Explained

> Explore Python BFS and DFS graph traversal algorithms. Learn how queue and stack implementations solve shortest paths and detect cycles. Ideal for unweighted graphs and deep exploration.

- Repository: [The Algorithms/Python](https://github.com/TheAlgorithms/Python)
- Tags: tutorial
- Published: 2026-02-24

---

**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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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

```python
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

```python
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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/graphs/breadth_first_search.py) tracks visited nodes using integer sets, whereas the DFS implementation in [`graphs/depth_first_search.py`](https://github.com/TheAlgorithms/Python/blob/main/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.