Data Structures & Algorithms•28 min read•Advanced

Graphs: BFS, DFS, Topological Sort

The most universal data structure in CS. Friend networks, road maps, dependency graphs — all the same algorithms.

What is a graph?

A graph is a set of nodes (vertices) connected by edges. Edges can be directed (one-way streets, Twitter follows) or undirected (roads, Facebook friendships). They can also be weighted, meaning each edge carries a number — distance, cost, time.

Every problem you can think of involving relationships, networks, dependencies, or paths can be modeled as a graph. Once you've mastered the few core graph algorithms, you can solve a huge family of seemingly unrelated problems.

Representations

Adjacency list — for each node, store a list of its neighbors. Memory: O(V + E). Best for most problems.
Adjacency matrix — V×V boolean grid, m[i][j] = 1 if edge from i to j. O(V²) memory. Good when the graph is dense or you need O(1) edge queries.
Edge list — just a list of (u, v) pairs. Used by some algorithms (Kruskal's MST).

python

Try in Playground →

# Adjacency list as a dict of lists
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}

🌊

Real-life analogy — BFS = ripples; DFS = a maze runner

BFS spreads outward like ripples on a pond — everything 1 step away first, then 2 steps, then 3. DFS is a maze runner with a ball of string — it dives down one corridor as far as it can, hits a dead end, backtracks, and tries the next corridor.

Graph traversal: BFS vs DFS

Same graph, two strategies. BFS uses a queue and explores level by level. DFS uses a stack and goes deep first.

Queue (front → back)

Visited

Start: enqueue A

Breadth-first search (BFS)

BFS explores neighbors layer by layer: all nodes at distance 1, then all at distance 2, then 3, etc. Use a QUEUE. On an unweighted graph, BFS finds the shortest path — guaranteed.

python

Try in Playground →

from collections import deque

def shortest_path(graph, start, goal):
    if start == goal:
        return 0
    seen = {start}
    q = deque([(start, 0)])
    while q:
        node, dist = q.popleft()
        for nxt in graph[node]:
            if nxt == goal:
                return dist + 1
            if nxt not in seen:
                seen.add(nxt)
                q.append((nxt, dist + 1))
    return -1

print(shortest_path(graph, "A", "E"))   # 3

Depth-first search (DFS)

DFS goes as deep as possible before backtracking. Use a STACK (or recursion, which uses the call stack implicitly). DFS finds connected components, detects cycles, and is the basis for many algorithms (topological sort, finding bridges and articulation points).

python

Try in Playground →

def dfs(graph, start):
    seen = set()
    order = []
    def visit(node):
        if node in seen: return
        seen.add(node)
        order.append(node)
        for nxt in graph[node]:
            visit(nxt)
    visit(start)
    return order

Topological sort

On a directed acyclic graph (DAG), a topological sort is an ordering where every edge goes from earlier to later. Use cases: build systems (compile dependencies in order), course prerequisites, task scheduling. The classic algorithm uses BFS on in-degrees (Kahn's algorithm).

python

Try in Playground →

from collections import deque, defaultdict

def topo_sort(num_nodes, edges):
    graph = defaultdict(list)
    in_deg = [0] * num_nodes
    for u, v in edges:
        graph[u].append(v)
        in_deg[v] += 1

    q = deque(i for i, d in enumerate(in_deg) if d == 0)
    out = []
    while q:
        node = q.popleft()
        out.append(node)
        for nxt in graph[node]:
            in_deg[nxt] -= 1
            if in_deg[nxt] == 0:
                q.append(nxt)

    return out if len(out) == num_nodes else None    # None = cycle

💡 Tip

If a graph problem involves WEIGHTED edges and shortest paths, BFS isn\u2019t enough. You need Dijkstra\u2019s algorithm (priority queue) — covered in the advanced structures lesson.

← Previous

Trees & Binary Search Trees

Dynamic Programming