Cấu trúc dữ liệu đồ thịGraph Data Structures

Part of the Data Structures & Algorithms Roadmap knowledge base.

Overview

A graph is a set of vertices (nodes) together with a set of edges, where each edge connects a pair of vertices. That definition is almost insultingly simple, and that is exactly why graphs matter: almost every relationship you can name is a graph. Cities and roads. Web pages and hyperlinks. People and friendships. Packages and their dependencies. Tasks and their prerequisites. Bank accounts and transfers. Pixels and their neighbours. Git commits and their parents. Once you can see the graph inside a problem, a large catalogue of standard algorithms becomes available to you.

Graphs are also the most general of the structures in this roadmap. A linked list is a graph where every vertex has out-degree at most one. A tree is a connected acyclic undirected graph. A heap is a tree with an ordering constraint. Everything you have learned so far is a special case of what follows, which is why graph algorithms need no new primitives — a queue gives you BFS, a stack gives you DFS, and a priority queue gives you Dijkstra.

The two things worth being deliberate about are how you store the graph and how you walk it. Choosing an adjacency matrix for a social network with ten million users is a hundred-terabyte mistake; choosing an adjacency list when your inner loop is “is there an edge between u and v?” turns a constant-time check into a linear scan. And nearly every graph algorithm in this note and the next two is BFS or DFS with something extra bolted on. Get the traversals right and the rest follows.

This note covers terminology, the three standard representations and their trade-offs, BFS and DFS in both iterative and recursive form, and the standard applications: connected components, cycle detection, topological sort, bipartite checking, and grid traversal. Weighted shortest paths are in ./14-shortest-path-algorithms.md; minimum spanning trees in ./15-minimum-spanning-trees.md.

Fundamentals

Terminology

Formally a graph is G = (V, E) where V is the vertex set and E ⊆ V × V is the edge set. Throughout this note V means |V|, the number of vertices, and E means |E|, the number of edges — the standard abuse of notation in complexity statements like O(V + E).

• Adjacent / neighbour — u and v are adjacent if the edge (u, v) exists. The neighbours of u are all vertices adjacent to it.
• Incident — an edge is incident to the two vertices it connects.
• Degree — the number of edges incident to a vertex. In a directed graph this splits into in-degree (edges pointing at it) and out-degree (edges leaving it).
• Path — a sequence of vertices where consecutive vertices are connected by an edge. A simple path repeats no vertex.
• Cycle — a path that starts and ends at the same vertex, with at least one edge and no repeated edge.
• Connected — an undirected graph is connected if there is a path between every pair of vertices. A maximal connected piece is a connected component.
• Strongly connected — a directed graph in which every vertex can reach every other vertex. Weakly connected means connected when you ignore edge direction.
• Acyclic — contains no cycle. A directed acyclic graph is a DAG, the single most important special case in practice (build systems, task schedulers, spreadsheet formulas, Git history).
• Self-loop — an edge from a vertex to itself. Parallel edges (a multigraph) are two edges between the same pair. Most algorithms assume neither; be explicit when your input has them.
• Subgraph — a graph formed from a subset of the vertices and edges. A spanning subgraph uses every vertex.

The handshake lemma is worth internalizing because it makes complexity bounds obvious: in an undirected graph, Σ deg(v) = 2E, because every edge contributes one to the degree of each endpoint. This is why “visit every vertex, and for each vertex iterate its neighbours” costs O(V + E) and not O(V · E) — the inner loops sum to 2E in total, not E each.

Directed vs undirected

In an undirected graph the edge {u, v} is symmetric: if you can walk from u to v, you can walk back. Friendship, physical wires, “shares a border with.”

In a directed graph (digraph) each edge (u, v) has a tail u and a head v and points one way only. One-way streets, Twitter follows, “depends on,” “is a parent commit of.”

   Undirected                     Directed
   0 --- 1                        0 ---> 1
   |    /|                        ^     /|
   |   / |                        |    / |
   |  /  |                        |   v  v
   2 --- 3                        2 <--- 3

