Graphs and Graph Algorithms Questions

Direct answer

Kruskal's algorithm builds a minimum spanning tree (MST) by sorting all edges by weight ascending, then greedily adding each edge to the MST as long as it does not create a cycle with edges already added, using Union-Find to detect cycles in near-constant time per check. The algorithm stops once $n-1$ edges have been added (a spanning tree on $n$ nodes always has exactly $n-1$ edges), and total runtime is dominated by the sort: $O(E \log E)$, with the Union-Find operations contributing an additional $O(E \cdot \alpha(n))$, which is asymptotically dominated by the sort.

Structured elaboration

Why greedy-by-weight, skip-cycles is correct. This is the cut property in action: for any partition of the nodes into two non-empty sets, the minimum-weight edge crossing that partition must belong to SOME minimum spanning tree. Processing edges in ascending weight order and adding each one that does not close a cycle is exactly equivalent to repeatedly picking the lightest crossing edge for whatever partition the current partial MST implicitly defines (the current set of already-connected components on one "side," everything else on the other), which is why the greedy approach provably produces a GLOBALLY minimum tree, not just a locally reasonable one.

Role of Union-Find. Two nodes already in the same Union-Find set means a path already connects them using edges already accepted into the MST; adding another edge between them would necessarily create a cycle. Checking find(u) != find(v) before accepting an edge is an $O(\alpha(n))$ amortized cycle check, far cheaper than an explicit DFS/BFS cycle check per candidate edge, which is what makes Kruskal's practical at scale.

Sorting complexity dominates. Sorting $E$ edges is $O(E \log E)$. Since $E \le V^2$ for a simple graph (and typically $E = O(V)$ for sparse graphs common in practice), $O(E \log E)$ is also frequently written as $O(E \log V)$ (because $\log(V^2) = 2\log V$, a constant factor difference). The Union-Find operations across all $E$ edges cost $O(E \cdot \alpha(n))$, which is asymptotically smaller than the sort, so the sort is the bottleneck: Kruskal's overall complexity is $O(E \log E)$.

Worked example

from typing import List, Tuple

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

def kruskal(n: int, edges: List[Tuple[int, int, int]]) -> List[Tuple[int, int, int]]:
    dsu = DSU(n)
    mst = []
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if dsu.union(u, v):
            mst.append((u, v, w))
            if len(mst) == n - 1:
                break
    return mst

if __name__ == "__main__":
    n = 6
    edges = [
        (0, 1, 4), (0, 2, 4), (1, 2, 2),
        (2, 3, 3), (2, 5, 2), (2, 4, 4), (3, 4, 3), (5, 4, 3), (5, 3, 1)
    ]
    mst = kruskal(n, edges)
    total_weight = sum(w for _, _, w in mst)
    print("MST edges:", mst)
    print("total weight:", total_weight)
    print("edge count:", len(mst), "(expected n-1 =", n - 1, ")")

Output:

MST edges: [(5, 3, 1), (1, 2, 2), (2, 5, 2), (3, 4, 3), (0, 1, 4)]
total weight: 12
edge count: 5 (expected n-1 = 5 )

Trace by hand: edges sorted by weight are (5,3,1), (1,2,2), (2,5,2), (2,3,3), (3,4,3), (5,4,3), (0,1,4), (0,2,4), (2,4,4). Processing in that order: (5,3,1) accepted (new edge, new component {5,3}). (1,2,2) accepted ({1,2}). (2,5,2) accepted, merging {1,2} and {5,3} into {1,2,5,3}. (2,3,3) rejected, 2 and 3 are already in the same component. (3,4,3) accepted ({1,2,5,3,4}). (5,4,3) rejected, same component already. (0,1,4) accepted, merging in node 0, now 5 edges total, stop. Sum: $1+2+2+3+4=12$, matching the printed output exactly.

Trade-offs and pitfalls

