Listen, I've seen this a dozen times in technical interviews and junior PRs: the assumption that a graph is just a "fancy tree." If you go into this thinking a graph is just a tree where a node can have multiple parents, you're going to crash your program. Literally.

Graphs Aren't Just Trees With Extra Steps

In a tree, you have a clear hierarchy and no cycles. If you write a recursive function to traverse a tree, you don't have to worry about ending up where you started. But try that same logic on a graph—say, a social network where Alice follows Bob, Bob follows Charlie, and Charlie follows Alice—and you'll hit a RecursionError: maximum recursion depth exceeded faster than you can say "infinite loop."

# The "Tree-Mindset" Trap
def traverse_graph(node, graph):
    print(node)
    for neighbor in graph[node]:
        traverse_graph(neighbor, graph)

# If our graph is: A -> B -> C -> A
network = {'A': ['B'], 'B': ['C'], 'C': ['A']}
traverse_graph('A', network) # BOOM. Stack overflow.

The fundamental difference is that graphs can have cycles. To survive a graph, you need a memory—specifically, a set to keep track of every node you've already visited. If you've seen it, don't touch it again. It's that simple.

Building the Adjacency List

While there are several ways to represent a graph, I almost always recommend the adjacency list using a Python dictionary. It's intuitive, it gives us O(1) lookup for a node's neighbors, and it doesn't waste space like a massive 2D matrix would if your graph is sparse (which most real-world graphs are).

class Graph:
    def __init__(self):
        self.adj_list = {}

    def add_edge(self, u, v, bidirectional=True):
        if u not in self.adj_list: self.adj_list[u] = []
        if v not in self.adj_list: self.adj_list[v] = []
        
        self.adj_list[u].append(v)
        if bidirectional:
            self.adj_list[v].append(u)

Diving Deep with DFS

Depth-First Search (DFS) is your go-to when you need to explore as far as possible along a branch before backtracking. It's great for checking if a path exists between two nodes or for solving mazes. You can do this recursively, but you must pass that visited set along.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(f"Visiting {start}")
    
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Finding the Shortest Path with BFS

Here is where people usually get confused: DFS cannot reliably find the shortest path in an unweighted graph. If you want the minimum number of hops to get from Point A to Point B, you need Breadth-First Search (BFS). BFS explores in "ripples"—it visits all immediate neighbors first, then all neighbors of neighbors.

To implement this, we ditch recursion and use a collections.deque. Using a standard list as a queue in Python is a performance nightmare because pop(0) is O(n). Deques are O(1).

from collections import deque

def bfs(graph, start, target):
    visited = {start}
    queue = deque([(start, 0)]) # Store (node, distance)

    while queue:
        current_node, distance = queue.popleft()
        
        if current_node == target:
            return distance
            
        for neighbor in graph.get(current_node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))
                
    return -1 # Target unreachable

My rule of thumb? If the problem asks for "shortest," "nearest," or "minimum steps," reach for BFS. If it asks "is it possible" or "find any path," DFS is usually simpler to write.

📋 Practical Task

Exercise: Mapping a Transit Network to Find Minimum Transfers

You are building a simplified subway navigator. You have a set of stations and the tracks that connect them. Your goal is to determine the minimum number of stops (edges) a passenger must take to get from the starting station to the destination station.

Requirements:

• Create a SubwayGraph class that uses an adjacency list.
• Implement a method min_stops(start_station, end_station) using a BFS traversal.
• Ensure your code handles cases where the destination station is unreachable.

Test Case:

# Setup the network
subway = SubwayGraph()
subway.add_edge("Central", "North Park")
subway.add_edge("Central", "South Station")
subway.add_edge("North Park", "Airport")
subway.add_edge("South Station", "Financial District")
subway.add_edge("Financial District", "Airport")
subway.add_edge("West End", "Isolated Island") # Isolated cluster

# Expected results:
print(subway.min_stops("Central", "Airport")) # Should output 2
print(subway.min_stops("Central", "Isolated Island")) # Should output -1