The distinction is not cosmetic — several algorithms differ fundamentally:

Storing an undirected graph means storing each edge twice in the adjacency list — once in adj[u] and once in adj[v]. Forgetting the second insertion is the single most common graph bug, and it produces a graph that looks fine until a traversal mysteriously fails to reach half the vertices.

Weighted vs unweighted

In a weighted graph each edge carries a number: distance, cost, latency, capacity, probability. In an unweighted graph edges are all equal, which is the same as all weights being 1.

This distinction decides which shortest-path algorithm you need. On an unweighted graph, BFS gives you shortest paths in O(V + E), and reaching for Dijkstra would be a waste. On a weighted graph BFS is simply wrong — the fewest-edges path is not the lowest-weight path:

        1
   A ------- B
    \        |
     \ 10    | 1
      \      |
       ------ C

BFS from A says dist(A→C) = 1 edge (the weight-10 edge).
The cheapest route is A→B→C with total weight 2.

Weights can be negative (a refund, an energy gain, a currency arbitrage), which breaks Dijkstra’s greedy argument entirely — see ./14-shortest-path-algorithms.md.

Dense vs sparse

A simple undirected graph on V vertices has at most V(V−1)/2 edges; a directed one at most V(V−1). Define density as E relative to that maximum.

• Sparse — E = O(V) or thereabouts. Road networks (each intersection has ~4 roads), social graphs (bounded friend counts), dependency graphs, most real-world graphs.
• Dense — E = Θ(V²). Complete graphs, distance matrices between all pairs of cities, correlation graphs, small graphs where everything touches everything.

Density is the deciding input to almost every representation and algorithm choice in this note. O(V²) and O(E) are the same order on a dense graph and wildly different on a sparse one: for V = 10⁶ and E = 5 × 10⁶ (a plausible road network), V² is 10¹² — a million times more work.

The three representations

Take this small undirected graph:

   0 --- 1
   |   / |
   |  /  |
   2     3

Adjacency list — for each vertex, the list of its neighbours. This is the default; use it unless you have a specific reason not to.

adj[0] = [1, 2]
adj[1] = [0, 2, 3]
adj[2] = [0, 1]
adj[3] = [1]

Adjacency matrix — a V × V grid where m[u][v] is 1 (or the weight) if the edge exists.

      0  1  2  3
   0 [ 0  1  1  0 ]
   1 [ 1  0  1  1 ]
   2 [ 1  1  0  0 ]
   3 [ 0  1  0  0 ]

Edge list — just the edges, in no particular order. Compact, useless for “who are u’s neighbours”, and exactly the input format that Kruskal’s algorithm and Bellman-Ford want.

[(0, 1), (0, 2), (1, 2), (1, 3)]

class AdjListGraph:
    """The default representation: adj[u] is the list of u's neighbours."""

    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self.adj = [[] for _ in range(n)]

    def add_edge(self, u, v):
        self.adj[u].append(v)
        if not self.directed:
            self.adj[v].append(u)      # undirected = store the edge from both ends

    def neighbours(self, u):
        return self.adj[u]             # O(1) to get the list, O(deg(u)) to walk it

    def has_edge(self, u, v):
        return v in self.adj[u]        # O(deg(u)) — the weak spot of this layout


class AdjMatrixGraph:
    """V x V grid. O(1) edge lookup, O(V^2) space regardless of how few edges exist."""

    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self.m = [[0] * n for _ in range(n)]

    def add_edge(self, u, v, w=1):
        self.m[u][v] = w
        if not self.directed:
            self.m[v][u] = w

    def neighbours(self, u):
        return [v for v in range(self.n) if self.m[u][v]]   # O(V) even if u has 2 edges

    def has_edge(self, u, v):
        return self.m[u][v] != 0       # O(1) — the reason this layout exists

For weighted graphs the adjacency list stores pairs instead of bare vertex ids: adj[u] = [(v, w), ...]. That is the shape assumed throughout ./14-shortest-path-algorithms.md.