• Common mistake: forgetting the early-stop condition. Once $n-1$ edges are accepted, the MST is complete and any further edges are guaranteed to create a cycle if added; continuing to scan the remaining sorted edges (which Union-Find would correctly reject anyway) wastes work, though it does not produce a WRONG answer, only a slower one on a graph where $E \gg V$.
• Kruskal's requires the graph to be CONNECTED to produce a true spanning tree. On a disconnected graph, the algorithm terminates having accepted fewer than $n-1$ edges (once no more cycle-free edges remain to add), producing a minimum spanning FOREST, one tree per connected component, rather than a single tree; a correct implementation should check len(mst) == n - 1 at the end and treat a shortfall as a signal the graph was disconnected, not silently return a forest labeled as a tree.
• Common mistake: implementing the cycle check with a slower structure (a plain visited-array BFS/DFS per candidate edge, $O(V+E)$ each) instead of Union-Find, which turns an $O(E \log E)$ algorithm into something closer to $O(E \cdot (V+E))$ in the worst case, since every one of the $E$ edges could require a full traversal to check.
• Kruskal's is a better fit than Prim's when the edge list is already available and sorting is cheap relative to the graph's density (sparse graphs); Prim's, which grows a single tree outward using a priority queue keyed on the CHEAPEST edge crossing the current tree's boundary, tends to be preferred on dense graphs where an adjacency-matrix-backed Prim's can run in $O(V^2)$ without ever needing to sort the full edge list.

Direct answer

Bellman-Ford detects a negative-weight cycle by relaxing every edge $V-1$ times and then running one more pass: if any edge still improves a distance after $V-1$ passes have already had enough rounds to propagate every legitimate shortest simple path, that improvement can only be coming from a cycle that keeps paying off each time it is traversed, which is exactly what a negative cycle is. The algorithm costs $O(V \cdot E)$, strictly worse than Dijkstra's $O((V+E)\log V)$, but it is the tool of choice whenever negative edge weights (not just non-negative ones) must be supported, since Dijkstra's greedy finalize-and-never-revisit strategy is provably wrong once weights can be negative.

Structured elaboration

Why $V-1$ passes suffice, and why a $V$-th exposes a cycle. Any shortest path that does not repeat a vertex (a simple path) has at most $V-1$ edges, since a path with $V$ or more edges on a graph with only $V$ vertices must revisit one. Each full relaxation pass propagates a shortest-path value at least one edge further along its optimal path (in the worst case), so $V-1$ passes are enough to fully propagate every simple shortest path. If a negative cycle is reachable from the source, however, there is no shortest SIMPLE path at all: the "shortest path" can always be made cheaper by looping the cycle one more time, so the distance is not well-defined (it is $-\infty$ in the limit), and relaxation never stops improving, which is exactly what the $V$-th pass is checking for.

Complexity. $O(V \cdot E)$: $V-1$ (or fewer, with early termination when a pass makes no change) full passes over all $E$ edges, plus a final detection pass.

When Bellman-Ford is preferred over Dijkstra. The deciding factor is whether negative weights are possible at all, not performance: Dijkstra is asymptotically faster whenever it is legal to use, so Bellman-Ford's only justification is a graph where some edge genuinely can be negative. Two scenarios where this shows up specifically in machine learning (ML) systems or feature computations: a feature store's derived-feature dependency graph where an edge's weight is the marginal COST of computing one feature from an upstream one, and a caching or precomputation transformation legitimately REDUCES that downstream cost (a negative-weight edge), so finding the cheapest chain of transformations to materialize a target feature needs Bellman-Ford precisely because some of those cost-reducing edges are negative; and reward-shaping in a reinforcement learning (RL) pipeline, where a state-transition graph's edge weight is a change in loss or cost and some transitions are explicitly loss-reducing by design (a shaped reward bonus), so a "cheapest path" query over that graph again requires an algorithm that tolerates negative weights. Beyond ML specifically, the same need for negative-weight tolerance appears in a currency arbitrage graph modeling exchange-rate log-ratios, or a dependency graph with penalty and bonus edges that can legitimately be negative. Once negative weights are possible, there is no faster correct alternative for general graphs, only Bellman-Ford (or, if the graph happens to also be acyclic, a topological-order relaxation pass in $O(V+E)$, which sidesteps the need for repeated passes entirely because acyclicity alone, independent of weight sign, guarantees a safe processing order).

The $|E| \gg |V|$ scale consideration. Bellman-Ford's cost is $O(V \cdot E)$, which grows linearly with $E$ for a fixed $V$, so on a graph where edges vastly outnumber vertices (a dense graph, or a multigraph with many parallel edges between the same pairs), the constant-factor gap between Bellman-Ford's $O(VE)$ and Dijkstra's $O((V+E)\log V)$ widens further, since $V \cdot E$ grows much faster than $(V+E)\log V$ as $E$ increases with $V$ fixed. This sharpens the earlier point: if there is any way to confirm the graph has no negative weights (even at ingestion time, by validating every edge as it is added), switching to Dijkstra on a dense graph is not a marginal win, it can be a large one.

