Graphs

Graph Traversal

● Intermediate ⏱ 11 min read graphs

Graph traversal visits every reachable vertex exactly once. The two fundamental algorithms are Breadth-First Search (BFS), which explores level by level using a queue, and Depth-First Search (DFS), which dives deep before backtracking using a stack (or recursion).

Breadth-First Search (BFS)

BFS visits all vertices at distance 1 before any at distance 2. This guarantees the shortest path (fewest hops) in an unweighted graph.

Python

from collections import deque, defaultdict

graph = defaultdict(list)
for u, v in [("A","B"),("A","C"),("B","D"),("B","E"),("C","F")]:
    graph[u].append(v)
    graph[v].append(u)

def bfs(graph, start):
    visited = {start}
    queue   = deque([start])
    order   = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    return order

print(bfs(graph, "A"))   # ['A', 'B', 'C', 'D', 'E', 'F']

# BFS shortest path
def bfs_shortest_path(graph, start, end):
    if start == end:
        return [start]
    visited  = {start}
    queue    = deque([[start]])
    while queue:
        path = queue.popleft()
        node = path[-1]
        for nb in graph[node]:
            if nb == end:
                return path + [nb]
            if nb not in visited:
                visited.add(nb)
                queue.append(path + [nb])
    return None

print(bfs_shortest_path(graph, "A", "F"))  # ['A', 'C', 'F']

DFS — Recursive

Python

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=" ")
    for nb in graph[node]:
        if nb not in visited:
            dfs_recursive(graph, nb, visited)

dfs_recursive(graph, "A")   # A B D E C F  (order depends on adjacency list)

DFS — Iterative

The iterative version avoids Python’s recursion depth limit, which matters on graphs with thousands of nodes.

Python

def dfs_iterative(graph, start):
    visited = set()
    stack   = [start]
    order   = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for nb in reversed(graph[node]):   # reversed to match recursive order
            if nb not in visited:
                stack.append(nb)
    return order

print(dfs_iterative(graph, "A"))   # ['A', 'B', 'D', 'E', 'C', 'F']

Cycle Detection

Python

# Undirected graph: cycle exists if DFS revisits a non-parent node
def has_cycle_undirected(graph, vertices):
    visited = set()

    def dfs(node, parent):
        visited.add(node)
        for nb in graph[node]:
            if nb not in visited:
                if dfs(nb, node):
                    return True
            elif nb != parent:
                return True           # back-edge → cycle
        return False

    for v in vertices:
        if v not in visited:
            if dfs(v, None):
                return True
    return False

# Directed graph: cycle detected via DFS with a "recursion stack"
def has_cycle_directed(graph, vertices):
    visited  = set()
    rec_stack = set()

    def dfs(node):
        visited.add(node)
        rec_stack.add(node)
        for nb in graph[node]:
            if nb not in visited:
                if dfs(nb):
                    return True
            elif nb in rec_stack:     # back-edge in directed graph
                return True
        rec_stack.discard(node)
        return False

    for v in vertices:
        if v not in visited:
            if dfs(v):
                return True
    return False

Topological Sort (Kahn’s Algorithm)

Topological sort orders vertices of a DAG so that every edge u→v has u before v. Used for build systems, task scheduling, and dependency resolution.

Python

from collections import deque

def topological_sort(graph, vertices):
    in_degree = {v: 0 for v in vertices}
    for u in vertices:
        for v in graph[u]:
            in_degree[v] += 1

    queue = deque([v for v in vertices if in_degree[v] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nb in graph[node]:
            in_degree[nb] -= 1
            if in_degree[nb] == 0:
                queue.append(nb)

    if len(order) != len(vertices):
        raise ValueError("Graph has a cycle — no topological order exists")
    return order

# Example: course prerequisites
dag = defaultdict(list)
dag["A"].append("C")   # A must come before C
dag["B"].append("C")
dag["B"].append("D")
dag["C"].append("E")
dag["D"].append("F")
dag["E"].append("F")

print(topological_sort(dag, ["A","B","C","D","E","F"]))
# ['A', 'B', 'C', 'D', 'E', 'F']  (or another valid ordering)

BFS vs DFS

Property	BFS	DFS
Data structure	Queue	Stack / recursion
Shortest path (unweighted)	Yes	No
Memory (wide graph)	O(w) — can be large	O(h) — usually smaller
Memory (deep graph)	O(w) — small	O(h) — can hit recursion limit
Topological sort	Kahn’s (BFS-based)	DFS-based (post-order)
Cycle detection	Yes	Yes

Complexity Table

Algorithm	Time	Space	Note
BFS	O(V+E)	O(V)	Queue + visited set
DFS	O(V+E)	O(V)	Call stack depth = O(V)
Topological sort	O(V+E)	O(V)	Kahn’s algorithm
Cycle detection	O(V+E)	O(V)	DFS with recursion stack