Representation comparison

Reading the table as advice:

• Use an adjacency list by default. Real graphs are sparse, traversals dominate, and O(V + E) beats O(V²).
• Use an adjacency matrix when the graph is dense, V is small (say ≤ 2000), or has_edge is the hot operation. Floyd-Warshall wants a matrix. So does any algorithm phrased as matrix arithmetic (counting paths of length k via matrix powers, PageRank as a linear operator).
• Use an edge list when the algorithm consumes edges globally rather than per-vertex. Kruskal sorts all edges; Bellman-Ford relaxes all edges V−1 times. Neither ever asks “who are u’s neighbours.”

A concrete sizing example: V = 100,000, E = 300,000 (a modest road network). An adjacency list of Python ints costs on the order of a few million machine words. An adjacency matrix would need 10¹⁰ cells — 10 GB even at one byte each, of which 99.997% are zero. The matrix is not a slower choice here; it is an impossible one.

If you want a hash-map adjacency list keyed by arbitrary labels rather than integers 0..n−1, collections.defaultdict(list) is what you would actually write in production. It costs a hash per lookup instead of an array index — still O(1) expected, with a constant factor of maybe 3-5x. For competitive programming or hot loops, relabel vertices to integers first.

Key Concepts

Breadth-first search

BFS explores the graph in layers: first the source, then everything one edge away, then everything two edges away, and so on. It uses a queue — first in, first out — which is exactly what produces the layering.

Source 0, layers of an undirected graph:

   layer 0:      0
                / \
   layer 1:    1   2
              /   / \
   layer 2:  3   4   5

from collections import deque


def bfs(adj, source):
    """Breadth-first search from `source`.

    Returns (dist, parent) where dist[v] is the number of EDGES on a shortest
    path source -> v (-1 if unreachable), and parent[v] is v's predecessor on
    that path. Time O(V + E), space O(V).
    """
    n = len(adj)
    dist = [-1] * n
    parent = [-1] * n

    dist[source] = 0
    q = deque([source])

    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:            # not discovered yet
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)              # mark on ENQUEUE, never on dequeue

    return dist, parent


def reconstruct_path(parent, source, target):
    """Walk the parent pointers backwards, then reverse. O(path length)."""
    if target != source and parent[target] == -1:
        return []                        # unreachable
    path = []
    cur = target
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    path.reverse()
    return path

Two details that are the difference between a correct BFS and a quadratic one:

1. Mark vertices as discovered when you push them, not when you pop them. If you mark on pop, a vertex reachable from three neighbours enters the queue three times. On a dense graph this degrades badly and the “distance” you record is no longer guaranteed minimal on the first visit.
2. Use a real deque. collections.deque gives O(1) popleft. A Python list with pop(0) is O(n) per call because it shifts every remaining element — that alone turns an O(V + E) BFS into O(V² + E).

Complexity: O(V + E) time, O(V) space. Each vertex is enqueued at most once (V pushes and pops), and for each dequeued vertex we scan its adjacency list once; by the handshake lemma those scans total 2E on an undirected graph and E on a directed one. Space is the dist/parent arrays plus the queue, which holds at most one full layer — on a wide graph (a grid, a complete bipartite graph) that layer can be Θ(V).

What BFS is for: shortest paths in unweighted graphs (its headline property), level-order traversal of a tree, finding the minimum number of moves in a puzzle, web crawling by link depth, and computing eccentricity/diameter by running it from every vertex.

Depth-first search

DFS goes as deep as it can along one branch, then backtracks and tries the next. It uses a stack — last in, first out — which is either explicit or, in the recursive form, the call stack itself.

import sys


def dfs_recursive(adj, source):
    """The natural formulation. Time O(V + E), space O(V) for `visited` plus
    O(depth) for the call stack — which is the catch, see below."""
    visited = [False] * len(adj)
    order = []

    def visit(u):
        visited[u] = True
        order.append(u)                  # pre-order: record on entry
        for v in adj[u]:
            if not visited[v]:
                visit(v)
        # post-order work would go here, after all descendants are done

    visit(source)
    return order