Worked example

Take the 4-node cycle $1\to2$ (weight -3), $2\to3$ (weight 1), $3\to1$ (weight 1), reachable from source 0 via $0\to1$ (weight 1). The cycle's total weight is $-3+1+1=-1$, negative.

After 3 relaxation passes ($V-1=3$ for this 4-node graph), the distances to nodes on the cycle keep decreasing each additional pass rather than stabilizing (each additional loop around the cycle subtracts another 1 from the achievable distance), so the 4th pass still finds an edge to relax, correctly signaling a negative cycle.

Verification. Rather than leave that as an unsupported claim, here is the actual implementation and its real output on this exact graph:

def bellman_ford(graph, source):
    dist = {u: float("inf") for u in graph}
    pred = {u: None for u in graph}
    dist[source] = 0
    V = len(graph)
    for _ in range(V - 1):
        changed = False
        for u in graph:
            if dist[u] == float("inf"):
                continue
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    pred[v] = u
                    changed = True
        if not changed:
            break
    culprit = None
    for u in graph:
        if dist[u] == float("inf"):
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                culprit = v
                pred[v] = u
                break
        if culprit is not None:
            break
    if culprit is None:
        return {"has_negative_cycle": False, "distances": dist, "predecessors": pred}
    node = culprit
    for _ in range(V):
        node = pred[node]
    cycle = [node]
    cur = pred[node]
    while cur != node:
        cycle.append(cur)
        cur = pred[cur]
    cycle.append(node)
    cycle.reverse()
    return {"has_negative_cycle": True, "cycle": cycle}

g = {0: [(1, 1)], 1: [(2, -3)], 2: [(3, 1)], 3: [(1, 1)]}
r = bellman_ford(g, 0)
print("result:", r)

def cycle_weight(graph, cycle):
    total = 0
    for i in range(len(cycle) - 1):
        u, v = cycle[i], cycle[i + 1]
        w = next(w for vv, w in graph[u] if vv == v)
        total += w
    return total

print("cycle weight:", cycle_weight(g, r["cycle"]))

Output (actually executed with python3):

result: {'has_negative_cycle': True, 'cycle': [1, 2, 3, 1]}
cycle weight: -1

Confirms the algorithm flags has_negative_cycle: True and reconstructs the cycle [1, 2, 3, 1], whose own edge weights independently re-sum to $-1$.

Trade-offs and pitfalls

• Common mistake: treating "the graph has a negative edge" and "the graph has a negative cycle" as the same warning sign. A single negative edge with no cycle is completely fine for Bellman-Ford and produces a well-defined, correct shortest-path answer; only a negative CYCLE (a way to keep re-visiting and re-paying a net-negative loop) breaks the notion of "shortest path" itself.
• Common mistake: running only $V-1$ passes and stopping, without the extra detection pass, on data that has not been validated to be cycle-free. Silently returning distances that are secretly still decreasing (had one more pass been run) reports numbers that are not the true shortest distances, without any signal that something is wrong.
• The early-termination optimization (stop as soon as one full pass makes no change) is safe and commonly implemented, but does not remove the need for the dedicated detection pass on the FIRST run through the loop that would otherwise have kept changing; it only shortens how many of the $V-1$ passes actually execute when the graph converges early.
• If the domain genuinely never has negative weights, defaulting to Bellman-Ford anyway "to be safe" trades away real performance for a guarantee that costs nothing to instead enforce at the input-validation layer (reject or flag any negative edge on ingestion, then use Dijkstra with confidence).

Direct answer

Both breadth-first search (BFS) and depth-first search (DFS) run in $O(V+E)$ time on an adjacency list, because the total work is bounded by the number of vertices touched plus the total number of neighbor-pointer traversals across the whole run, which sums to exactly $E$ (or $2E$ for an undirected graph, still $O(E)$). On an adjacency matrix, both run in $O(V^2)$, because finding a vertex's neighbors means scanning its entire row of $V$ entries regardless of how many of them are actually edges, and this happens for every vertex.

Structured elaboration

Adjacency list derivation. Let $\text{visited}[]$ track which vertices have been processed, guaranteeing each vertex is expanded at most once.

