Graph Algorithms in Python: BFS, DFS, Dijkstra

Graphs are versatile non-linear data structures used to model networks such as social connections, routing tables, dependency graphs, and recommendation engines. Mastering core graph traversal and shortest-path algorithms is a fundamental requirement for technical interviews and high-performance backend systems.

This comprehensive guide explores implementing adjacency list representations, Breadth-First Search (**BFS**), Depth-First Search (**DFS**), and **Dijkstra's shortest path algorithm** in clean, idiomatic Python.

1. Graph Representation: Adjacency List

Before implementing traversal algorithms, we must represent the graph in memory. An **adjacency list** (implemented using Python dictionaries) is the most efficient and standard way to represent sparse graphs.

              
            
C

            
            # Representing a directed, weighted graph as an adjacency list
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 5), ('E', 1)],
    'C': [('A', 2), ('F', 3)],
    'D': [('B', 5)],
    'E': [('B', 1), ('F', 2)],
    'C': [('C', 3), ('E', 2)]
};
          

2. Breadth-First Search (BFS)

**Breadth-First Search (BFS)** explores a graph level by level, visiting all neighbors of a node before moving to the next level. It utilizes a **Queue** (First-In, First-Out) data structure and guarantees the shortest path in unweighted graphs.

Time Complexity: $O(V + E)$ where $V$ is vertices and $E$ is edges.
Space Complexity: $O(V)$ to store the queue and visited set.
Primary Use Cases: Finding the shortest path in unweighted networks, level-order tree traversals, and web crawlers.

              
            
C

            
            from collections import deque

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)
    traversal_order = []

    while queue:
        current = queue.popleft()
        traversal_order.append(current)

        for neighbor, _ in graph.get(current, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return traversal_order;
          

3. Depth-First Search (DFS)

**Depth-First Search (DFS)** explores as deep as possible along each branch before backtracking. It can be implemented recursively using the call stack or iteratively using an explicit **Stack** (Last-In, First-Out).

Time Complexity: $O(V + E)$.
Space Complexity: $O(V)$ for recursion stack depth and visited tracking.
Primary Use Cases: Detecting cycles, topological sorting, solving mazes, and finding connected components.

              
            
C

            
            def dfs_recursive(graph, current, visited=None, traversal_order=None):
    if visited is None:
        visited = set()
    if traversal_order is None:
        traversal_order = []

    visited.add(current)
    traversal_order.append(current)

    for neighbor, _ in graph.get(current, []):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, traversal_order)

    return traversal_order;
          

4. Dijkstra's Shortest Path Algorithm

**Dijkstra's algorithm** finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. It greedily selects the unvisited node with the smallest tentative distance using a Min-Heap (`heapq`).

Time Complexity: $O((V + E) \log V)$ when implemented with a priority queue.
Space Complexity: $O(V + E)$ for distance maps and heap storage.
Constraint: Fails or produces incorrect results if negative edge weights are present (requires Bellman-Ford instead).

              
            
C

            
            import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    # Priority queue stores tuples of (current_distance, node)
    pq = [(0, start)]

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph.get(current_node, []):
            distance = current_distance + weight

            # Found a shorter path to neighbor
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances;
          

Conclusion

Proficiency in graph algorithms—such as queue-based **BFS**, recursive/stack-based **DFS**, and heap-optimized **Dijkstra's algorithm**—empowers software engineers to architect robust routing systems, recommendation engines, and complex network analyzers in Python.