def dfs_iterative(adj, source):
    """Same traversal with an explicit stack — no recursion-depth limit."""
    visited = [False] * len(adj)
    order = []
    stack = [source]

    while stack:
        u = stack.pop()
        if visited[u]:                   # here we must check on POP, not on push,
            continue                     # because a vertex can sit on the stack twice
        visited[u] = True
        order.append(u)
        for v in reversed(adj[u]):       # reversed() to match the recursive visit order
            if not visited[v]:
                stack.append(v)

    return order

The recursive and iterative versions visit the same vertices in O(V + E) but the iterative one differs in one respect: a vertex may be pushed several times before it is first popped, so the stack can hold O(E) entries rather than O(V). That is usually fine, and the trade is worth it because Python’s default recursion limit is 1000. A DFS on a path graph of 100,000 vertices will raise RecursionError long before it finishes. You have two outs: sys.setrecursionlimit(300000) (which risks a hard interpreter crash because the C stack is a separate, smaller limit), or write it iteratively. On any input you do not control the size of, write it iteratively.

If you need post-order work (finishing times, topological sort, subtree aggregation) in an iterative DFS, keep an iterator per stack frame so you can tell “I have more children to try” from “I am done”:

def dfs_pre_and_post(adj, source):
    """Iterative DFS that produces both entry (pre) and exit (post) orders.
    Each stack frame holds a live iterator over the vertex's adjacency list."""
    visited = [False] * len(adj)
    pre, post = [], []

    visited[source] = True
    pre.append(source)
    stack = [(source, iter(adj[source]))]

    while stack:
        u, it = stack[-1]
        advanced = False
        for v in it:                     # resumes where this iterator left off
            if not visited[v]:
                visited[v] = True
                pre.append(v)
                stack.append((v, iter(adj[v])))
                advanced = True
                break
        if not advanced:                 # adjacency list exhausted: u is finished
            stack.pop()
            post.append(u)

    return pre, post

Complexity: O(V + E) time, O(V) space (plus recursion depth, worst case V on a path graph).

What DFS is for: connected components, cycle detection, topological sort, strongly connected components (Tarjan, Kosaraju), articulation points and bridges, backtracking search over an implicit state graph (see ./21-backtracking.md), and any problem where you want to do work after the whole subtree is processed.

BFS or DFS?

For “is t reachable from s” either works. For “how far is t”, it must be BFS. For “order these tasks” or “is there a cycle”, it is usually DFS.

Connected components

Repeatedly start a traversal from any unvisited vertex; everything it reaches is one component.

def connected_components(adj):
    """Label every vertex of an undirected graph with its component id.
    Returns (count, comp). Time O(V + E)."""
    n = len(adj)
    comp = [-1] * n
    count = 0

    for s in range(n):
        if comp[s] != -1:
            continue                     # already assigned to an earlier component
        comp[s] = count
        stack = [s]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if comp[v] == -1:
                    comp[v] = count
                    stack.append(v)
        count += 1

    return count, comp

The outer loop over all s is what makes this O(V + E) overall rather than O(V(V + E)): each vertex is entered exactly once across all traversals, so the total work is still one pass over the graph. With comp in hand, “are u and v connected?” becomes comp[u] == comp[v] in O(1).

If the edges arrive incrementally and you need connectivity queries interleaved with insertions, a traversal is the wrong tool — use a disjoint-set union structure instead, see ./16-disjoint-set-union-find.md.

Cycle detection — and why directed and undirected differ

This is the classic place where copying the wrong snippet gives a subtly wrong program. The two cases genuinely need different logic.

Undirected: an edge to any visited vertex that is not your parent means a cycle. The “not your parent” exclusion is necessary because in an undirected graph every edge u—v appears in both adjacency lists, so from v you always see u again. That is not a cycle; it is the same edge.