• Per-vertex overhead: each of the $V$ vertices is enqueued/pushed and dequeued/popped at most once, each operation $O(1)$ amortized, contributing $\Theta(V)$ total.
• Per-edge overhead: when a vertex $u$ is processed, the algorithm iterates its adjacency list, one step per neighbor. Summed across every vertex processed during the traversal, this equals the total number of adjacency-list entries touched. For a directed graph, $\sum_v \deg^+(v) = E$ (every edge appears exactly once, in its source's list). For an undirected graph, $\sum_v \deg(v) = 2E$ (every edge appears once in each endpoint's list), still $\Theta(E)$ since the factor of 2 is a constant.
• Total: $\Theta(V) + \Theta(E) = \Theta(V+E)$.
• Why an edge is inspected only a constant number of times: visited[] ensures a vertex's adjacency list is scanned exactly once (when that vertex itself is dequeued/popped), not once per incoming edge; without this guard, a vertex reachable by many edges could have its list rescanned redundantly.

Adjacency matrix derivation.

• Per-vertex overhead: identical to the list case, $\Theta(V)$ for enqueue/dequeue bookkeeping.
• Per-edge overhead: finding vertex $u$'s neighbors means scanning row $u$ of the $V \times V$ matrix, $V$ cell checks, REGARDLESS of how many of those cells are actually 1 (an edge). This happens once per processed vertex, giving $V$ vertices $\times$ $V$ cells each $= \Theta(V^2)$.
• Total: $\Theta(V) + \Theta(V^2) = \Theta(V^2)$, dominated entirely by the per-vertex row scan; the matrix's time bound does not depend on $E$ at all, sparse or dense.

Directed versus undirected. The derivation's shape is identical for both; the only difference is the constant factor in the edge-count term ($E$ for directed, $2E$ for undirected in the list case; the matrix case is unaffected either way since a full row is scanned regardless of the graph's directedness, though an undirected adjacency matrix is symmetric, which some implementations exploit to only store, though not necessarily to only SCAN, roughly half the entries).

Assumptions about the visiting mechanism. This analysis assumes iterating a vertex's adjacency list (or a matrix row) costs $O(1)$ per element visited, true for a plain array, a linked list, or a language iterator with $O(1)$ amortized next(). If neighbors were instead stored in a structure with a more expensive per-element access cost (a balanced tree ordered by neighbor id, for instance, used to support fast edge-existence checks), the per-edge term would pick up an extra $O(\log \deg(v))$ factor, changing the bound to $O(V + E \log(\text{avg degree}))$; the classic $O(V+E)$ result specifically assumes the cheapest reasonable neighbor-storage structure, not any adjacency-list variant whatsoever.

Worked example

Take $V = 1000$, and consider two graphs on that vertex set: a sparse one with $E = 2000$ (average degree 4) and a dense one with $E = 400{,}000$ (close to the $V(V-1)/2 \approx 499{,}500$ maximum for an undirected simple graph).

Adjacency-list time is $\Theta(V+E)$: $1000 + 2000 = 3000$ "units" of work for the sparse graph, $1000 + 400{,}000 = 401{,}000$ units for the dense one, work that scales directly with how many real edges exist.

Adjacency-matrix time is $\Theta(V^2) = 1000^2 = 1{,}000{,}000$ units of work for BOTH graphs, since the matrix traversal cost never looks at $E$ at all. For the sparse graph, the matrix does roughly 333x MORE work than the list (1,000,000 vs 3,000); for the dense graph, the gap narrows sharply but does NOT invert: the list's 401,000 units is still fewer than the matrix's 1,000,000, about 2.5x less. This is not an artifact of the chosen numbers: for ANY simple graph (no self-loops or parallel edges), $E$ is bounded by $V(V-1)/2$, so $V+E$ is bounded by $V(V+1)/2 \approx V^2/2$, always roughly HALF of the matrix's $V^2$, even at the maximum possible density (at $V=1000$'s true max, $E=499{,}500$, list work is 500,500 versus the matrix's 1,000,000, still about 2x less). The list's raw operation count can never actually exceed the matrix's for a full traversal of a simple graph; there is no density at which this accounting makes the matrix outright faster. What DOES happen as $E$ approaches $V^2$ is that the list's ASYMPTOTIC advantage evaporates (both become $\Theta(V^2)$), which is why dense-graph implementations reach for the matrix anyway: not because it traverses faster, but because its better constant factors, contiguous memory with strong cache locality, a simpler implementation, and $O(1)$ point edge-existence checks the list cannot match, are worth more once the list's shrinking speed edge is no longer an order-of-magnitude win.

