Graphs and Graph Algorithms Questions
Graph representations (adjacency list and adjacency matrix) and the traversal algorithms applied to general, non-tree structures: BFS, DFS, topological sort (Kahn's algorithm and DFS-based), shortest paths (Dijkstra, Bellman-Ford, A*), minimum spanning trees, cycle detection, connected components, and union-find. Covers modeling a problem as a graph even when the underlying data is not obviously graph-shaped, such as state-space search, an implicit graph over strings or grid cells (for example Word Ladder), or a task-dependency graph, and implementing these traversals with a hash map or hash set as the storage vehicle (adjacency map, visited set, memoization table), not the subject being tested. The graded skill is traversal, ordering, connectivity, or shortest-path reasoning over nodes and edges. This topic does not own: traversal, reconstruction, or serialization of a single-rooted binary tree (preorder, inorder, postorder, or level-order implementation, rebuilding a tree from traversal arrays, lowest common ancestor, binary search tree validation), which belongs to binary trees and binary search trees even though a tree is technically a graph; hash table internals such as hash function design, collision resolution, and load factor and resizing, which belong to hashing and hash tables; and deriving or comparing algorithmic complexity across graph algorithms without implementing them, such as comparing the time complexity of BFS, DFS, Dijkstra, and A*, which belongs to time and space complexity analysis. One of the highest-signal areas in senior coding interviews.
Discuss how common graph algorithms should handle input edge cases: self-loops, parallel/multi-edges, isolated nodes, and nodes with multiple labels. For BFS/DFS, Dijkstra, union-find and topological sort, describe concrete pitfalls you might encounter in production and how to sanitize or validate input to make implementations robust.
Sample Answer
Direct answer
Self-loops, parallel edges, isolated nodes, and multi-labeled nodes each break a different assumption that textbook graph algorithms make silently. The fix in every case is the same shape: normalize the input into a well-defined canonical graph once, before any algorithm runs, rather than trying to make every algorithm defensive against every possible malformed input independently.
Structured elaboration
General sanitization, done once up front:
- Canonicalize node identity: if a node can carry multiple labels (say, a user identified by both an internal id and an email), map every label to one canonical id before building the graph, so two labels never get treated as two different vertices.
- Make directedness and weightedness explicit metadata on the graph object, not an assumption baked into each algorithm.
- Decide, as policy, how to treat parallel edges: keep them all, collapse to a single edge with the minimum or summed weight, or reject them, and apply that policy consistently at ingestion time.
Breadth-first search (BFS) and depth-first search (DFS).
- Pitfall: a self-loop (an edge from a node to itself) can cause an algorithm that naively re-enqueues or re-recurses into "unvisited-looking" neighbors to loop forever if it does not check the node against its own visited set before revisiting.
- Pitfall: parallel edges between the same pair of nodes cause duplicate work (the same neighbor gets examined twice) but not incorrectness, if the visited set is checked correctly.
- Pitfall: isolated nodes (no edges at all) are invisible if the traversal only iterates over nodes reachable from a starting adjacency list; they must be included by iterating the full node set, not just the edges.
- Fix: ignore self-loops when expanding neighbors, deduplicate a node's adjacency entries or rely on a visited set to absorb duplicates from parallel edges, and iterate the complete node set (not just nodes that appear in some edge) so isolated nodes are still reported.
Dijkstra's algorithm.
- Pitfall: negative edge weights break Dijkstra's correctness proof outright (it can commit to a shortest distance for a node before a cheaper path through a negative edge is discovered); a self-loop with a negative weight is a degenerate case of the same problem, an infinitely improvable "path."
- Pitfall: parallel edges with different weights, if not collapsed to the minimum, cause the algorithm to needlessly relax the more expensive one.
- Fix: validate no negative weights at ingestion (reject the input, or route to Bellman-Ford instead if negative weights are legitimate); collapse parallel edges to the minimum weight before running; ignore or explicitly reject positive-weight self-loops (they can never improve a shortest path so are safe to drop, but a negative-weight self-loop must be rejected, not silently dropped, since it signals corrupt input).
Union-Find (disjoint set).
- Pitfall: repeated
unioncalls on the same pair (from parallel edges, or a self-loop passed asunion(x, x)) are not incorrect, but they are wasted work at scale if the caller does not short-circuit them. - Pitfall: multi-labeled nodes that were not canonicalized to one id will be unioned as though they were two separate elements, silently splitting what should be one connected component into two.
- Fix: canonicalize labels to ids before any
unioncall; skip a union whenfind(a) == find(b)already (this is also just good practice for path compression); with path compression and union by rank, redundant unions from parallel edges cost only a few extrafindcalls, not a correctness problem.
Topological sort.
- Pitfall: a self-loop or any cycle makes a valid topological order impossible to produce, and an implementation that does not check for this can either infinite-loop or silently return a partial, wrong order.
- Pitfall: parallel edges inflate a node's in-degree count in Kahn's algorithm; if the algorithm decrements in-degree once per edge (correct) but the caller expected in-degree to reflect the number of DISTINCT predecessors (a different definition), results diverge from expectations even though the algorithm itself is correct.
- Fix: run cycle detection first (or let Kahn's algorithm detect it implicitly: if fewer than V nodes are output, a cycle exists) and fail with a clear error naming the graph as invalid rather than returning a partial order silently; be explicit about which in-degree definition (edge count vs. distinct-predecessor count) the implementation uses.
Worked example
A small ingestion pipeline for a dependency graph: raw edges arrive as [(A,B), (A,B), (B,B), (B,C), (D,D)], where node A has two labels ("A" and "A_alias") elsewhere in the source data.
Canonicalization step: map "A_alias" -> "A". Then classify: (A,B) appears twice (parallel edge, policy: collapse), (B,B) and (D,D) are self-loops (policy: drop for BFS/DFS/topo-sort; reject if these were meant to carry negative Dijkstra weights), (B,C) is a normal edge, and D otherwise has no other edges (it is effectively isolated once its self-loop is dropped, so it must still appear in the node set with an empty adjacency list).
After sanitization, the canonical graph is: nodes {A, B, C, D}, edges {A->B, B->C}, D isolated. A topological sort on this is well-defined: A, B, C, D (D can appear anywhere, it has no dependencies). Running the same sort on the RAW, unsanitized edge list would either double-process the A->B edge (wasted, not wrong) or, worse, if (B,B) were left in, a naive cycle-unaware implementation could report the whole graph as cyclic when it is not, since the self-loop alone is technically a cycle even though it does not affect ordering between A, B, C, D.
Trade-offs and pitfalls
- Fail fast and specifically: a Dijkstra call that silently ignores a negative edge weight instead of rejecting the input produces a confidently wrong shortest-path answer, which is worse than an error, since nothing downstream will notice.
- Make the collapse-vs-keep-parallel-edges policy configurable rather than hardcoded, since the correct choice depends on what the edges represent (multiple communication channels between two services are meaningfully different from a single duplicated log entry).
- Add tests that specifically exercise self-loops, parallel edges, isolated nodes, and multi-label collisions; these are exactly the inputs that a generated test graph (typically simple, well-formed, connected) will never happen to include on its own, so they need to be constructed deliberately.
- Log sanitization metrics (how many labels were merged, how many parallel edges were collapsed, how many self-loops were dropped) so a spike in any of them signals an upstream data quality problem rather than silently degrading algorithm output.
Implement an iterative DFS in Python to check whether there exists a path between two nodes in a directed graph. Use early exit to improve performance, handle missing nodes gracefully, and discuss stack size and worst-case complexity.
Sample Answer
Direct answer
Use an explicit stack and a visited set; check whether the popped node is the target BEFORE checking or updating visited state, so the function can return True the instant the target is discovered rather than waiting to fully process it. This early exit is the main performance lever over a full traversal, since for many queries the target is found long before the rest of the graph would have been explored.
Structured elaboration
Path existence between two nodes only needs a yes/no answer, so nothing about a full traversal's bookkeeping (discovery order, per-node results) is required. The traversal can stop the instant the target is popped from the stack, rather than finishing whatever level or subtree it happens to be in. A visited set still guards against revisiting nodes on graphs with cycles, exactly as in any other DFS, but the check for "is this the target" happens first, ahead of the visited check, so that even a target reachable through a cycle is caught immediately rather than only after normal traversal bookkeeping would have gotten to it.
Worked example
def has_path_iterative_dfs(graph, start, target):
if start not in graph and start != target:
return False
if start == target:
return True
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node == target:
return True
if node in visited:
continue
visited.add(node)
for nbr in graph.get(node, []):
if nbr not in visited:
stack.append(nbr)
return False
if __name__ == "__main__":
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["D"],
"D": ["A"], # cycle back to A
"E": ["F"], # separate component, unreachable from A
"F": [],
}
print("A -> D reachable:", has_path_iterative_dfs(graph, "A", "D"))
print("A -> E reachable (different component):", has_path_iterative_dfs(graph, "A", "E"))
print("A -> A trivial (same node):", has_path_iterative_dfs(graph, "A", "A"))
print("Z -> A, Z missing from graph:", has_path_iterative_dfs(graph, "Z", "A"))
# Early-exit proof: on a long chain, reaching the immediate neighbor of start
# should not require expanding the rest of a huge unrelated subgraph.
chain = {i: [i + 1] for i in range(100000)}
print("Long chain of 100000 nodes, 0 -> 1 found:", has_path_iterative_dfs(chain, 0, 1))
Output (actually executed with python3):
A -> D reachable: True
A -> E reachable (different component): False
A -> A trivial (same node): True
Z -> A, Z missing from graph: False
Long chain of 100000 nodes, 0 -> 1 found: True
Complexity
- Worst case (target unreachable, or reachable only after exploring most of the graph): time O(V+E), each node and edge examined at most once.
- Best case (target adjacent to
startor found early): far less than a full traversal, the early exit on thenode == targetcheck returns as soon as the target is popped. - Space: O(V) for the visited set; stack size in the worst case also O(V), bounded by the longest unexplored path currently pending.
Edge cases
start == target: handled explicitly up front, returnsTrueimmediately without touching the graph at all.startmissing from the graph entirely (not even a value somewhere): returnsFalseimmediately rather than attempting a lookup that would find nothing anyway.- Empty graph: no nodes to explore, returns
Falseunlessstart == targetwas already caught above. - Very long chains: the early-exit test above uses a 100,000-node chain and confirms an immediate neighbor is found without materializing or fully walking the rest of the chain.
Trade-offs and pitfalls
- Common mistake: checking
node in visitedbefore checkingnode == target; if the target itself somehow ends up added tovisitedon an earlier pass through the loop (for instance, if the visited check were structured differently), the function could miss reporting it as found, ordering the target check first avoids this entirely. - This function only answers existence, not the path itself. If the ACTUAL path is needed, track a parent-pointer map alongside the stack (
came_from[neighbor] = nodeat push time) and reconstruct by walkingcame_frombackward from the target once found. - For REPEATED path-existence queries between many different pairs on the same static graph, computing connected components once (via a single traversal or union-find) and then answering each query as an O(1) "same component" check is far cheaper than re-running a fresh DFS per query.
Implement clone (deep copy) of an undirected graph given a reference to a node. The graph may contain cycles. Provide both BFS and DFS approaches and explain how you ensure node identity mapping and avoid infinite loops.
Sample Answer
Direct answer
Deep-cloning a graph with cycles requires a map from each original node to its clone, created the first time that node is encountered, so that any later edge pointing back to an already-cloned node reuses the existing clone instead of recursing or looping into it again. Both breadth-first search (BFS) and depth-first search (DFS) work; the map is what actually prevents infinite loops on a cycle, not the choice of traversal order.
Structured elaboration
The core invariant both approaches maintain is: a node is added to the clone map exactly once, the first time it is seen, before its neighbors are processed. In the BFS version, a node is cloned when it is first discovered (dequeued or about to be enqueued) and its edges are wired up as its neighbors are visited. In the recursive DFS version, the clone must be created and stored in the map BEFORE recursing into that node's neighbors, otherwise a cycle back to the current node would trigger another recursive call before the map has a place to short-circuit into, causing infinite recursion.
Worked example
from collections import deque
class Node:
def __init__(self, val, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def clone_graph_bfs(node):
if not node:
return None
clones = {node: Node(node.val)}
q = deque([node])
while q:
cur = q.popleft()
for nbr in cur.neighbors:
if nbr not in clones:
clones[nbr] = Node(nbr.val)
q.append(nbr)
clones[cur].neighbors.append(clones[nbr])
return clones[node]
def clone_graph_dfs(node, clones=None):
if not node:
return None
if clones is None:
clones = {}
if node in clones:
return clones[node]
clones[node] = Node(node.val)
for nbr in node.neighbors:
clones[node].neighbors.append(clone_graph_dfs(nbr, clones))
return clones[node]
def build_cyclic_triangle():
# 1 -- 2 -- 3 -- 1, an undirected triangle, a genuine 3-cycle
n1, n2, n3 = Node(1), Node(2), Node(3)
n1.neighbors = [n2, n3]
n2.neighbors = [n1, n3]
n3.neighbors = [n1, n2]
return n1
def graph_signature(start):
'''BFS the graph and return {val: sorted(neighbor vals)} by value, independent of object identity.'''
seen = {}
q = deque([start])
visited_ids = {id(start)}
while q:
cur = q.popleft()
seen[cur.val] = sorted(n.val for n in cur.neighbors)
for nb in cur.neighbors:
if id(nb) not in visited_ids:
visited_ids.add(id(nb))
q.append(nb)
return seen
if __name__ == "__main__":
original = build_cyclic_triangle()
clone_b = clone_graph_bfs(original)
clone_d = clone_graph_dfs(original)
print("Original signature:", graph_signature(original))
print("BFS clone signature:", graph_signature(clone_b))
print("DFS clone signature:", graph_signature(clone_d))
print("BFS clone structurally identical to original:", graph_signature(clone_b) == graph_signature(original))
print("DFS clone structurally identical to original:", graph_signature(clone_d) == graph_signature(original))
# Prove it's a deep copy, not a reference: mutating the clone must not affect the original
clone_b.val = 999
print("Original node's val unaffected by mutating the BFS clone (proves deep copy, not alias):", original.val == 1)
Output (actually executed with python3):
Original signature: {1: [2, 3], 2: [1, 3], 3: [1, 2]}
BFS clone signature: {1: [2, 3], 2: [1, 3], 3: [1, 2]}
DFS clone signature: {1: [2, 3], 2: [1, 3], 3: [1, 2]}
BFS clone structurally identical to original: True
DFS clone structurally identical to original: True
Original node's val unaffected by mutating the BFS clone (proves deep copy, not alias): True
Complexity
- Both BFS and DFS: time O(V+E), each node cloned once, each edge wired once.
- Space: O(V) for the clone map, plus O(V) for the BFS queue or the DFS recursion stack in the worst case (a long chain).
Edge cases
nodeisNone: both functions returnNoneimmediately, no traversal attempted.- Disconnected components: only the component reachable from the given starting node is cloned, since neither traversal has any way to discover a component it cannot reach, this matches the problem's own framing (clone starting from a single reference node).
- Self-loops: a node listing itself as a neighbor is handled correctly, the map check (
if nbr not in clones) treats "myself" the same as any other neighbor once it has been added to the map.
Trade-offs and pitfalls
- BFS versus DFS here is a memory-shape choice, not a correctness choice. DFS's recursion depth equals the longest simple path in the graph, which risks a stack overflow on deep or adversarially long graphs; BFS's queue depth is bounded by the width of the widest frontier instead. For graphs that might be very deep (a long chain-like dependency structure), prefer BFS or an iterative DFS with an explicit stack.
- Common mistake: checking
if nbr not in clonesin the DFS version but creating the clone AFTER recursing into the neighbor instead of before; this defeats the entire cycle guard and reintroduces infinite recursion on any cycle. - Common mistake: cloning
neighborsby reference (new_node.neighbors = old_node.neighbors) instead of building a fresh list of cloned neighbor references; this produces a shallow copy that still points at the ORIGINAL nodes, silently failing the "deep copy" requirement while still returning without error.
Explain the formal differences between a tree and a general graph. Describe properties that define a tree (connected, acyclic, exactly n-1 edges for n nodes), implications such as unique simple path between nodes, and how those properties simplify algorithms (e.g., no need for visited set in some traversals). Give concrete examples of when you'd model a problem as a tree versus as a general graph.
Sample Answer
Direct answer
A tree is a special case of a graph: connected, acyclic, and with exactly n−1 edges for n nodes. Those three properties are not independent facts to memorize separately, any two of them imply the third for a graph on n nodes (connected and acyclic implies exactly n−1 edges; connected with n−1 edges implies acyclic; acyclic with n−1 edges implies connected). The single most useful consequence is that a tree has EXACTLY ONE simple path between any two nodes, which is what lets several algorithms drop bookkeeping that a general graph requires.
Structured elaboration
The defining properties.
- Connected: every node is reachable from every other node.
- Acyclic: no sequence of edges returns to a starting node without repeating an edge.
- Exactly n−1 edges: the minimum number of edges that can connect n nodes (fewer would leave the graph disconnected), and simultaneously the maximum a connected graph can have before a cycle becomes unavoidable.
Why unique simple paths follow. If two different simple paths existed between the same pair of nodes u and v, combining them (going from u to v along one path and back along the other) would trace out a cycle, since the two paths, taken together, revisit u without repeating any single edge twice. This contradicts acyclicity, so at most one simple path can exist; connectivity guarantees at least one exists; together, exactly one.
How this simplifies algorithms. A general graph traversal (breadth-first search (BFS) or depth-first search (DFS)) needs a visited set specifically to avoid two things a tree traversal never has to worry about: re-processing a node reached by more than one route (impossible in a tree, since only one route exists), and looping forever around a cycle (impossible, since there are none). A tree traversal from a chosen root still benefits from tracking "the parent I came from" to avoid immediately walking back the edge just traversed, but that is a much lighter requirement than a full visited set, since it only needs to exclude one specific neighbor (the parent), not remember an arbitrarily large set of everywhere already visited. This is also why tree algorithms can often be written as a clean recursive function of "process this node, then recurse into every neighbor except the parent," with no separate visited-tracking data structure at all.
Worked example
Model as a tree: an organizational reporting hierarchy (each employee has exactly one manager, forming a rooted tree), a filesystem directory structure (each file or folder has exactly one parent directory, ignoring symbolic links), or a binary decision tree used for classification (each internal node has exactly one path down from the root). In each case, "does A report (transitively) to B" or "what is the path from the root to this file" has exactly one answer, and that answer can be found by walking up parent pointers without ever needing to consider an alternative route.
Model as a general graph: a social network (a person can be connected to many others through multiple independent paths, and cycles like mutual-friend triangles are common and meaningful), a service-dependency graph (multiple services may all depend on a shared cache, creating multiple paths between two other services through it), or a road network (there are almost always multiple ways to get from one intersection to another). Forcing any of these into a tree structure would either lose real information (dropping legitimate alternate paths) or require artificially picking one "true" parent per node, discarding the graph's actual shape.
A concrete boundary case worth naming: a graph can look tree-like in casual description ("each task depends on its predecessor") while actually being a directed acyclic graph (DAG), not a tree, the moment a task has more than one direct dependency (two edges pointing INTO the same node). A DAG is still acyclic, but multiple parents mean it is not a tree, and it does not get the "exactly one path between any two nodes" guarantee, a build system's dependency graph is the standard example: a shared library can be a prerequisite for many independent components at once, giving that library multiple incoming edges from unrelated parts of the graph.
Trade-offs and pitfalls
- Common mistake: treating "acyclic" and "tree" as synonyms. A DAG is acyclic but can have nodes with multiple parents (multiple incoming edges), which breaks the unique-simple-path property that trees rely on; algorithms that assume tree structure (a plain parent-pointer walk with no visited set) will double-count or infinite-loop-free-but-redundantly-revisit shared nodes in a DAG, even though the DAG has no cycle to get stuck in.
- Common mistake: assuming "connected with no cycles found so far" is the same as "is a tree," without separately checking the edge count. A connected graph with n nodes and MORE than n−1 edges necessarily contains a cycle (by the same counting argument that shows n−1 is the connectivity-preserving maximum), so if a traversal reports "no cycle found" on a graph that was never checked for edge count, that traversal may simply not have reached the cycle-forming edge yet, especially in a partial or early-terminated search.
- Real systems often START as trees and DRIFT into general graphs as requirements grow: an initial single-parent category hierarchy in a product catalog is a tree, but the moment a product needs to belong to two categories at once (multiple parents), the structure is a DAG, and any code written assuming a tree (recursive descent with no cycle guard, path-uniqueness assumptions in a breadcrumb trail) needs to be revisited, not just extended.
- When in doubt about which structure a system actually has, the edge-count check is cheap and decisive: count edges, count nodes, and confirm ∣E∣=∣V∣−1 AND connectivity before relying on any tree-only simplification; skipping this and assuming "it's basically a tree" is a common source of subtle graph-traversal bugs once the data eventually violates the assumption.
Write functions in C++ to convert between adjacency matrix and adjacency list representations for a graph with n nodes labeled 0..n-1. Consider both directed and undirected graphs and explain the time and space complexity of each representation and of the conversion. Provide guidance on when to prefer one representation over the other.
Sample Answer
Direct answer
Converting matrix to list means scanning every cell of the V×V matrix and recording the column indices where an entry is nonzero, an O(V2) operation regardless of how sparse the result is. Converting list to matrix means allocating a zeroed V×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 n2 cells once; each nonzero cell appends a neighbor to the source vertex's list. listToMatrix allocates an n×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(n2) 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(n2) (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(n2) for the allocated matrix (dominates regardless of m).buildBothFromEdgeList: time O(n+m), but still pays O(n2) 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(n2) 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 andadj[1]contains 0):listToMatrixwriting 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
int0/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(n2) scan that
matrixToListwould otherwise require. - Common mistake: converting list to matrix for a graph where n is large and the result will be sparse anyway; the O(n2) 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).
Unlock Full Question Bank
Get access to all Graphs and Graph Algorithms interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.