def has_cycle_undirected(adj):
    """True iff the undirected graph contains a cycle. Time O(V + E)."""
    n = len(adj)
    visited = [False] * n

    def visit(u, parent):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                if visit(v, u):
                    return True
            elif v != parent:            # a back edge to some OTHER visited vertex
                return True
        return False

    return any(visit(s, -1) for s in range(n) if not visited[s])

A shortcut worth knowing: a connected undirected graph is acyclic (a tree) if and only if E = V − 1. So for a connected graph you can answer the question by counting edges. In general, an undirected graph is acyclic iff E = V − c where c is the number of connected components.

Directed: a cycle exists iff DFS finds a back edge to a vertex still on the recursion stack. “Already visited” is not enough — in a DAG like A→B, A→C, B→D, C→D, the DFS from A reaches D twice, and D is visited the second time, yet there is no cycle. The three-colour scheme distinguishes “finished” from “in progress”:

WHITE, GRAY, BLACK = 0, 1, 2         # unvisited / on the stack / fully explored


def has_cycle_directed(adj):
    """True iff the directed graph contains a cycle. Time O(V + E)."""
    n = len(adj)
    color = [WHITE] * n

    def visit(u):
        color[u] = GRAY                  # u is now on the current DFS path
        for v in adj[u]:
            if color[v] == GRAY:         # back edge -> cycle
                return True
            if color[v] == WHITE and visit(v):
                return True
        color[u] = BLACK                 # u and all its descendants are finished
        return False

    return any(visit(s) for s in range(n) if color[s] == WHITE)

The mnemonic: GRAY means “an ancestor of where I am standing.” Hitting a GRAY vertex means you have walked in a circle. Hitting a BLACK vertex means you have merely arrived at something already fully explored by a different route — a cross edge or forward edge, both harmless.

Two caveats for the undirected version. First, it treats parallel edges (two distinct edges between the same pair) as non-cycles because both look like “the parent”; if your input is a multigraph, track edge ids rather than the parent vertex. Second, a self-loop u—u is correctly reported as a cycle since u != parent in that check only when parent != u; if u is its own parent-free root the check fires as intended, but it is worth asserting your input has no self-loops rather than relying on the edge case.

Topological sort

A topological order of a DAG is a linear ordering of its vertices such that every edge u → v places u before v. It answers “in what order can I do these tasks so that every prerequisite is done first?” — course scheduling, build systems, spreadsheet recalculation, package installation, database migration ordering.

It exists if and only if the graph is a DAG. A cycle means a set of tasks that mutually depend on each other, and no order can satisfy them all.

Kahn’s algorithm (BFS-style) repeatedly removes a vertex with in-degree zero:

from collections import deque


def topo_sort_kahn(adj):
    """Topological order of a DAG via repeated removal of in-degree-0 vertices.
    Raises ValueError if the graph has a cycle. Time O(V + E), space O(V)."""
    n = len(adj)
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1

    q = deque(u for u in range(n) if indeg[u] == 0)
    order = []

    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1                # pretend we deleted the edge u -> v
            if indeg[v] == 0:            # v's last prerequisite just finished
                q.append(v)

    if len(order) != n:                  # some vertices never reached in-degree 0
        raise ValueError("graph has a cycle - no topological order exists")
    return order

Kahn’s gives you cycle detection for free — if the output is shorter than V, the leftover vertices are exactly those trapped in or downstream of a cycle. Swap the deque for a heap and you get the lexicographically smallest topological order, at O((V + E) log V). Track the layer index instead of just the order and you get the critical path length of the DAG, which is how build systems estimate parallel makespan.

DFS-based topological sort relies on a fact worth remembering: in a DAG, reverse post-order is a topological order. A vertex finishes only after all of its descendants have finished, so pushing vertices onto a list on exit and reversing gives you exactly what you want.