Trade-offs and pitfalls

• Common mistake: assuming the $O(V+E)$ vs $O(V^2)$ comparison means the list is dramatically faster at every density, OR (the opposite, equally wrong error) that a genuinely dense graph flips the ordering and makes the matrix faster in raw traversal work. Neither extreme is right: for a simple graph the list's operation count can never exceed roughly $V^2/2$, so it never actually loses this race, but its margin shrinks from over 300x at low density to under 3x near maximum density, which is why dense-graph code often reaches for the matrix anyway, not because it got faster, but because the list's shrinking advantage stops being worth its extra implementation complexity once cache locality and $O(1)$ edge lookups are on the table.
• Common mistake: treating $O(V+E)$ as automatically implying the algorithm is "linear." It is linear in the SIZE OF THE INPUT (which is itself $\Theta(V+E)$ for an adjacency list), not linear in $V$ alone; a graph where $E$ grows quadratically in $V$ makes the traversal quadratic too, list or no list.
• The visited-array guard is what makes the list bound tight, not incidental to it. Removing it (allowing a vertex's adjacency list to be rescanned every time any neighbor points to it) would make the bound $O(V \cdot E)$ in the worst case (a densely-interconnected graph revisiting the same expensive vertex repeatedly), which is exactly the kind of subtle omission that turns a correct asymptotic claim into a wrong one.
• Space follows the same split: adjacency list is $\Theta(V+E)$ (proportional to what actually exists), matrix is $\Theta(V^2)$ (fixed regardless of edge count), independent of the traversal algorithm's own $O(V)$ queue/stack overhead, which is the same for both representations.

Direct answer

Adjacency list, adjacency matrix, and compressed sparse row (CSR) trade cache locality, edge-existence-check speed, and update flexibility against each other, and no single one wins every query type. For a monitoring system that mostly iterates neighbors and rarely mutates the graph structure, CSR (contiguous storage, best cache locality) is usually the strongest default; if edge-existence checks dominate the workload and the graph is small enough, an adjacency matrix's O(1) lookup wins outright; if the graph mutates frequently, a plain adjacency list is the only one of the three that handles that well without expensive rebuilds.

Structured elaboration

Compressed sparse row (CSR) layout, concretely. CSR stores a graph as two flat arrays instead of a list of lists: indptr (size $V+1$), where indptr[v] and indptr[v+1] mark the start and end of vertex $v$'s neighbor slice, and indices (size $E$), the flattened, concatenated neighbor lists of every vertex back to back. Vertex $v$'s neighbors are exactly indices[indptr[v]:indptr[v+1]], a single contiguous memory read. A third parallel array data (also size $E$) holds edge weights or labels if the graph is weighted, indexed the same way as indices.

Cache locality. A plain adjacency list, especially one implemented as a list of separately-heap-allocated per-node lists, scatters each node's neighbors across memory wherever the allocator happened to place them; walking from node to node during a traversal means following pointers to unrelated memory regions, which defeats CPU cache prefetching. CSR's indices array is one single contiguous block; scanning any node's slice, or scanning many nodes' slices in sequence (as a repeated monitoring sweep does), stays within cache-friendly, sequentially-addressed memory the whole time. This is CSR's actual selling point over a plain list: not a better asymptotic bound (both are $O(\deg(v))$ for neighbor iteration) but a dramatically better constant factor from memory layout alone.

Memory usage and update frequency. An adjacency matrix's $O(V^2)$ space is wasteful for sparse graphs (most cells encode "no edge") but supports $O(1)$ point updates trivially, since flipping one cell needs no restructuring. CSR's $O(V+E)$ space matches an adjacency list, but a single edge insertion into an already-built CSR structure generally requires shifting every subsequent entry in indices (and updating every indptr entry from that point onward), an $O(V+E)$ operation in the worst case; CSR is built for static or batch-rebuilt graphs, not graphs under constant incremental edit.

Worked example

A monitoring system tracking 50,000 services with roughly 200,000 dependency edges (average degree 4, clearly sparse: $E \ll V^2 = 2.5 \times 10^9$).

• Adjacency matrix: $V^2 = 2.5 \times 10^9$ cells; even at 1 bit per cell, that is over 300 MB, almost entirely encoding "no dependency," and every neighbor-iteration query pays a 50,000-cell row scan regardless of the target node's actual degree of 4. Ruled out on both memory and iteration-speed grounds for this workload.
• Adjacency list (per-node Python lists or similar): $O(V+E) \approx 250{,}000$ entries, modest memory, but repeated sweeps (a monitoring tool re-scanning the whole dependency graph every few seconds) pay the pointer-chasing cost on every sweep.
• CSR: same $O(V+E) \approx 250{,}000$ entries, but stored contiguously; a full sweep reads through one linear block of memory, and the batch-update pattern here (dependencies change occasionally, not every request) fits CSR's rebuild-on-batch model well: rebuild the CSR structure once when a deployment changes dependencies, then serve many fast, cache-friendly reads until the next rebuild.

For this workload, CSR is the strongest default specifically because reads (neighbor iteration, repeated sweeps) vastly outnumber writes (dependency changes), which is the regime CSR is built for.

Trade-offs and pitfalls

• Common mistake: picking CSR for a graph under frequent, fine-grained mutation (an edge added or removed on every request) without accounting for the rebuild cost; CSR's read-side wins are real but assume a read-heavy, write-light or write-batched access pattern.
• Common mistake: defaulting to an adjacency matrix "for simplicity" on a graph whose density was never actually checked; the moment $V$ grows into the tens of thousands, an $O(V^2)$ structure becomes prohibitive even at 1 bit per cell, well before considering iteration cost at all.
• Edge-existence checks specifically favor the matrix ($O(1)$, unconditionally) over CSR's $O(\log \deg(v))$ (needs a sorted slice) or a plain list's $O(\deg(v))$ (needs no preprocessing but is linear); a workload dominated by "does edge (u,v) exist" queries on a graph small enough to matrix-fit should not default to CSR or a list just because they are more common defaults.
• Parallel sharding is where CSR's design pays off most concretely: because indptr gives an exact, precomputed byte range for every vertex's neighbors, splitting the vertex set into contiguous ranges and handing each range to a separate worker requires no coordination or locking between workers, unlike a list-of-lists structure where per-node allocations may be scattered across memory in a way that makes range-based sharding no more cache-friendly than random sharding.

Direct answer

Converting matrix to list means scanning every cell of the $V \times V$ matrix and recording the column indices where an entry is nonzero, an $O(V^2)$ operation regardless of how sparse the result is. Converting list to matrix means allocating a zeroed $V \times V$ grid and, for each stored edge, setting one entry (two for undirected, since both $(u,v)$ and $(v,u)$ must be marked). Prefer the list representation when the graph is sparse or algorithms need neighbor iteration; prefer the matrix when dense or when O(1) edge-existence checks dominate.

Structured elaboration

Approach. Nodes are labeled $0..n-1$. matrixToList walks all $n^2$ cells once; each nonzero cell appends a neighbor to the source vertex's list. listToMatrix allocates an $n \times n$ grid of zeros, then for every stored edge sets the corresponding cell(s): one cell for a directed graph, both symmetric cells for undirected. A third useful variant, building both representations directly from a raw edge list in a single pass (rather than building one and converting to the other), avoids doing the $O(n^2)$ matrix-scan step entirely when the source data is already an edge list.

Directed vs undirected. For directed graphs, only the $(u,v)$ cell/list-entry is written. For undirected graphs, both listToMatrix and the edge-list builder must write both $(u,v)$ and $(v,u)$; matrixToList does not need special-casing since a symmetric input matrix already encodes both directions, it just needs the caller to have supplied a symmetric matrix if the graph is meant to be undirected.

Worked example

#include <vector>
#include <utility>
#include <iostream>
#include <stdexcept>
using std::vector;
using std::pair;

// --- Convert matrix -> list ---
vector<vector<int>> matrixToList(const vector<vector<int>>& mat) {
    int n = (int)mat.size();
    vector<vector<int>> adj(n);
    for (int u = 0; u < n; ++u) {
        if ((int)mat[u].size() != n) throw std::invalid_argument("matrix must be n x n");
        for (int v = 0; v < n; ++v)
            if (mat[u][v]) adj[u].push_back(v);
    }
    return adj;
}

// --- Convert list -> matrix ---
vector<vector<int>> listToMatrix(const vector<vector<int>>& adj, bool directed) {
    int n = (int)adj.size();
    vector<vector<int>> mat(n, vector<int>(n, 0));
    for (int u = 0; u < n; ++u)
        for (int v : adj[u]) {
            mat[u][v] = 1;
            if (!directed) mat[v][u] = 1;
        }
    return mat;
}

// --- Build both directly from an edge list in one pass ---
pair<vector<vector<int>>, vector<vector<int>>> buildBothFromEdgeList(
    int n, const vector<pair<int,int>>& edges, bool directed) {
    vector<vector<int>> adj(n);
    vector<vector<int>> mat(n, vector<int>(n, 0));
    for (auto& e : edges) {
        int u = e.first, v = e.second;
        adj[u].push_back(v);
        mat[u][v] = 1;
        if (!directed) { adj[v].push_back(u); mat[v][u] = 1; }
    }
    return {adj, mat};
}

int main() {
    // 4-node directed graph: edges 0->1, 0->2, 1->2, 2->3, 3->0
    vector<vector<int>> mat = {{0,1,1,0},{0,0,1,0},{0,0,0,1},{1,0,0,0}};
    auto adj = matrixToList(mat);
    std::cout << "Adjacency list from matrix (directed):\n";
    for (int u = 0; u < (int)adj.size(); ++u) {
        std::cout << u << ": ";
        for (int v : adj[u]) std::cout << v << " ";
        std::cout << "\n";
    }
    auto mat2 = listToMatrix(adj, true);
    std::cout << "Round-trip list->matrix matches original: " << (mat2 == mat) << "\n";

    // 4-node undirected path: 0-1-2-3
    vector<vector<int>> undirected_adj = {{1},{0,2},{1,3},{2}};
    auto undirected_mat = listToMatrix(undirected_adj, false);
    std::cout << "Undirected adjacency matrix from list:\n";
    for (auto& row : undirected_mat) { for (int x : row) std::cout << x << " "; std::cout << "\n"; }

    vector<pair<int,int>> edges = {{0,1},{0,2},{1,2},{2,3},{3,0}};
    auto [adj2, mat3] = buildBothFromEdgeList(4, edges, true);
    std::cout << "Direct-from-edge-list build agrees with edge-by-edge insertion: "
              << (adj2 == adj && mat3 == mat) << "\n";
}

Output (actually executed with g++ -std=c++17):

Adjacency list from matrix (directed):
0: 1 2 
1: 2 
2: 3 
3: 0 
Round-trip list->matrix matches original: 1
Undirected adjacency matrix from list:
0 1 0 0 
1 0 1 0 
0 1 0 1 
0 0 1 0 
Direct-from-edge-list build agrees with edge-by-edge insertion: 1

Complexity

• matrixToList: time $O(n^2)$ (must inspect every cell even if the graph is sparse), space $O(n + m)$ for the output list, $m$ = number of edges.
• listToMatrix: time $O(n + m)$ to walk the input lists, space $O(n^2)$ for the allocated matrix (dominates regardless of $m$).
• buildBothFromEdgeList: time $O(n + m)$, but still pays $O(n^2)$ space for the matrix half of the output.
• The conversion itself is never cheaper than the more expensive of the two representations' own space bound; you cannot avoid the $O(n^2)$ cost anywhere a matrix is materialized.

Edge cases

• Non-square input matrix: validated and rejected (std::invalid_argument) rather than silently reading out of bounds.
• Undirected input list that already contains both directions (e.g., adj[0] contains 1 and adj[1] contains 0): listToMatrix writing both symmetric cells is idempotent, so duplicate directions in the input do not corrupt the output.
• Self-loops (mat[u][u] = 1): handled naturally by both directions, no special-casing needed.
• Weighted graphs: swap the int 0/1 matrix for a weight type and use a sentinel (e.g., infinity or a boolean "present" flag alongside the weight) instead of 0 to distinguish "no edge" from "edge with weight 0."

Trade-offs and pitfalls

• If the source data naturally arrives as an edge list (as it often does from a database export or event stream), building both representations directly (the third function above) avoids the wasted intermediate $O(n^2)$ scan that matrixToList would otherwise require.
• Common mistake: converting list to matrix for a graph where $n$ is large and the result will be sparse anyway; the $O(n^2)$ allocation dominates and defeats the purpose of having started from a compact list.
• Common mistake: forgetting the symmetric write for undirected graphs, which silently turns an undirected graph into a directed one in the matrix representation and breaks any downstream algorithm that assumes symmetry (for example, an undirected connected-components check).