def topo_sort_dfs(adj):
    """Topological order via reverse DFS post-order. Time O(V + E)."""
    n = len(adj)
    color = [WHITE] * n
    order = []

    def visit(u):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:
                raise ValueError("graph has a cycle - no topological order exists")
            if color[v] == WHITE:
                visit(v)
        color[u] = BLACK
        order.append(u)                  # append on EXIT -> this is post-order

    for s in range(n):
        if color[s] == WHITE:
            visit(s)

    order.reverse()                      # reverse post-order == topological order
    return order

In Python, prefer Kahn’s for anything of unknown size, purely because it never touches the recursion limit. The standard library also ships graphlib.TopologicalSorter (Python 3.9+), which implements Kahn’s and additionally supports the “give me every node that is ready right now” API that parallel schedulers want.

Bipartite check (2-colouring)

A graph is bipartite if its vertices can be split into two sets with every edge crossing between them — equivalently, if it can be 2-coloured, equivalently if it has no odd-length cycle. Bipartite structure shows up in matching problems (jobs to workers, students to projects), conflict graphs (“these two cannot be in the same group”), and as a precondition for Hopcroft-Karp maximum matching.

def is_bipartite(adj):
    """Two-colour the graph with BFS. Returns (True, colors) or (False, None).
    Time O(V + E)."""
    n = len(adj)
    color = [-1] * n

    for s in range(n):
        if color[s] != -1:
            continue                     # this component is already coloured
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]   # neighbours get the opposite colour
                    q.append(v)
                elif color[v] == color[u]:    # an edge inside one side -> odd cycle
                    return False, None

    return True, color

The outer loop matters: bipartiteness is a property of every component, so a graph is bipartite only if all of its components are. Note that a graph with no edges is trivially bipartite, and every tree is bipartite (colour by depth parity).

Grids are graphs in disguise

A huge fraction of “grid” problems — flood fill, counting islands, shortest path through a maze, rotting oranges, number of enclaves — are ordinary graph problems where nobody bothered to build the graph. The trick is to see the implicit graph: each cell (r, c) is a vertex, and its neighbours are the up to four (or eight, if diagonals count) in-bounds cells adjacent to it. You never materialize an adjacency list; you compute neighbours on the fly.

DIRS4 = ((-1, 0), (1, 0), (0, -1), (0, 1))          # up, down, left, right


def count_islands(grid):
    """Number of connected groups of '1' cells in a rows x cols grid.
    Each cell is a vertex; edges connect orthogonally adjacent '1' cells.
    Time O(rows * cols), space O(rows * cols)."""
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    islands = 0

    for r0 in range(rows):
        for c0 in range(cols):
            if grid[r0][c0] != "1" or seen[r0][c0]:
                continue
            islands += 1                             # found a new component
            seen[r0][c0] = True
            stack = [(r0, c0)]                       # iterative: a 1000x1000 grid of
            while stack:                             # land would blow the call stack
                r, c = stack.pop()
                for dr, dc in DIRS4:
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < rows and 0 <= nc < cols
                            and grid[nr][nc] == "1" and not seen[nr][nc]):
                        seen[nr][nc] = True
                        stack.append((nr, nc))

    return islands


def grid_shortest_path(grid, start, goal):
    """Fewest steps from start to goal avoiding '#' cells, or -1.
    Plain BFS on the implicit grid graph. Time O(rows * cols)."""
    rows, cols = len(grid), len(grid[0])
    dist = {start: 0}
    q = deque([start])

    while q:
        r, c = q.popleft()
        if (r, c) == goal:
            return dist[(r, c)]
        for dr, dc in DIRS4:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and grid[nr][nc] != "#" and (nr, nc) not in dist):
                dist[(nr, nc)] = dist[(r, c)] + 1
                q.append((nr, nc))

    return -1

Three things go wrong in grid traversals more than anywhere else:

• Bounds checks before the array access. In Python, grid[-1][c] silently wraps to the last row instead of raising, so a missing 0 <= nr check produces a wrong answer rather than a crash.
• Recursion depth. A 1000×1000 grid of all-land is a path/blob 10⁶ vertices deep. Flood fill must be iterative at that size.
• Marking timing. Mark cells as seen when you push them, for exactly the reason BFS does — otherwise a cell with four qualifying neighbours enters the queue four times.

The same “implicit graph” idea generalizes far beyond grids: the vertices of a puzzle state graph (a Rubik’s cube configuration, a jug-pouring state, a word ladder) are generated by a successor function rather than stored. BFS over an implicit graph is the standard solution to “minimum number of moves” problems, and the only thing that changes is how you enumerate neighbours.

Where graphs show up outside algorithm practice

Graph thinking is not confined to interview problems. Query planners in a relational database represent a join order search as a DAG of plan nodes (see ../../postgresql-dba/en/10-query-planning-and-performance-tuning.md). Graph databases such as Neo4j make adjacency the primary storage primitive rather than a derived one — see ../../backend/en/09-nosql-databases.md. Distributed data processing frameworks schedule work as a DAG of stages, discussed in ../../data-engineer/en/10-big-data-and-distributed-computing.md. In every case the algorithms are the ones in this note, applied to a domain-specific graph.

Best Practices

• Default to an adjacency list. Switch to a matrix only when the graph is dense, V is small, or has_edge is genuinely the hot path. Switch to an edge list only when the algorithm consumes edges globally (Kruskal, Bellman-Ford).
• Relabel vertices to 0..n−1 at the boundary. Take whatever ids the problem gives you — strings, UUIDs, coordinates — and map them once to dense integers. Every array-based structure downstream becomes simpler and several times faster.
• When building an undirected graph, append in both directions. Write a single add_edge helper and use it everywhere rather than hand-appending at call sites; the bug where half the edges are one-way is very hard to see and very easy to prevent.
• Mark vertices at push time in BFS, at pop time in the iterative DFS. These are different for a reason: BFS pushes each vertex once and needs the first-discovery distance to be final; iterative DFS deliberately allows duplicates on the stack.
• Write DFS iteratively for anything you do not control the size of. Python’s 1000-frame default recursion limit will find your 10,000-vertex path graph. Raising the limit trades a clean RecursionError for a segfault.
• Use the right cycle-detection routine for the graph’s directedness. Undirected needs the parent exclusion; directed needs the on-stack (GRAY) check. Using the undirected version on a directed graph reports cycles in every diamond; using the directed version on an undirected graph reports a cycle for every single edge.
• Prefer collections.deque over list for queues. list.pop(0) is O(n). This is the single most common way to accidentally write a quadratic BFS.
• Handle disconnected graphs explicitly. A single BFS/DFS from vertex 0 only covers vertex 0’s component. Any property of the whole graph — bipartiteness, acyclicity, component count — needs the loop over all start vertices.
• Check V, E and the presence of self-loops/parallel edges before trusting a snippet. Most published graph code silently assumes a simple graph.
• Store parent[] alongside dist[] from the start. Reconstructing the actual path afterwards is nearly free if you kept parents and impossible if you did not.
• Sanity-check with the handshake lemma. After building an undirected graph, sum(len(adj[u]) for u in range(n)) must equal 2 * E. A one-line assertion catches a whole class of construction bugs.

References

• roadmap.sh — Data Structures & Algorithms
• Graph (abstract data type) — Wikipedia
• Graph theory — Wikipedia
• Breadth-first search — Wikipedia
• Depth-first search — Wikipedia
• Topological sorting — Wikipedia
• Bipartite graph — Wikipedia
• cp-algorithms — Breadth-first search
• cp-algorithms — Depth-first search
• cp-algorithms — Finding connected components
• cp-algorithms — Checking a graph for acyclicity and finding a cycle
• cp-algorithms — Topological sorting
• cp-algorithms — Check whether a graph is bipartite
• CLRS — Introduction to Algorithms, Part VI: Graph Algorithms
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• VisuAlgo — Graph traversal (DFS/BFS)
• Python Documentation — collections.deque
• Python Documentation — graphlib.TopologicalSorter
• Big-O Cheat Sheet