Skip to content
Data Structures & Algorithms

Graph Theory interview questions and answers

50 questions, 26 with code. About 4 h 10 min to read them all.

By TestLab · Updated

Plan for an interview
50 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

How is a graph defined in graph theory?

A graph is a mathematical structure used to model relationships between objects. It consists of vertices connected by edges, and it may be directed or undirected and weighted or unweighted.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Properties

A graph is commonly written as G = (V, E):

  • Vertices (V): The nodes or objects in the model, such as people, cities, or web pages.

  • Edges (E): Connections between vertices, such as friendships, roads, or hyperlinks.

  • Degree: The number of edges incident to a vertex.

  • Path: A sequence of vertices connected by edges.

  • Cycle: A path that starts and ends at the same vertex.

A graph can also be classified by several properties:

  • Undirected graph: Edges have no direction; A—B is equivalent to B—A.

  • Directed graph: Edges have direction; A→B does not imply B→A.

  • Unweighted graph: Every edge has equal cost, so BFS can find the path with the fewest edges.

  • Weighted graph: Each edge has a cost, distance, capacity, or other numeric value.

  • Simple graph: There are no self-loops, and each pair of vertices has at most one edge.

  • Multigraph: Multiple edges may connect the same pair of vertices.

The examples below use an undirected, unweighted graph represented by an adjacency list.

Common Representations

Representation Structure Space including the graph Main trade-off
Adjacency list dict[node, list[neighbor]] O(V + E) Efficient for sparse graphs
Adjacency matrix matrix[u][v] O(V²) Constant-time edge lookup but wasteful for sparse graphs
Edge list List of (u, v) pairs O(V + E) Compact, but traversals usually require building an adjacency list

An undirected adjacency list stores each edge twice, once in each endpoint’s neighbor list, but its asymptotic space remains O(V + E). A directed adjacency list stores each edge once and also uses O(V + E) space.

Typical Graph Algorithms

Algorithm Precondition Best, average and worst time Auxiliary space
BFS Works on weighted and unweighted graphs O(V + E) O(V) for the queue and visited set
DFS Works on directed and undirected graphs O(V + E) O(V) for the stack, visited set, and recursion stack
Dijkstra Edge weights must be non-negative O((V + E) log V) with a binary heap O(E) for a lazy priority queue
Bellman–Ford Can handle negative edge weights O(V × E) O(V) for distance values
Topological sort The directed graph must be a DAG O(V + E) O(V) for indegrees, the queue, and ordering
Floyd–Warshall Suitable for relatively small dense graphs O(V³) O(V²) for the distance matrix

These bounds assume an adjacency-list representation. Including the stored graph, BFS and DFS use O(V + E) total space; Dijkstra and Bellman–Ford use O(V + E) total space.

Example Traversal

Consider the undirected edges:

A—B, B—C, B—D, D—E

A breadth-first traversal starting at A produces:

Step Visited vertices Queue after processing
1 A B
2 A, B C, D
3 A, B, C D
4 A, B, C, D E
5 A, B, C, D, E Empty

BFS discovers vertices in increasing distance from the starting vertex. The shortest path from A to E is A—B—D—E, containing three edges.

Common Pitfalls

  • Confusing V and E: V is the number of vertices, while E is the number of edges.

  • Ignoring disconnected graphs: Traversal algorithms must start another search from every unvisited vertex.

  • Forgetting the visited set: A visited set prevents repeated processing and infinite recursion in cyclic graphs.

  • Misusing cycle detection: Undirected graphs need parent tracking or union-find; directed graphs use three-color DFS or a recursion stack.

  • Ignoring direction and weights: An undirected shortest path is not necessarily valid in a directed graph, and Dijkstra is invalid with negative edge weights.

  • Recursion depth: Recursive DFS can exceed Python’s default recursion limit on large graphs; an iterative stack is safer.

2

How are common graph types and categories defined?

Graph categories classify a graph by properties such as edge direction, weights, connectivity, cycles, and structure. These classifications are not mutually exclusive: a graph can simultaneously be directed, weighted, acyclic, sparse, and bipartite.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model and Representations

A graph consists of vertices (nodes) and edges connecting them. Let (V) be the number of vertices and (E) the number of edges.

Representation Structure Total space, including input Common operations
Adjacency list dict[node, list] (O(V + E)) Traversal (O(V + E)); edge lookup (O(deg(v)))
Adjacency matrix Two-dimensional array (O(V^2)) Edge lookup (O(1)); traversal (O(V^2))
Edge list List of (source, target) pairs (O(V + E)) Traversal (O(V + E)); edge lookup (O(E))

Adjacency lists are preferred for sparse graphs. Matrices can be useful when edge lookups must be constant-time or when the graph is dense.

Direction and Weight Categories

  • Directed graph: Edges, called arcs, have a source and destination. A directed path must follow the arc direction.

  • Undirected graph: Edges have no direction and can be traversed in either direction.

  • Weighted graph: Each edge has a numeric cost, distance, capacity, or time.

  • Unweighted graph: Every edge has equal cost, so the minimum number of edges determines shortest-path distance.

  • Mixed graph: Contains both directed and undirected edges; this is less common in standard algorithm problems.

  • Multigraph: Allows multiple edges between the same pair of vertices.

  • Simple graph: Has no self-loops and at most one edge between any pair of vertices.

For an adjacency-list traversal, time is (O(V + E)) because every vertex and edge is processed a constant number of times.

Structural Categories

Category Definition Typical implication
Connected graph Every pair of vertices has a path between them All vertices belong to one connected component
Disconnected graph Contains multiple connected components Algorithms must start from every unvisited vertex
Cyclic graph Contains at least one cycle Cycle-dependent behavior must be handled
Acyclic graph Contains no cycles Often easier to reason about recursively
Tree Connected, undirected, and acyclic Exactly (V-1) edges
DAG Directed and acyclic Supports a topological ordering
Bipartite graph Vertices can be divided into two sets with no edges inside either set Every cycle has even length
Complete graph Every pair of distinct vertices is connected Usually represented by a matrix because it has (Theta(V^2)) edges
Planar graph Can be drawn without edge crossings Used in network-layout and geographic problems
Sparse graph Has (O(V)) edges Usually best represented by an adjacency list
Dense graph Has (Theta(V^2)) edges Often benefits from an adjacency matrix

A DAG is a specific directed graph, not a general replacement for “acyclic,” because an undirected tree is also acyclic but is not a DAG.

Representative Algorithm Complexities

Auxiliary space below excludes the input graph but includes data structures such as queues, heaps, and recursion stacks.

Algorithm Precondition Time Auxiliary space Reason
BFS/DFS Any directed or undirected graph (O(V + E)) (O(V)) Tracks visited vertices; DFS recursion stack may also reach (O(V))
Topological sort DAG (O(V + E)) (O(V)) Maintains in-degree information and a queue
Dijkstra Non-negative edge weights (O((V + E)log V)) (O(V + E)) with a duplicate-entry binary heap Relaxes edges and updates heap priorities
Bellman-Ford Detects negative-weight cycles (O(VE)) (O(V)) Relaxes every edge up to (V-1) times
Kruskal Undirected weighted graph (O(Elog E)) (O(V)) Sorts edges and maintains union-find components
Prim Undirected weighted graph (O(Elog V)) (O(V)) Maintains a priority queue of frontier edges
Floyd-Warshall Usually directed weighted graph (O(V^3)) (O(V^2)) Considers every intermediate vertex

These bounds are worst-case bounds and do not normally differ between best, average, and worst cases. An adjacency-list edge lookup is (O(1)) average when using a set but (O(deg(v))) with a list.

Interview Tips

  • Always identify whether a graph is directed or undirected and weighted or unweighted.

  • Use a visited set or equivalent state to avoid repeatedly processing cycles.

  • Handle disconnected graphs by starting a traversal from every unvisited vertex.

  • Treat a DAG as a directed graph; topological sorting does not apply to a general undirected graph.

  • Dijkstra is invalid for negative edge weights; use Bellman-Ford when negative edges or negative-cycle detection are required.

  • Clarify whether space complexity excludes the input representation and whether a recursive DFS stack is included.

3

What distinguishes a tree from a graph?

A tree is a specialized type of graph that is connected and acyclic, meaning there is exactly one path between any two nodes. A graph is a more general structure consisting of vertices (nodes) and edges that can form cycles, be disconnected, and have arbitrary connections.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definitions

  • Tree: A connected, undirected, acyclic graph. It has a hierarchical structure with a designated root node (in rooted trees) and parent-child relationships. Every tree with (V) nodes has exactly (V-1) edges.

  • Graph: A collection of vertices (V) and edges (E) where edges can connect any pair of vertices. Graphs can be directed or undirected, weighted or unweighted, cyclic or acyclic, connected or disconnected.

Key Differences

Property Tree Graph
Cycles None (acyclic) Allowed (cyclic or acyclic)
Connectivity Always connected Can be disconnected
Edges Exactly (V-1) (0) to (V(V-1)/2) (undirected) or (V^2) (directed)
Path uniqueness Exactly one path between any two nodes Zero, one, or multiple paths
Hierarchy Implicit (root, parent, child, leaf) None unless imposed
Root node Usually designated (rooted tree) No inherent root
Traversal Pre-order, in-order, post-order, level-order BFS, DFS, topological sort (DAGs)
Common representations Adjacency list, parent array, nested objects Adjacency list, adjacency matrix, edge list

When to Use Which

  • Use a tree when data has a natural hierarchy (file systems, DOM, organization charts), when you need fast search/insert/delete with ordering (binary search trees, heaps), or when the problem guarantees no cycles (e.g., decision trees, Huffman coding).

  • Use a graph when relationships are arbitrary or many-to-many (social networks, road maps, dependency graphs, web links), when cycles exist (deadlock detection, circuit analysis), or when you need shortest-path, flow, or connectivity algorithms.

Common Pitfalls

  • Assuming all graphs are trees: Forgetting that graphs can be disconnected or contain cycles leads to infinite loops in traversal without a visited set.

  • Treating a tree as a general graph: Applying Dijkstra or Bellman-Ford on a tree is overkill; simple BFS/DFS suffices because edge weights are often uniform or the unique path property holds.

  • Ignoring the root: In rooted trees, algorithms often depend on the root (e.g., lowest common ancestor, subtree queries). Forgetting to pass or identify the root breaks the logic.

  • Edge count confusion: A tree with (V) nodes always has (V-1) edges. If a connected graph has (V) edges, it contains exactly one cycle.

  • Interview follow-up: “How would you check if a given graph is a tree?” → Verify it is connected (one component via BFS/DFS) and has exactly (V-1) edges (or no cycles during traversal with parent tracking).

4

What is the minimum number of edges for a connected graph?

For a connected undirected graph with V >= 1 vertices, the minimum number of edges is V - 1. This bound is achieved by a tree, and it is independent of whether the edges are weighted.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Type

  • The default interpretation is an undirected graph, whether weighted or unweighted.

  • For a directed graph, connectivity must be specified as weak connectivity or strong connectivity.

  • A representation such as an adjacency list is assumed when discussing standard traversal complexity.

Why the Minimum Is V - 1

  1. Start with one vertex.

  2. Each new edge can connect at most one additional vertex to the already reachable set.

  3. Reaching all V vertices therefore requires at least V - 1 edges.

  4. A tree has exactly V - 1 edges and is connected, so the lower bound is achievable.

An undirected graph with exactly V - 1 edges is a tree exactly when it is connected. Edge count alone does not guarantee connectivity: a graph can have V - 1 edges while being disconnected and containing a cycle elsewhere.

For directed graphs:

  • Weak connectivity requires the underlying undirected graph to be connected, so the minimum is also V - 1.

  • Strong connectivity requires every vertex to reach every other vertex. For V >= 2, at least V directed edges are necessary, and a directed cycle achieves that bound.

  • For V = 1, no edges are required.

Representations and Space Costs

Representation Space complexity Notes
Adjacency list O(V + E) Includes the stored graph data
Adjacency matrix O(V^2) Appropriate for dense graphs
Edge list O(E) Add O(V) if a vertex set is stored to represent isolated vertices

These costs include the graph representation itself. Temporary traversal memory is listed separately below.

Checking Connectivity

For an undirected graph represented by an adjacency list, run BFS or DFS from any vertex and check whether all V vertices are visited.

  • Time complexity: O(V + E) because the traversal processes each vertex and edge a constant number of times.

  • Auxiliary space complexity: O(V) for the visited set and BFS queue, or for the visited set and recursive DFS stack, excluding the input graph.

  • An adjacency-matrix traversal takes O(V^2) time.

  • To count all connected components, loop over every vertex and start a new traversal from each unvisited vertex. To test connectivity, one traversal from any vertex is enough.

Common Pitfalls

  • Empty graph (V = 0): the V - 1 formula does not apply; under the usual convention, the empty graph is not connected.

  • Single vertex (V = 1): it is connected with 0 edges.

  • Disconnected graphs: having V - 1 edges alone does not make a graph connected.

  • Cycles: cycles are unnecessary for the minimum edge count.

  • Duplicate or parallel edges: duplicates do not connect new vertices and cannot reduce the minimum.

  • Negative weights and sorted input: neither affects this graph-theoretic bound.

5

What are Euler paths and circuits in graph theory?

An Euler path traverses every edge of a graph exactly once, while an Euler circuit traverses every edge exactly once and returns to its starting vertex. The terms describe the entire edge set, not necessarily every vertex.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Definitions

  • Euler path: A walk that uses every edge exactly once. It may start and end at different vertices.

  • Euler circuit: A closed walk that uses every edge exactly once, so its starting and ending vertices are the same.

  • Some texts use Euler trail as a more precise synonym for Euler path.

  • An Euler circuit is also considered an Euler path in conventions where “path” includes closed walks.

  • Edge weights are irrelevant: weighted and unweighted graphs can both contain Euler paths or circuits.

Graph Types and Existence Conditions

The following conditions assume the graph is finite and that isolated vertices do not need to be traversed.

Graph type Euler path exists when Euler circuit exists when
Undirected Exactly zero or two vertices have odd degree, and all vertices with nonzero degree belong to one connected component Every vertex has even degree, and all vertices with nonzero degree belong to one connected component
Directed Exactly one vertex has outdegree = indegree + 1, exactly one has indegree = outdegree + 1, all others have equal degrees, and all edge-bearing vertices are weakly connected Every vertex has indegree = outdegree, and all edge-bearing vertices belong to one strongly connected component

For an undirected graph:

  • Zero odd-degree vertices imply an Euler circuit.

  • Exactly two odd-degree vertices imply an Euler path that begins at one odd vertex and ends at the other.

  • More than two odd-degree vertices means no Euler path exists.

For a directed graph:

  • The vertex with one extra outgoing edge is the required starting point of an Euler path.

  • The vertex with one extra incoming edge is the required ending point.

  • Euler circuits do not have distinct start and end vertices.

Representation and Complexity

A common representation is an adjacency list:

graph = {
    "A": ["B", "C"],
    "B": ["A", "C"],
    "C": ["A", "B"],
}

This stores each undirected edge twice, so its total space is O(V + E). An adjacency matrix uses O(V²) space regardless of the number of edges.

Checking the existence conditions takes:

  • Time: O(V + E) using an adjacency list, because the algorithm computes degrees and checks connectivity.

  • Auxiliary space: O(V) for degree counts, visited vertices, and traversal stacks or queues, excluding the input graph.

  • Total space including input: O(V + E) for an adjacency list.

  • With an adjacency matrix, the corresponding time and space are O(V²).

For directed graphs, checking strong connectivity can use DFS on the graph and its transpose, also taking O(V + E) time and O(V) auxiliary space.

Small Example

Consider the undirected graph with edges:

A-B, B-C, C-A, A-D

Its vertex degrees are:

Vertex Degree
A 3
B 2
C 2
D 1

There are exactly two odd-degree vertices, A and D, so the graph has an Euler path but no Euler circuit. One valid traversal is:

  1. Start at A.

  2. Traverse A-B.

  3. Traverse B-C.

  4. Traverse C-A.

  5. Traverse A-D.

Every edge is used exactly once. The traversal starts at A and ends at D, so it is not an Euler circuit.

Common Pitfalls

  • Do not confuse an Euler path with a Hamiltonian path: Euler concerns traversing every edge exactly once, while Hamiltonian concerns visiting every vertex exactly once.

  • Connectivity must account for isolated vertices. They do not prevent an Euler path or circuit in the component containing the edges.

  • For directed graphs, “connected” means strongly connected for an Euler circuit and weakly connected for the stated Euler-path condition.

  • In an undirected graph, remember to count every edge in both endpoint degrees.

  • A visited set is required when checking connectivity or reconstructing a traversal; otherwise cycles cause repeated processing.

  • Interviewers commonly ask for the degree-based conditions, the difference between an Euler path and a Hamiltonian path, and how to construct the traversal using Hierholzer’s algorithm.

6

What is the difference between adjacency lists and adjacency matrices?

An adjacency list stores each vertex’s neighbors and is usually the better choice for sparse graphs, while an adjacency matrix stores whether—or with what weight—each pair of vertices is connected and is often better for dense graphs. Their main difference is the trade-off between efficient neighbor traversal and efficient edge lookup.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Types and Representations

Both structures can represent:

  • Directed or undirected graphs

  • Weighted or unweighted graphs

  • Disconnected graphs, including isolated vertices when the vertex set is retained separately

For a graph with (V) vertices and (E) edges:

  • Adjacency list: dict[node, list]

  • A directed graph normally stores each edge once.

  • An undirected graph normally stores each edge twice.

  • Weighted edges can be stored as tuples such as (neighbor, weight).

  • Adjacency matrix: a (V times V) matrix

  • An unweighted matrix usually uses a boolean or a special “no edge” value.

  • A weighted matrix stores the edge weight, using a sentinel such as None when no edge exists.

  • For an undirected graph, entries ((u,v)) and ((v,u)) represent the same edge.

Complexity Comparison

The following complexities describe individual operations and assume direct vertex access is (O(1)) on average. For the shown list-valued adjacency dictionary, finding a neighbor requires scanning a list.

Operation Adjacency List Adjacency Matrix
Check whether edge ((u,v)) exists Best (O(1)), average (O(text{degree}(u))), worst (O(V)) (O(1))
Add an edge (O(1)) amortized for list append; an individual list resize can take (O(V)) (O(1))
Remove an edge Directed list: (O(text{degree}(u))); undirected list: (O(text{degree}(u)+text{degree}(v))), worst (O(V)) (O(1))
Access all neighbors of u (O(text{degree}(u))) (O(V))
Traverse the entire graph (O(V + E)) (O(V^2))
Add a vertex (O(1)) average and amortized for the outer dictionary (O(V^2)) when the matrix is expanded by copying
Enumerate all vertices (O(V)) (O(V)), if a separate vertex list exists

If each neighbor collection is itself a hash-based dictionary, edge lookup and deletion are (O(1)) on average and (O(V)) in the worst case because of hash collisions. Python list operations instead require scanning or shifting elements.

Space Complexity

  • Adjacency list: (O(V + E)) storage

  • The input graph representation itself is counted.

  • Directed graphs contain approximately (E) stored entries; undirected graphs contain approximately (2E).

  • An additional traversal typically requires (O(V)) space for a visited set and stack or queue.

  • Adjacency matrix: (O(V^2)) storage

  • The input matrix itself is counted.

  • Traversal requires an additional (O(V)) visited set and stack or queue.

Neither representation requires recursion, so there is no recursion-stack cost. An iterative traversal is preferable for graphs with more than roughly 1,000 vertices because a recursive implementation could exceed Python’s default recursion limit.

Practical Trade-offs

Consideration Adjacency List Adjacency Matrix
Sparse graph Usually more space-efficient Can waste most of the matrix
Dense graph More memory per stored edge Often more space-efficient
Edge lookup Depends on degree and collection type Constant-time lookup
Neighbor traversal Iterates only actual neighbors Scans an entire matrix row
Weighted graphs Stores weight beside each neighbor Naturally associates a weight with each pair
Duplicate edges Lists can retain them; sets can remove them A matrix stores only one value per pair

For example, a social network with millions of users but relatively few connections is usually sparse, making an adjacency list appropriate. A road graph with many connections between every district may be dense enough for an adjacency matrix to be reasonable.

Common Pitfalls and Interview Tips

  • Do not confuse (O(V+E)) with (O(V^2)): adjacency-list traversal visits only actual edges, while matrix traversal examines every possible vertex pair.

  • In an undirected graph, adding edge ((u,v)) normally updates both adjacency[u] and adjacency[v]; removing it normally removes both entries.

  • A complete (V times V) matrix has a row for every vertex, but retain a separate vertex list or index map so isolated vertices can still be enumerated.

  • Use a sentinel rather than numeric zero to distinguish “no edge” from a valid edge of weight zero.

  • Empty graphs and single-vertex graphs are valid. Decide whether duplicate or parallel edges are meaningful; a basic matrix cannot preserve them without additional data.

  • Negative edge weights can be stored structurally, but the choice of shortest-path algorithm depends on whether negative weights or negative cycles are possible.

  • Both representations can contain cycles. During traversal, always use a visited set and loop over every vertex so disconnected components are included.

  • A common follow-up is: “Which representation supports Dijkstra’s algorithm more efficiently?” The adjacency list is usually preferred because it avoids scanning every possible neighbor of each vertex.

7

What is an incidence matrix, and when is it used?

An incidence matrix is a rectangular binary or signed matrix describing which vertices are endpoints of each edge. It is useful when graph relationships must be expressed through matrix operations, particularly for cycle analysis, network flows, and other linear-algebraic problems.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Type and Representation

Consider a graph (G=(V,E)):

  • Undirected graph: Each column represents an edge, with 1 in the rows of its two endpoints.

  • Directed graph: Each column represents a directed edge, usually with 1 at the tail and -1 at the head. Some conventions reverse these signs.

  • Weighted graph: The incidence matrix records connectivity only. Edge weights are stored separately or in an augmented matrix.

For (V) vertices and (E) edges, the matrix has:

  • Rows: vertices, indexed from (0) to (V-1)

  • Columns: edges, indexed from (0) to (E-1)

  • Dimensions: (V times E)

For example, an undirected graph with edges (a, b), (b, c), and (a, c) has this incidence matrix:

Vertex (a,b) (b,c) (a,c)
a 1 0 1
b 1 1 0
c 0 1 1

A column therefore answers: “Which vertices are incident to this edge?”

When It Is Used

An incidence matrix is most useful when the problem naturally involves linear algebra:

  • Cycle-space analysis: For a connected undirected graph, the dimension of the cycle space is (E-V+1). Basis cycles can be derived using matrix nullspace techniques.

  • Network flow and electrical networks: A reduced incidence matrix describes how edges contribute to vertex balances. For example, Kirchhoff’s current law can be represented using matrix equations.

  • Graph algorithms and spectral methods: Incidence matrices support operations involving edge flows, graph Laplacians, and signal propagation.

  • Incidence-based linear algebra: Multiplying an incidence matrix by a vector of edge values can compute the net contribution arriving at each vertex.

  • Educational and theoretical settings: The matrix makes graph topology explicit for proofs, derivations, and algorithm analysis.

It is usually not the best representation for ordinary graph search, shortest paths, or connectivity queries because an adjacency list is more compact for sparse graphs.

Complexity

For a graph with (V) vertices and (E) edges:

Operation Time complexity Reason
Access one matrix entry (O(1)) Direct row and column indexing
Construct a dense matrix from an edge list (O(VE)) Allocating the matrix dominates; filling entries takes (O(E))
Multiply by a dense edge vector (O(VE)) Potentially examines every matrix entry
Compute vertex degree sums (O(VE)) Naively sums every matrix column for each vertex

The bounds are deterministic, so best, average, and worst cases are the same.

  • Space complexity: (O(VE)) for the matrix, commonly (O(V(E+1))) to include the empty-edge case.

  • Input accounting: The original adjacency list or edge list uses (O(V+E)) space and is not counted in the matrix-space figure.

  • Recursion stack: No recursion stack is used.

Representation Comparison

Representation Space Main advantage Typical use
Adjacency list (O(V+E)) Compact for sparse graphs BFS, DFS, shortest paths
Adjacency matrix (O(V^2)) Constant-time edge lookup Dense graphs and matrix algorithms
Incidence matrix (O(VE)) Direct vertex-edge algebra Flows, cycles, network analysis

For a dense graph where (E=O(V^2)), an incidence matrix uses (O(V^3)) space, so it is substantially larger than an adjacency matrix.

Common Pitfalls

  • Confusing dimensions: An ordinary graph incidence matrix is (V times E), not (E times V).

  • Ignoring orientation: Directed matrices require a consistent sign convention for edge direction.

  • Assuming weights are included: A standard incidence matrix records incidence, not edge cost.

  • Using it for sparse traversal: An adjacency list is usually faster and smaller for BFS, DFS, and connectivity.

  • Forgetting disconnected graphs: Algebraic statements such as (E-V+1) generally assume a connected undirected graph; otherwise component structure must also be considered.

8

What is an edge list in graph algorithms?

An edge list represents a graph as a collection of edges rather than storing adjacency information for each vertex. It is especially useful for sparse graphs and algorithms that process edges globally, such as Kruskal’s algorithm and Bellman–Ford.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Representation

An edge list can describe directed or undirected graphs and weighted or unweighted graphs:

  • Unweighted undirected: (u, v) represents one undirected connection.

  • Unweighted directed: (u, v) represents an edge from u to v.

  • Weighted: (u, v, weight) also stores a cost.

For example, the weighted undirected graph with vertices {A, B, C, D} could use the edge list [(A, B, 4), (B, C, 3), (A, C, 2)]. An edge-only list cannot represent isolated vertices, so a separate collection of vertices is often maintained. Identifiers may be integers, strings, or other objects, although objects used as dictionary or set keys must be hashable.

Storage and Alternatives

Let V be the number of vertices and E the number of edges.

Representation Shape Total space Known-pair lookup Neighbor access
Edge list list[(u, v)] or list[(u, v, weight)] O(V + E) including vertices O(E) by scanning O(E) by scanning
Adjacency list dict[node, list] O(V + E) O(degree(u)) O(degree(u))
Adjacency matrix matrix[V][V] O(V²) O(1) O(V)

A set-valued adjacency list can provide expected O(1) known-pair lookup, but a standard list-valued adjacency list requires scanning one endpoint’s neighbor list. For a dense graph, an adjacency matrix and an edge list both have O(V²) asymptotic storage, although their constant factors can differ.

Complexity

Unless otherwise stated, the bounds below are the same in the best, average, and worst cases.

  • Stored graph: O(V + E) total space when the separate vertex collection is included; the edges alone require O(E).

  • Building from edge data: O(E) time if identifiers are already valid and no vertex collection is built; using a hash set takes expected O(V + E) time and O(V) additional space.

  • Scanning all edges: O(E) time because every edge must be examined.

  • Finding one edge by scanning: O(1) best case if it is first, and O(E) average and worst case; an absent edge also requires O(E) time.

  • Retrieving one adjacency list: expected O(1) time with a general O(V) worst-case hash-table bound and no additional asymptotic space.

  • BFS or DFS with an existing adjacency list: O(V + E) time and O(V) auxiliary space, including the visited set and queue or recursion stack. The input adjacency list is excluded from auxiliary space.

  • Building an adjacency list before traversal: the conversion requires an additional O(V + E) workspace; total storage including the original edge list is still O(V + E).

Use Cases

  • Kruskal’s minimum spanning forest: Applicable to undirected weighted graphs, including disconnected graphs. Sorting and processing edges takes O(E log E) time; including O(V) union-find initialization gives O(V + E log E) overall. Auxiliary space is O(V + E) because of union-find and the sorted copy of the edges.

  • Bellman–Ford: Applicable to weighted directed or undirected graphs and supports negative edge weights. It takes O(V × E) time and O(V) auxiliary space for distances and optional predecessors. It can detect negative cycles reachable from the source.

  • Dijkstra: Requires non-negative edge weights and normally uses an adjacency list built from the edge list. It takes O((V + E) log V) time and O(V + E) space including the conversion, distances, visited state, and heap.

  • Topological sorting: Applicable to directed acyclic graphs. Kahn’s algorithm takes O(V + E) time and O(V + E) space including the adjacency list, indegree array, and queue.

  • Filtering and counting: A single scan takes O(E) time. Filtering uses O(1) additional space, while counting degrees may use O(V) space for degree totals.

Example Walkthrough

For edges [(0, 1, 4), (1, 2, 3), (0, 2, 2)], sorting by weight gives:

Edge Components before processing Decision
(0, 2, 2) {0}, {1}, {2} Select
(1, 2, 3) {0, 2}, {1} Select
(0, 1, 4) {0, 1, 2} Skip because it creates a cycle

The resulting spanning tree has total weight 5.

Common Pitfalls

  • Empty graph or single vertex: Preserve the vertex collection; an empty edge list alone cannot distinguish them.

  • Direction semantics: (u, v) means something different in directed and undirected graphs.

  • Duplicates and self-loops: They may be valid in a multigraph, but their interpretation must be specified.

  • Negative weights: Edge lists can store them, but algorithms such as Dijkstra require non-negative weights.

  • Already sorted input: It may avoid one sorting step, but an algorithm must not assume that property without being told.

  • Disconnected graphs: Keep isolated vertices and loop over all components when traversal or spanning-forest behavior is required.

  • Cycles: Use a visited set during traversal and a component check in algorithms such as Kruskal.

  • Input mutation: Sort or filter a copy when the caller’s edge list must remain unchanged.

9

How does Compressed Sparse Row save graph storage space?

Compressed Sparse Row (CSR) stores graph adjacency information in compact, contiguous arrays rather than allocating space for every possible vertex pair. It saves the most space for sparse graphs, where the number of edges is much smaller than the number of possible connections.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph and Storage Model

For this explanation, consider a directed, weighted graph initially represented as an adjacency list:

dict[node, list[(neighbor, weight)]]

CSR represents the graph using:

  • row_ptr: A length-V + 1 array. The neighbors of vertex u occupy row_ptr[u]:row_ptr[u + 1].

  • col_indices: The destination vertex of each stored adjacency entry.

  • values: The corresponding edge weight; this array is omitted for an unweighted graph.

For an undirected graph, each logical edge is normally inserted in both directions. Therefore, E below means the number of stored directed adjacency entries, not necessarily the number of logical undirected edges.

Space Savings

Representation Stored information Space
Adjacency matrix A value for every possible vertex pair O(V²)
Edge list Source, destination, and optional weight for each edge O(E)
Adjacency list V lists containing E adjacency entries O(V + E)
CSR V + 1 offsets, E column indices, and optional E weights O(V + E)

CSR avoids allocating entries for absent edges. Thus, when E = O(V), CSR requires O(V) space rather than the O(V²) required by a dense adjacency matrix.

CSR does not improve the asymptotic space of a conventional adjacency list: both require O(V + E) space. However, compact typed arrays can substantially reduce the per-edge object overhead found in languages such as Python. CSR also provides better locality when traversing all neighbors of one vertex.

Example and Access Pattern

Consider the edges 0 → 1, 0 → 2, and 1 → 2:

Vertex Stored neighbors Ending offset
0 1, 2 2
1 2 3
2 None 3

The resulting arrays are:

  • row_ptr = [0, 2, 3, 3]

  • col_indices = [1, 2, 2]

  • values = [2.5, 1.0, 4.0]

To iterate over the neighbors of vertex u, read col_indices from row_ptr[u] up to, but not including, row_ptr[u + 1]. This takes O(deg(u)) time, while obtaining the starting offset takes O(1).

Complexity and Edge Cases

Assuming construction sorts each adjacency row independently with a comparison sort:

  • Best construction time: O(V + E) when an adaptive sort recognizes that every row is already sorted.

  • Average construction time: O(V + Σ deg(u) log(deg(u) + 1)) for randomly ordered rows, bounded by O(V + E log(E + 1)).

  • Worst construction time: O(V + E log(E + 1)).

  • Persistent CSR space: O(V + E), excluding the original input graph.

  • Temporary construction space: O(Δ), where Δ is the maximum degree, when rows are sorted one at a time.

  • Peak space including the input and output: O(V + E).

  • Recursion stack: O(1) for an iterative construction.

An empty graph produces a single zero offset, and a graph with one isolated vertex produces two zero offsets. Disconnected graphs are supported without modification. Duplicate edges may remain as duplicate entries or be aggregated according to defined graph semantics. Negative weights and cycles are valid because CSR imposes no weight or acyclicity restrictions.

Common Pitfalls

  • Incorrect row offsets: Every row must end where the next begins, and the final offset must equal the number of stored adjacency entries.

  • Missing isolated vertices: Omitting an isolated vertex shifts later rows and corrupts neighbor lookups.

  • Confusing edge counts: An undirected edge normally contributes two CSR entries.

  • Unstated duplicate semantics: Decide whether repeated edges remain separate or require aggregated weights.

  • Frequent updates: CSR is efficient for read-heavy workloads, but inserting or deleting entries often requires rebuilding the arrays or maintaining auxiliary data structures.

10

How does Breadth-First Search traversal work on a graph?

Breadth-First Search (BFS) explores a graph layer by layer, visiting all nodes at one distance from the start before processing the next layer. It uses a queue to preserve this order and a visited set to avoid processing cycles or duplicate entries repeatedly.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

BFS traversal can operate on directed or undirected graphs, weighted or unweighted. However, it guarantees a shortest path in number of edges only in an unweighted graph.

The algorithm is:

  1. Create an empty queue, visited set, and result list.

  2. Mark the starting node as visited and enqueue it.

  3. Dequeue a node, append it to the result, and inspect its neighbors.

  4. Mark each unvisited neighbor as visited and enqueue it.

  5. Repeat until the queue is empty.

  6. To traverse disconnected components, start another BFS from every unvisited node in the graph.

Marking a node as visited when it is enqueued is important: it prevents the same node from being added to the queue multiple times before its first dequeue.

Graph Model and Representation

The example below uses a directed, unweighted graph represented as an adjacency list, dict[node, list]. Each key is a source node, and its list contains the node’s outgoing neighbors. For an undirected graph, each edge must appear in both endpoints’ neighbor lists.

Representation Graph Storage Space
Adjacency list O(V + E)
Adjacency matrix O(V²)
Edge list O(V + E)

For an adjacency-list traversal, every adjacency-list entry is examined once. An undirected edge contributes two entries, one for each endpoint.

Complexity

  • Time: O(V + E) in the best, average, and worst cases. Every vertex is enqueued and dequeued once, and every adjacency-list entry is inspected once.

  • Auxiliary space: O(V). The queue, visited set, and result list each store at most O(V) vertices. The recursion stack is O(1) because the implementation is iterative. These costs exclude the O(V + E) input graph; include that storage if total memory is being measured.

Example Walkthrough

For the graph {1: [2, 3], 2: [4], 3: [], 4: []}:

  1. Enqueue 1; the queue becomes [1].

  2. Dequeue 1 and enqueue 2 and 3; the queue becomes [2, 3].

  3. Dequeue 2 and enqueue 4; the queue becomes [3, 4].

  4. Dequeue 3; the queue becomes [4].

  5. Dequeue 4; the queue becomes empty.

The traversal order is [1, 2, 3, 4].

Code Example

from collections import deque


def bfs_traversal(graph: dict[int, list[int]]) -> list[int]:
    """Return the BFS traversal order of all components in the graph."""
    visited: set[int] = set()
    queue: deque[int] = deque()
    result: list[int] = []

    # Start another traversal when a disconnected component is found.
    for start_node in graph:
        if start_node in visited:
            continue

        visited.add(start_node)
        queue.append(start_node)

        while queue:
            node = queue.popleft()
            result.append(node)

            # Missing keys represent vertices without outgoing neighbors.
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

    return result


if __name__ == "__main__":
    example_graph = {1: [2, 3], 2: [4], 3: [], 4: []}
    print(bfs_traversal(example_graph))  # Output: [1, 2, 3, 4]

The code handles an empty graph by returning [], a single-node graph, duplicate neighbors, cycles, and disconnected components. Negative node identifiers work as ordinary dictionary keys. An already sorted adjacency list only changes the order among nodes at the same depth and does not affect correctness or complexity.

Common Pitfalls

  • Forgetting the visited set causes repeated processing and infinite loops on cyclic graphs.

  • Marking nodes as visited when dequeued rather than when enqueued can put duplicates into the queue.

  • Omitting the outer loop misses disconnected components.

  • Using list.pop(0) is O(n); use collections.deque, whose popleft() is O(1).

  • Recursive BFS can exceed Python’s recursion limit for large graphs; the iterative queue implementation avoids that issue.

11

How does Depth-First Search traverse a graph?

Depth-First Search (DFS) explores a graph by following one branch as far as possible before backtracking. It manages pending work with a stack, either explicitly or through recursion.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

DFS supports directed or undirected graphs and weighted or unweighted graphs, although it does not use edge weights to determine traversal order. The example below uses an adjacency list, dict[int, list[int]]; every node appearing as a neighbor must also have a key in the dictionary.

  1. Select an unvisited starting node and mark it as visited.

  2. Examine its next unvisited neighbor.

  3. Mark that neighbor as visited and explore its neighbors before returning to the starting node.

  4. When a node has no remaining unvisited neighbors, backtrack to its predecessor.

  5. Repeat from another unvisited node if the graph is disconnected.

For graph = {0: [1, 2], 1: [3], 2: [3], 3: []}, the traversal proceeds as follows:

  1. Visit 0 and descend to neighbor 1.

  2. From 1, visit 3; it has no neighbors, so backtrack.

  3. Back at 0, visit 2; its neighbor 3 is already visited.

  4. The resulting preorder is [0, 1, 3, 2].

Complexity Analysis

  • Time: For an adjacency list, best, average, and worst case are O(V + E). Each vertex and adjacency-list entry is processed once; an undirected edge appears in both endpoint lists but is still examined only a constant number of times.

  • Auxiliary space: O(V) for the visited set and traversal stack. Including the returned order, the total remains O(V). The input adjacency list is excluded; including it gives O(V + E).

  • A recursive DFS also uses up to O(V) recursion-stack space, but it can exceed Python’s default recursion limit.

Graph Representations

Representation Input Space DFS Time Auxiliary Space Best For
Adjacency list O(V + E) O(V + E) O(V) Sparse graphs
Adjacency matrix O(V²) O(V²) O(V) Dense graphs

Code Example

This iterative implementation preserves recursive DFS ordering while avoiding Python’s recursion limit.

from collections.abc import Iterator


def dfs_traversal(graph: dict[int, list[int]]) -> list[int]:
    """Return the DFS preorder of every node in an adjacency-list graph."""
    visited: set[int] = set()
    order: list[int] = []

    for start in graph:
        if start in visited:
            continue

        visited.add(start)
        order.append(start)

        # Each frame stores a node and its remaining neighbors.
        stack: list[tuple[int, Iterator[int]]] = [
            (start, iter(graph[start]))
        ]

        while stack:
            current, neighbors = stack[-1]

            try:
                neighbor = next(neighbors)
            except StopIteration:
                stack.pop()
                continue

            if neighbor not in visited:
                visited.add(neighbor)
                order.append(neighbor)
                stack.append((neighbor, iter(graph[neighbor])))

    return order


example_graph = {0: [1, 2], 1: [3], 2: [3], 3: []}
print(dfs_traversal(example_graph))  # [0, 1, 3, 2]

Common Pitfalls

  • Forgetting the visited set: Cycles can cause repeated processing or nontermination.

  • Ignoring disconnected components: Iterate over all graph keys and start another traversal when necessary.

  • Recursion depth: Recursive DFS may exceed Python’s default limit; the iterative stack avoids that issue.

  • Edge cases: Empty input returns []; a one-node graph returns that node; duplicate neighbors or edges do not cause duplicate visits; negative integer labels work because labels are not interpreted as weights.

  • Ordering: The adjacency list requires no sorting; traversal follows the order of its neighbor lists.

  • Follow-ups: Topological sorting with DFS requires a DAG. Undirected cycle detection uses parent tracking or union-find, while directed cycle detection uses three colors or a recursion stack.

12

What are the main differences between BFS and DFS?

Breadth-first search (BFS) explores a graph level by level using a queue, while depth-first search (DFS) follows one branch as deeply as possible using a stack or recursion. Both run in O(V + E) time with an adjacency-list representation, but they provide different ordering, path guarantees, and practical use cases.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model and Representation

This answer covers directed or undirected, weighted or unweighted graphs represented by an adjacency list such as dict[node, list[node]].

  • Vertices (V): the number of nodes.

  • Edges (E): the number of connections.

  • Input space: O(V + E) for the adjacency list.

  • Traversal itself does not depend on edge weights. However, BFS finds a shortest path only for an unweighted graph or when all edges have equal cost.

  • With an adjacency matrix, traversal time becomes O(V²), while the matrix occupies O(V²) space.

BFS vs DFS

Aspect BFS DFS
Exploration strategy Explores all vertices at one distance before deeper levels Explores a branch before returning to earlier branches
Main data structure FIFO queue, commonly collections.deque Stack or recursion
Path guarantee Finds a minimum-edge path in unweighted or equal-cost graphs Does not generally guarantee a shortest path
Typical applications Shortest paths, level traversal, bipartite checking, nearest-node searches Cycle detection, connected components, topological sorting, maze exploration
Memory behavior Queue may contain many vertices from the current and next levels Stack depth is generally smaller, but can still reach O(V)
Directed cycle detection Not a natural cycle-detection method Uses three-color states in a directed graph
Undirected cycle detection Possible, but DFS with parent tracking is usually clearer Uses parent tracking or union-find

DFS-based topological sorting requires a directed acyclic graph (DAG). Weighted shortest paths with nonnegative weights are better handled by Dijkstra’s algorithm rather than ordinary BFS or DFS.

How the Traversals Work

BFS removes a vertex from the front of a queue and adds its undiscovered neighbors to the back. DFS removes a vertex from the top of a stack and explores its neighbors before returning to the previous branch.

For this graph:

A: B, C
B: D
C: E
D:
E:
F:

The disconnected component containing F is visited separately.

Step BFS processed and queue afterward DFS processed and stack afterward
1 A; queue [B, C] A; stack [C, B]
2 B; queue [C, D] B; stack [C, D]
3 C; queue [D, E] D; stack [C]
4 D; queue [E] C; stack [E]
5 E; queue [] E; stack []
6 F; queue [] F; stack []

The resulting orders are:

  • BFS: A, B, C, D, E, F

  • DFS: A, B, D, C, E, F

Complexity

Traversal Best time Average time Worst time Auxiliary space
BFS O(V + E) O(V + E) O(V + E) O(V)
DFS O(V + E) O(V + E) O(V + E) O(V)
  • Time reason: Each vertex is visited once, and each adjacency-list entry is examined once. Thus, undirected edges may be inspected from both endpoints, but the total remains O(V + E).

  • Space reason: The visited set and queue or stack contain at most O(V) vertices. This excludes the O(V + E) input graph. Recursive DFS also has an O(V) recursion stack; iterative DFS avoids Python’s default recursion-depth limit.

  • Queue and stack operations take O(1) amortized time, but this does not change the overall traversal complexity.

Code Example

from collections import deque
from collections.abc import Hashable, Mapping, Sequence
from typing import TypeVar

Node = TypeVar("Node", bound=Hashable)


def traversal_orders(
    graph: Mapping[Node, Sequence[Node]],
) -> tuple[list[Node], list[Node]]:
    """Return BFS and DFS orders, including every disconnected component."""

    def bfs_order() -> list[Node]:
        visited: set[Node] = set()
        order: list[Node] = []

        for start in graph:
            if start in visited:
                continue

            visited.add(start)
            queue: deque[Node] = deque([start])

            while queue:
                node = queue.popleft()
                order.append(node)

                for neighbor in graph.get(node, ()):
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)

        return order

    def dfs_order() -> list[Node]:
        visited: set[Node] = set()
        order: list[Node] = []

        for start in graph:
            if start in visited:
                continue

            visited.add(start)
            stack: list[Node] = [start]

            while stack:
                node = stack.pop()
                order.append(node)

                for neighbor in reversed(graph.get(node, ())):
                    if neighbor not in visited:
                        visited.add(neighbor)
                        stack.append(neighbor)

        return order

    return bfs_order(), dfs_order()


graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["E"],
    "D": [],
    "E": [],
    "F": [],
}

bfs, dfs = traversal_orders(graph)
# bfs == ['A', 'B', 'C', 'D', 'E', 'F']
# dfs == ['A', 'B', 'D', 'C', 'E', 'F']

Common Pitfalls

  • Forgetting disconnected components: Start a new traversal from every unvisited vertex.

  • Omitting the visited set: Cycles cause infinite loops, while duplicate edges can cause repeated processing.

  • Assuming DFS finds shortest paths: DFS finds an available path, not necessarily the shortest one.

  • Using BFS for arbitrary weighted paths: Use Dijkstra’s algorithm for nonnegative weighted edges and Bellman-Ford when negative edges may exist.

  • Ignoring edge cases: Empty graphs return empty lists, one-vertex graphs return that vertex, duplicate edges are harmless, and negative weights do not affect traversal order. Input ordering is not required to be sorted.

  • Exceeding recursion limits: Prefer iterative DFS for graphs with paths longer than Python’s default recursion limit of roughly 1,000.

  • Typical follow-up questions: Ask about shortest paths, bipartite graphs, cycle detection, topological sorting, iterative implementations, and time or space optimization.

13

How do I implement a path check between two graph vertices?

A path exists when two vertices belong to the same connected component of an undirected graph. The implementation below uses breadth-first search (BFS) to label connected components, then compares the component IDs of the two vertices.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model

  • Graph type: Undirected and unweighted.

  • Representation: Adjacency list, dict[node, list].

  • Every vertex must appear as a dictionary key.

  • Each undirected edge should appear in both vertices’ adjacency lists.

  • Weights do not affect path existence. Even negative weights are irrelevant when checking reachability rather than a shortest path.

The adjacency list occupies O(V + E) space, where V is the number of vertices and E is the number of edges.

How It Works

  1. Return False if either requested vertex is missing.

  2. Loop over every vertex so disconnected components are handled.

  3. For each unvisited vertex, run BFS and assign a component ID to every reachable vertex.

  4. Compare the component IDs assigned to the start and target vertices.

For the example graph below, the traversal proceeds as follows:

Step Vertex processed Newly discovered Queue afterward
1 A B, D [B, D]
2 B C [D, C]
3 D E [C, E]
4 C None [E]

Because A and C receive the same component ID, the result is True.

Complexity

  • Average time: O(V + E). Every vertex is visited once and every adjacency-list entry is examined once; dictionary and set operations take average O(1) time.

  • Best-case time: O(V + E) under the usual constant-time hash-table model because the implementation labels every component.

  • Worst-case time: O(V² + EV) if adversarial hash collisions make dictionary and set operations O(V) each.

  • Auxiliary space: O(V) for the visited set, component mapping and BFS queue.

  • Input space: O(V + E) for the adjacency list, excluded from the auxiliary-space figure.

  • No recursion is used, so there is no recursion-stack cost or recursion-depth risk.

Code Example

from collections import deque
from collections.abc import Hashable
from typing import TypeVar

Node = TypeVar("Node", bound=Hashable)


def has_path(
    graph: dict[Node, list[Node]],
    start: Node,
    target: Node,
) -> bool:
    """Return whether start and target are in the same connected component."""
    if start not in graph or target not in graph:
        return False

    visited: set[Node] = set()
    component_by_node: dict[Node, int] = {}
    component_id = 0

    # Loop over all roots so disconnected components are also processed.
    for root in graph:
        if root in visited:
            continue

        visited.add(root)
        component_by_node[root] = component_id
        queue: deque[Node] = deque([root])

        while queue:
            node = queue.popleft()

            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    component_by_node[neighbor] = component_id
                    queue.append(neighbor)

        component_id += 1

    return component_by_node[start] == component_by_node[target]


graph = {
    "A": ["B", "D"],
    "B": ["A", "C"],
    "C": ["B", "E"],
    "D": ["A", "E"],
    "E": ["C", "D"],
}

print(has_path(graph, "A", "C"))  # True

Common Pitfalls

  • Directed graphs: Comparing undirected components is insufficient. For a directed graph, run BFS from start, follow only outgoing edges and return True only when target is reached.

  • Missing vertices: An empty graph or an absent start or target vertex returns False. A one-vertex graph returns True only when both arguments identify that vertex.

  • Same vertex: The implementation treats a zero-edge path as valid and returns True.

  • Disconnected graphs: Vertices in separate components correctly return False.

  • Cycles and duplicate edges: The visited set prevents infinite traversal; duplicate edges are harmless. Forgetting the visited set on a cyclic graph causes the traversal not to terminate.

  • Negative values: Negative weights do not affect reachability. Negative integer vertex labels are valid because integers are hashable.

  • Input mutation: This implementation does not modify the adjacency list. Copy it if callers require the original graph to remain isolated from later changes.

  • Representation and bounds: Keep adjacency entries consistent and include every vertex as a key. Sorting is unnecessary. This reachability check has no array offsets, but index-based implementations should avoid off-by-one errors; Python integers do not overflow, while other languages need a sufficiently wide integer type for vertex IDs and counters.

  • Interview follow-up: Expect questions about directed graphs, weighted shortest paths, path reconstruction and the distinction between reachability and shortest-path algorithms.

14

How to print all simple paths in a directed graph with DFS?

Use DFS backtracking to enumerate every simple path from the source to the destination. Each recursive branch maintains its own current path and a path-specific visited set, so cycles are avoided without incorrectly discarding valid paths.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model

The example uses a directed, unweighted graph represented as an adjacency list:

graph[node] = list of outgoing neighbors
  • Space for the representation: O(V + E) for V nodes and E edges.

  • An adjacency matrix would require O(V²) space and is less space-efficient for sparse graphs.

  • “All paths” means all simple paths: a node cannot appear twice in the same path. If repeated vertices were allowed, a cyclic graph could contain infinitely many walks.

How DFS Works

  1. Start at the source with the path [source].

  2. For each unvisited outgoing neighbor:

  3. Add the neighbor to the path and visited set.

  4. Continue exploring from that neighbor.

  5. Remove it afterward when backtracking.

  6. When the destination is reached, print the current path.

  7. The iterative implementation uses an explicit stack, avoiding Python’s recursion-depth limit.

The visited set must belong to the current path, not the whole graph. A global visited set would incorrectly prevent a node from appearing in different valid paths.

Step-by-Step Trace on Example Graph

Graph: A → B, C; B → D; C → D; D → E; E → ∅. Source A, destination E.

Step Action Stack after the step (top at right)
0 Start [(A, (A))]
1 Pop A. Neighbors B, C (reversed → C, B). Push C then B. [(C, (A,C)), (B, (A,B))]
2 Pop B. Neighbor D. Push D. [(C, (A,C)), (D, (A,B,D))]
3 Pop D. Neighbor E is the destination → print A -> B -> D -> E. [(C, (A,C))]
4 Pop C. Neighbor D. Push D. [(D, (A,C,D))]
5 Pop D. Neighbor E is the destination → print A -> C -> D -> E. [] → done

Each stack entry also carries the visited set of its own path, which equals the nodes in that path.

Complexity

Let P be the number of simple paths from source to destination, and L the maximum path length (≤ V).

  • Best-case time: O(V + E) when the source has only the destination as neighbor (or the graph is a single edge). We only traverse that edge and print the path.
    Reason: The algorithm visits the source, sees the destination, prints, and stops without exploring other branches.

  • Average-case time: O((V + E) * P) in practice, because each path is built by extending prefixes and the work per prefix is proportional to its degree.
    Reason: The total number of stack operations is proportional to the number of simple-path prefixes explored, which is bounded by the number of paths times the path length.

  • Worst-case time: O(V! + P * L) (exponential/factorial) for dense graphs where the number of simple paths grows factorially.
    Reason: In a complete directed graph, the number of simple paths from source to destination is ∑_{k=0}^{V-2} (V-2)!/(V-2-k)! = O(V!).

  • Auxiliary space: O(V * Q) where Q is the maximum stack size (number of pending path prefixes). In the worst case Q can be exponential.
    Reason: Each stack entry stores a path tuple and a visited frozenset, each of size up to V.

  • Total space including input graph: O(V + E + V * Q).

  • Output space: O(1) additional if paths are printed as they are found.

Code Example

def print_all_paths_dfs(
    graph: dict[str, list[str]],
    source: str,
    destination: str,
) -> None:
    """Print every simple path from source to destination."""
    # A zero-length path is valid when source and destination are equal.
    if source == destination:
        print(source)
        return

    if source not in graph:
        return

    # Each stack item contains:
    # (current node, current path, vertices in the current path)
    stack: list[tuple[str, tuple[str, ...], frozenset[str]]] = [
        (source, (source,), frozenset((source,)))
    ]

    while stack:
        node, path, visited = stack.pop()

        # Remove duplicate adjacency entries for simple vertex paths.
        neighbors = list(dict.fromkeys(graph.get(node, [])))

        # Reverse neighbors so the first listed neighbor is explored first
        # by this LIFO stack.
        for neighbor in reversed(neighbors):
            if neighbor in visited:
                continue

            new_path = path + (neighbor,)

            if neighbor == destination:
                print(" -> ".join(new_path))
                continue

            new_visited = visited | frozenset((neighbor,))
            stack.append((neighbor, new_path, new_visited))


graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": ["E"],
    "E": [],
}

print_all_paths_dfs(graph, "A", "E")

# Expected output:
# A -> B -> D -> E
# A -> C -> D -> E

For the example, DFS explores A → B → D → E first, backtracks, and then explores A → C → D → E. The algorithm only visits the component reachable from the source; disconnected components do not contain a source-to-destination path.

Common Pitfalls and Interview Tips

  • Using one global visited set: This removes valid paths that reach the same node through different prefixes.

  • Forgetting to backtrack: The current path and visited set must be restored after each branch.

  • Allowing cycles: Without path-specific visited tracking, cyclic graphs can cause infinite traversal.

  • Ignoring duplicate edges: Duplicate adjacency entries can print the same vertex path repeatedly; the implementation removes them.

  • Confusing paths with walks: Simple paths forbid repeated vertices. Clarify this assumption in the interview.

  • Using recursive DFS without considering depth: A recursive solution may exceed Python’s default recursion limit; an explicit stack avoids that issue.

  • Common follow-up questions: How would BFS find the shortest path? How would Dijkstra handle weighted edges? How would you detect cycles? How would you count paths instead of printing them?

15

What is a bipartite graph and how is bipartiteness detected?

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects vertices in different sets. Equivalently, the graph is 2-colorable and contains no odd-length cycle.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Concept

For the undirected, unweighted graph discussed here, vertices are represented with an adjacency list such as dict[node, list[node]].

Assign one of two colors to every vertex, then use BFS to ensure that adjacent vertices receive opposite colors:

  1. Start an uncolored vertex with color 0.

  2. Visit its neighbors with BFS.

  3. Give each uncolored neighbor the opposite color.

  4. If two adjacent vertices already have the same color, the graph is not bipartite.

  5. Repeat from every remaining uncolored vertex to handle disconnected components.

The graph type and representation are:

  • Directed or undirected: The example uses an undirected graph. For a directed graph, the same coloring check treats every edge as a constraint between its endpoints.

  • Weighted or unweighted: Weights are irrelevant; only edge endpoints matter.

  • Adjacency list: Uses O(V + E) space including the graph, where V is the number of vertices and E is the number of edges.

  • Adjacency matrix: Would use O(V²) space but is less space-efficient for sparse graphs.

Detection Logic

Bipartiteness can be characterized in several equivalent ways:

Property Meaning
Two-colorable Vertices can be assigned one of two colors so adjacent vertices differ
No odd cycle The graph contains no cycle with an odd number of edges
BFS coloring succeeds Every edge connects opposite-colored vertices

The BFS algorithm is preferable to repeatedly trying every possible partition, which would require exponential time.

Complexity

For an adjacency-list graph with V vertices and E edges:

  • Best, average and worst-case time: O(V + E). Each vertex is visited at most once and each adjacency-list entry is inspected at most once.

  • Auxiliary space: O(V) for the color map, BFS queue, and visited information. The input graph is not counted.

  • Total space including input: O(V + E).

Code Example

from collections import deque
from typing import Hashable


def is_bipartite(graph: dict[Hashable, list[Hashable]]) -> bool:
    """Return True if an undirected adjacency-list graph is bipartite."""
    colors: dict[Hashable, int] = {}

    # Loop over all vertices so disconnected components are checked.
    for start in graph:
        if start in colors:
            continue

        colors[start] = 0
        queue = deque([start])

        while queue:
            node = queue.popleft()

            for neighbor in graph[node]:
                if neighbor not in colors:
                    colors[neighbor] = 1 - colors[node]
                    queue.append(neighbor)
                elif colors[neighbor] == colors[node]:
                    return False

    return True


# Expected output: False
print(is_bipartite({
    "A": ["B", "C"],
    "B": ["A", "E"],
    "C": ["A", "D"],
    "D": ["C", "E"],
    "E": ["D", "B"],
}))

Example Walkthrough

For the graph A-B-C style connections used in the code:

  1. Color A with color 0.

  2. Color its neighbors B and C with color 1.

  3. From C, color D with color 0.

  4. From D, color E with color 1.

  5. Edge B-E now connects two color-1 vertices, so the graph is not bipartite.

  6. In fact, B-A-C-D-E-B is a cycle of length five, which is an odd cycle.

Common Pitfalls

  • Ignoring disconnected components: Start BFS from every uncolored vertex, not only from the first vertex.

  • Forgetting the visited or color state: A single color map serves both purposes because each vertex needs one assigned color.

  • Using recursion: Recursive DFS can exceed Python’s default recursion limit for large graphs; iterative BFS avoids that issue.

  • Assuming every graph is connected: An empty graph and a graph with isolated vertices are both bipartite.

  • Handling self-loops incorrectly: A self-loop requires a vertex to have the opposite color from itself, so it correctly causes rejection.

  • Mutating the input: The implementation only reads the adjacency lists.

  • Common follow-up: Interviewers may ask for the actual two color groups, whether the graph contains an odd cycle, or how to verify bipartiteness in a directed graph.

16

How do you identify cyclic and acyclic graphs?

A cyclic graph contains at least one cycle, while an acyclic graph contains no cycles. For directed graphs, acyclicity means the graph is a directed acyclic graph (DAG); for undirected graphs, an acyclic graph is a forest, which may be disconnected.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Key Definitions

  • Directed cycle: A sequence of distinct vertices (v_0,ldots,v{k-1}) with directed edges (v_i rightarrow v{i+1}), where indices wrap around so that (v_{k-1} rightarrow v_0). A self-loop is a cycle of length one.

  • Undirected cycle: A closed path that returns to its starting vertex without repeating internal vertices. In a simple graph, it has at least three vertices.

  • Acyclic graph: A directed graph with no directed cycle, or an undirected graph with no undirected cycle.

  • Self-loop: An edge from a vertex to itself; it forms a cycle.

  • Weights: Edge weights do not affect cycle detection; the algorithms work for weighted and unweighted graphs.

The examples use an adjacency list represented as dict[node, list]. It requires (O(V+E)) total space, where (V) is the number of vertices and (E) is the number of edges. Directed edges appear once; undirected edges appear in both endpoints’ lists. The examples assume simple graphs, so duplicate adjacency entries represent the same edge rather than parallel edges.

Identification Methods

  • Directed graph—three-colour DFS:

  • White: not discovered.

  • Grey: currently on the DFS stack.

  • Black: completely processed.

  • An edge to a grey vertex identifies a directed cycle.

  • Undirected graph—parent tracking:

  • Track the parent from which each vertex was discovered.

  • In a simple graph, an edge to an already visited vertex other than the current vertex’s parent identifies a cycle.

  • Disconnected graphs: Start DFS from every unvisited vertex.

  • Implementation style: The examples use iterative DFS to avoid Python’s recursion-depth limit.

Code Example

from collections.abc import Iterator

Graph = dict[int, list[int]]


def has_directed_cycle(graph: Graph) -> bool:
    """Return whether a directed adjacency-list graph contains a cycle."""
    visited: set[int] = set()
    colors: dict[int, int] = {}  # 0 = white, 1 = grey, 2 = black

    for start in graph:
        if start in visited:
            continue

        visited.add(start)
        colors[start] = 1
        stack: list[tuple[int, Iterator[int]]] = [
            (start, iter(graph.get(start, ())))
        ]

        while stack:
            node, neighbors = stack[-1]

            try:
                neighbor = next(neighbors)
            except StopIteration:
                colors[node] = 2
                stack.pop()
                continue

            if colors.get(neighbor, 0) == 1:
                return True

            if neighbor not in visited:
                visited.add(neighbor)
                colors[neighbor] = 1
                stack.append((neighbor, iter(graph.get(neighbor, ()))))

    return False


def has_undirected_cycle(graph: Graph) -> bool:
    """Return whether a symmetric simple undirected graph contains a cycle."""
    visited: set[int] = set()

    for start in graph:
        if start in visited:
            continue

        visited.add(start)
        stack: list[tuple[int, int | None]] = [(start, None)]

        while stack:
            node, parent = stack.pop()
            unique_neighbors = set(graph.get(node, ()))

            for neighbor in unique_neighbors:
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append((neighbor, node))
                elif neighbor != parent:
                    return True

    return False


if __name__ == "__main__":
    directed_graph = {
        0: [1],
        1: [2],
        2: [0],
        3: [4],  # Separate disconnected component.
        4: [],
    }
    print(has_directed_cycle(directed_graph))  # True

    acyclic_directed_graph = {0: [1], 1: [2], 2: []}
    print(has_directed_cycle(acyclic_directed_graph))  # False

    undirected_graph = {
        0: [1, 2],
        1: [0, 2],
        2: [0, 1],
        3: [],
    }
    print(has_undirected_cycle(undirected_graph))  # True

For the directed example, DFS discovers 0, then 1, then 2. When 2 encounters the edge back to 0, vertex 0 is still grey, proving that a directed cycle exists.

Complexity

Algorithm Time Auxiliary space Total space including input
Directed three-colour DFS (O(V+E)) (O(V)) (O(V+E))
Undirected parent-tracking DFS (O(V+E)) (O(V+Delta)) (O(V+E))
  • Time: Each vertex and adjacency-list entry is processed once under the standard constant-time-average hash-set model.

  • Directed auxiliary space: The visited set, colour map, and explicit DFS stack each use at most (O(V)).

  • Undirected auxiliary space: The visited set and stack use (O(V)); the temporary neighbour set uses (O(Delta)), where (Delta) is the maximum adjacency-list length. For a simple graph, this is (O(V)).

  • Input counting: Auxiliary space excludes the adjacency list; total space includes it.

Common Pitfalls

  • An empty graph or a graph with one isolated vertex is acyclic; a single self-loop is cyclic.

  • Using only a visited set for directed graphs is insufficient: an edge to any visited vertex is not necessarily a cycle; it must target a grey vertex.

  • Forgetting the parent check in an undirected graph treats the edge back to the parent as a cycle.

  • Starting DFS from only one vertex misses cycles in disconnected components.

  • Duplicate adjacency entries are treated as the same edge in these simple-graph examples. Multigraphs require preserving edge multiplicity because parallel undirected edges form a cycle.

  • Assuming every acyclic directed graph is connected. A DAG may have multiple components.

  • Assuming weights affect the result: even negative weights do not change cycle detection.

  • Adjacency-list ordering is irrelevant; no sorted-input precondition is required.

17

What conditions determine whether a graph is planar in graph theory?

A planar graph is a graph that can be drawn in a plane without any edges crossing except where edges share an endpoint. Planarity is a property of the graph’s structure: a graph is planar if at least one crossing-free drawing exists, not necessarily every drawing.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model and Representation

The main conditions below apply to a finite, simple, undirected graph (G=(V,E)):

  • Vertices: (V) nodes.

  • Edges: (E) connections, with no self-loops or parallel edges.

  • Representation: Usually an adjacency list such as dict[node, list], requiring (O(V+E)) space.

For a weighted or directed graph, planarity depends on its underlying undirected simple graph. If that underlying graph is planar, the weighted or directed graph is also considered planar.

Necessary Conditions from Euler’s Formula

For a connected planar embedding, Euler’s formula is:

[ V-E+F=2 ]

where (F) is the number of faces, including the unbounded outer face. For a disconnected planar graph with © connected components:

[ V-E+F=1+C ]

Two useful consequences are:

Graph type Necessary edge bound Reason
Simple planar graph, (V ge 3) (E le 3V-6) Every face has boundary length at least 3, and face boundaries sum to (2E)
Simple planar bipartite graph, (V ge 3) (E le 2V-4) Every face has boundary length at least 4 because it alternates between the two parts

A related necessary condition is that every simple planar graph contains a vertex of degree at most 5. Equivalently, its average degree is less than 6.

These bounds are screening tests only. Satisfying an edge bound does not prove that a graph is planar.

Complete Characterization

The strongest classical characterization is Kuratowski’s theorem:

A graph is planar if and only if it contains no subgraph that is a subdivision of (K_5) or (K_{3,3}).

A subdivision replaces edges with internally vertex-disjoint paths.

Equivalently, Wagner’s theorem states that a graph is planar if and only if it contains neither (K_5) nor (K_{3,3}) as a minor.

These are complete conditions, unlike Euler’s edge bounds.

Examples of Nonplanar Graphs

Consider the two fundamental forbidden graphs:

  1. (K_5) has (V=5) and (E=10).

  2. The planar bound is (3V-6=9).

  3. Since (10>9), (K_5) cannot be planar.

  4. (K_{3,3}) has (V=6) and (E=9).

  5. It is bipartite, so the planar bipartite bound is (2V-4=8).

  6. Since (9>8), (K_{3,3}) cannot be planar.

Any graph containing a subdivision of either graph is also nonplanar. By contrast, trees and forests are always planar because they contain no cycles that create unavoidable crossings.

Complexity and Planarity Testing

Counting vertices and edges in an adjacency-list representation takes:

  • Time: (O(V+E)), because every adjacency-list entry is inspected.

  • Extra space: (O(1)) if only the counts are needed.

A complete planarity test, such as the Hopcroft–Tarjan algorithm, can:

  • Time: (O(V+E)).

  • Extra space: (O(V+E)) for the embedding and auxiliary structures.

  • Input storage: The adjacency-list representation itself occupies (O(V+E)).

An adjacency-matrix representation would occupy (O(V^2)) space, although matrix operations should not be confused with the complexity of the underlying planarity algorithm.

Common Pitfalls and Interview Tips

  • Edge bounds are not sufficient: A graph can satisfy (E le 3V-6) and still be nonplanar.

  • Bipartite does not imply planar: (K_{3,3}) is bipartite and nonplanar.

  • Drawing one planar embedding proves planarity: If edges can be positioned without crossings, the graph is planar regardless of whether other drawings have crossings.

  • Do not confuse planarity with cycle absence: Graphs with cycles can still be planar.

  • Handle disconnected graphs: Euler’s connected form uses (V-E+F=2); the disconnected form uses (V-E+F=1+C).

  • Common follow-up: Interviewers often ask for the complexity of a planarity test or how forbidden subgraphs differ from forbidden minors.

18

What are dense and sparse graphs, and how are their densities measured?

A dense graph has roughly the maximum possible number of edges for its vertex count (e.g. a complete graph), while a sparse graph has far fewer edges than the maximum, so most vertex pairs are non-adjacent. The distinction is not a strict binary — it is a continuum described by a density ratio or average degree.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definitions and Density Measures

For a simple graph with V vertices and E edges, the maximum number of edges is:

Graph type Maximum edges E_max
Undirected, simple V * (V - 1) / 2
Directed, simple V * (V - 1)

Common measures of density:

  • Density ratio: d = E / E_max. It lies in [0, 1]; d = 1 is complete, d = 0 is edgeless. Many texts use d ≥ 0.5 as the “dense” convention, but thresholds vary, so always state yours.

  • Average degree: 2E / V for undirected graphs, E / V for directed ones. A common shorthand: a graph is sparse when E = O(V) or E = O(V log V), and dense when E = Θ(V²).

  • Intermediate (“semi-sparse”): E = Θ(V^1.5) appears in real graphs and sits between the two regimes.

Worked example (undirected):

Graph V E E_max Density Average degree
Path A–B–C–D 4 3 6 0.50 1.5
Star with 4 leaves 5 4 10 0.40 1.6
Complete K4 4 6 6 1.00 3.0

Note the convention matters: self-loops and parallel edges are normally excluded from E_max, so if you allow multi-edges, E can exceed E_max and density must be defined differently.

Representation and Storage Costs

Representation Space Best fit Traversal cost
Adjacency list dict[node, list] O(V + E) Sparse graphs BFS/DFS O(V + E)
Adjacency matrix list[list[bool/int]] O(V²) Dense graphs Scanning a row is O(V); DFS/BFS O(V²)
Edge list list[(u, v)] O(V + E) Sparse graphs, Kruskal, union-find Sorting edges O(E log E)

Because matrix cells are mostly 0/False for sparse graphs, the O(V²) memory is wasted; conversely, for a dense graph a list forces you to scan many neighbours to find a specific one, while a matrix gives O(1) edge lookup.

Typical Use Cases

Dense graphs Sparse graphs
Complete or near-complete structures, small V Social networks, web links, citation networks
Floyd–Warshall all-pairs shortest paths O(V³) Road maps and transit networks
Transitive closure, reachability via bitsets Dependency and build graphs
Brute-force TSP / Hamiltonian search Topological sort of a DAG O(V + E)
Dense linear algebra, Gaussian elimination, network flow Dijkstra with a binary heap O((V + E) log V)
Game-AI move graphs, co-occurrence matrices Kruskal MST O(E log E), union-find O(E α(V))

Rule of thumb: use an adjacency matrix when E = Θ(V²) and you need many O(1) edge queries; use an adjacency list when E = O(V)–O(V log V) and you mostly traverse or run a heap-based algorithm.

Code Example

def count_edges(graph: dict[int, list[int]], *, directed: bool = False) -> int:
    """Count edges of a simple graph given as {node: [neighbours]}.

    Undirected count assumes symmetric neighbour lists and ignores self-loops.
    """
    count = 0
    for node, neighbours in graph.items():
        for other in neighbours:
            if directed:
                count += 1
            elif node < other:  # count each undirected edge once
                count += 1
    return count


def density(graph: dict[int, list[int]], *, directed: bool = False) -> float:
    """Return E / E_max for a simple graph; 0.0 for a graph with no possible edges."""
    vertices = len(graph)
    max_edges = vertices * (vertices - 1) if directed else vertices * (vertices - 1) // 2
    if max_edges == 0:  # empty graph or a single vertex
        return 0.0
    return count_edges(graph, directed=directed) / max_edges


# Example: path A-B-C-D
path = {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}
print(density(path))  # 0.5

Both functions run in O(V + E) time (they scan every adjacency entry) and O(1) extra space beyond the input; the input graph itself is not counted. The matrix-based equivalent is O(V²) time.

Common Pitfalls and Interview Tips

  • Off-by-one in E_max: use V(V-1)/2 for undirected and V(V-1) for directed; the former is only an integer because the product is always even.

  • Empty graph / single vertex: E_max = 0, so guard the division instead of returning NaN or crashing.

  • Direction matters: an undirected E/2 correction double-counts edges; count each edge once (as above) or divide the adjacency sum by two.

  • Self-loops and multi-edges break the “simple graph” density formula — state the assumption explicitly.

  • Don’t confuse density with connectivity: a graph can be sparse yet connected, or dense yet disconnected.

  • Watch the representation, not the label: an algorithm’s complexity depends on E and the storage format. A sparse graph stored as a matrix still costs O(V²) memory.

  • Typical follow-ups: “Which algorithms are faster on sparse vs dense graphs?” (Dijkstra/Kruskal/BFS vs Floyd–Warshall), “How would you detect a dense subgraph inside a large sparse graph?” (e.g. degree-based filtering, cliques, or heavy-hitter/heuristic methods), and “How does the choice of representation affect memory for a million-node graph?”

19

Why does DFS have O(V + E) time complexity?

For an adjacency-list graph, depth-first search (DFS) runs in O(V + E) time because it processes each vertex once and scans each adjacency-list entry only a constant number of times. A full traversal covers every connected component.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model

  • Vertices and edges: V is the number of vertices and E is the number of edges.

  • Graph types: DFS works on directed or undirected, weighted or unweighted graphs. Edge weights do not affect the traversal bound because ordinary DFS does not use them.

  • Representation: The analysis uses an adjacency list, dict[node, list].

  • Input space: The adjacency-list representation occupies O(V + E) space, including the dictionary, vertex lists, and stored edge entries.

  • Traversal requirement: A full DFS must start another search from an unvisited vertex to handle disconnected components.

Why the Bound Holds

During a DFS with visited tracking:

  1. Each vertex is discovered and processed at most once, contributing O(V) total vertex-processing work.

  2. Each processed vertex’s adjacency list is scanned exactly once.

  3. In a directed graph, each edge normally contributes one adjacency-list entry, so there are O(E) edge inspections.

  4. In an undirected graph, each edge appears in two adjacency lists, so there are 2E, or still O(E), edge inspections.

Combining the vertex and edge costs gives O(V + E). The constant-factor difference between directed and undirected graphs does not change the asymptotic bound.

For disconnected graphs, the individual component costs sum to at most O(V + E), provided the outer traversal starts a DFS from every unvisited vertex.

Complexity

Representation or metric Best case Average case Worst case Reason
Adjacency-list DFS O(V + E) O(V + E) O(V + E) Every vertex and adjacency entry is processed
Adjacency-matrix DFS O(V²) O(V²) O(V²) Each of V vertices may scan V matrix columns
Auxiliary space O(V) O(V) O(V) The visited set and DFS stack each contain at most V vertices

Auxiliary space is O(V), including both the visited set and either an explicit stack or recursive call stack, but excluding the input adjacency list. Including the input, total space is O(V + E). If the traversal order is retained, it adds O(V) output space.

Example Walkthrough

Consider the directed edges 0 → 1, 0 → 2, and 2 → 1. Using an iterative DFS that pushes neighbors in reverse adjacency-list order:

  1. Push 0 and mark it visited.

  2. Pop 0. Its reversed adjacency list causes 2 and then 1 to be pushed, so 1 is popped first.

  3. Pop 1; it has no outgoing edges.

  4. Pop 2; its neighbor 1 is already visited.

  5. The traversal order is [0, 1, 2].

Common Pitfalls

  • Forgetting disconnected components: A DFS started from one vertex does not visit the other components.

  • Omitting isolated vertices: Represent them as keys in the adjacency-list dictionary if they must appear in the traversal.

  • Failing to track visited vertices: Cycles and self-loops can cause repeated vertex processing.

  • Confusing representations: O(V + E) applies to adjacency lists; scanning an adjacency matrix takes O(V²).

  • Misstating duplicate handling: Parallel edges add adjacency entries and contribute to E, but proper visited-on-discovery tracking prevents repeated processing of the same vertex.

  • Recursive overflow: A recursive DFS may exceed Python’s roughly 1,000-call limit; an explicit stack avoids that limit.

  • Edge cases: Empty graphs have no components, a single vertex forms one component, disconnected graphs require multiple DFS starts, and cycles are handled by the visited set. Negative node labels work when hashable, weights are irrelevant to ordinary DFS, and adjacency-list ordering—including already sorted lists—does not change the complexity.

20

How do I implement topological sorting in a directed acyclic graph?

Topological sort produces an ordering of a directed acyclic graph’s vertices such that every vertex appears after all of its predecessors. Kahn’s algorithm uses indegree and a queue to construct this ordering in linear time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Kahn’s algorithm follows these steps:

  1. Calculate each vertex’s indegree—the number of incoming edges.

  2. Add every zero-indegree vertex to a queue.

  3. Repeatedly remove a vertex from the queue and append it to the result.

  4. Decrease the indegree of each outgoing neighbor. If its indegree becomes zero, enqueue it.

  5. If fewer than V vertices are processed, the graph contains a cycle and no topological ordering exists.

The algorithm is iterative, so it does not risk Python’s recursion-depth limit.

Graph Representation

This implementation expects a directed, acyclic graph, represented as an adjacency list:

  • Unweighted or weighted: Edge weights do not affect topological sorting.

  • Adjacency list dict[node, list]: Requires O(V + E) space, including the input.

  • Adjacency matrix dict[node, dict]: Requires O(V²) space but offers constant-time edge lookup.

Every vertex must appear as a key in the adjacency list, including vertices with no outgoing edges.

Example Walkthrough

For the edges A → B, A → C, B → D, and C → D:

Step Available zero-indegree vertices Output so far
1 A []
2 B, C [A]
3 C [A, B]
4 D [A, B, C]
5 None [A, B, C, D]

The ordering is not necessarily unique; any ordering that respects all dependencies is valid.

Code Example

from collections import deque


def topological_sort(graph: dict[str, list[str]]) -> list[str]:
    """Return a topological ordering of a directed acyclic graph."""
    indegree: dict[str, int] = {node: 0 for node in graph}

    for neighbors in graph.values():
        for neighbor in neighbors:
            indegree[neighbor] += 1

    queue = deque(node for node in graph if indegree[node] == 0)
    visited: set[str] = set()
    ordering: list[str] = []

    while queue:
        node = queue.popleft()

        if node in visited:
            continue
        visited.add(node)
        ordering.append(node)

        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(ordering) != len(graph):
        raise ValueError("Topological sort requires a directed acyclic graph")

    return ordering


graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": [],
}

print(topological_sort(graph))  # Expected output: ['A', 'B', 'C', 'D']

Complexity

For V vertices and E edges:

  • Time: O(V + E) in the best, average, and worst cases. Every vertex is processed once, and every edge is examined once.

  • Auxiliary space: O(V) in all cases for the indegree map, queue, visited set, and output. The input graph is not counted; there is no recursion stack.

Common Pitfalls

  • Missing disconnected components: Kahn’s algorithm naturally handles them because every vertex with indegree zero is initially queued.

  • Ignoring cycles: A cycle prevents its vertices from reaching indegree zero. Always compare the number of processed vertices with V.

  • Mutating the input: This implementation does not modify the adjacency list.

  • Duplicate edges: Repeated edges are treated as repeated dependencies; each occurrence is included in both the indegree calculation and decrement.

  • Assuming a unique ordering: Independent vertices may appear in any relative order.

  • Overlooking edge cases: Empty graphs return [], and a single-vertex graph returns that vertex.

21

How can you detect a cycle in an undirected graph?

Parent-tracking depth-first search (DFS) detects a cycle in an undirected graph by finding an already visited neighbor through an edge other than the DFS-tree edge used to reach the current vertex. The algorithm runs in linear time when the graph uses an adjacency-list representation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model

The example uses an undirected, unweighted graph represented as an adjacency list:

graph[node] = [neighbor1, neighbor2, ...]

Every vertex appears as a key, and each undirected edge appears in the adjacency lists of both endpoints.

  • Vertices: V

  • Edges: E

  • Adjacency-list input space: O(V + E)

  • Auxiliary space: O(V) for the visited set, parent map, and DFS stack

The implementation is iterative, so it does not depend on Python’s recursion limit.

How It Works

  1. Maintain a visited set and a parent_of map.

  2. Start DFS from every unvisited vertex so disconnected components are checked.

  3. When discovering a neighbor, record the current vertex as its parent.

  4. For an already visited neighbor:

  5. Ignore the reverse of the DFS-tree edge to the current vertex’s parent.

  6. Ignore a repeated occurrence of a DFS-tree edge.

  7. Otherwise, the non-tree edge closes a cycle and detection succeeds.

The parent checks are essential: each undirected tree edge appears in both adjacency lists, but neither direction represents a cycle by itself. Any other non-tree edge, together with the DFS-tree path between its endpoints, forms a cycle.

For the graph 0—1—2—0, DFS visits 0, then 1, then 2. Vertex 2 encounters already visited vertex 0 through a non-tree edge, so the result is True.

Complexity

For an adjacency-list representation:

Case Time Reason
Best O(V + E) Each vertex and adjacency-list entry is inspected at most once
Average O(V + E) Deterministic linear-time traversal
Worst O(V + E) All vertices and edges may be examined
  • Auxiliary space: O(V) for visited, parent_of, and the explicit DFS stack.

  • Space including the input: O(V + E).

  • The iterative implementation uses no recursion stack.

Code Example

def has_cycle(graph: dict[int, list[int]]) -> bool:
    """Return True if the simple undirected graph contains a cycle."""
    visited: set[int] = set()
    parent_of: dict[int, int | None] = {}

    # Check every component, not only the component containing one start node.
    for start in graph:
        if start in visited:
            continue

        visited.add(start)
        parent_of[start] = None
        stack: list[int] = [start]

        while stack:
            node = stack.pop()

            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    parent_of[neighbor] = node
                    stack.append(neighbor)
                elif (
                    parent_of[node] != neighbor
                    and parent_of[neighbor] != node
                ):
                    # A non-tree edge closes a cycle.
                    return True

    return False


graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1],
}

print(has_cycle(graph))  # True

Edge Cases

  • Empty graph: Returns False.

  • One vertex without a self-loop: Returns False.

  • Self-loop: Returns True; a self-loop is a cycle.

  • Disconnected graph: The outer loop checks every component.

  • Repeated adjacency entries: Repeated occurrences of the same endpoint pair are treated as one simple edge and do not create a false positive.

  • Parallel edges: A plain adjacency list cannot distinguish accidental duplicates from distinct parallel edges. This implementation treats them as one simple edge; use edge IDs or an edge list if two parallel edges should count as a cycle.

  • Negative or non-consecutive vertex labels: Labels have no effect on the algorithm.

Common Pitfalls

  • Forgetting the parent check: The reverse of every DFS-tree edge would incorrectly appear to form a cycle.

  • Forgetting the visited set: Vertices can be processed repeatedly, wasting time and potentially producing incorrect results.

  • Starting DFS from only one vertex: A disconnected component containing a cycle may be missed.

  • Off-by-one errors: The iterative algorithm uses no array indices, but a matrix-based variant must examine every valid row and column without going out of bounds.

  • Integer overflow in other languages: In fixed-width languages, counters and vertex identifiers need sufficiently wide integer types; Python integers do not overflow.

  • Using recursion: Deep graphs can exceed Python’s default recursion limit; the explicit stack avoids this issue.

  • Mutating the graph: This implementation does not modify the adjacency list.

  • Assuming adjacency lists are symmetric: For an undirected graph, each edge should be stored for both endpoints.

  • Interview follow-up: Interviewers may ask about directed-cycle detection using three colors or a recursion stack, or about using union-find when only cycle existence matters.

22

What is the complexity of all-pairs shortest path algorithms?

All-pairs shortest path (APSP) algorithms compute the shortest distance between every pair of vertices. Their complexity depends on the number of vertices, edges, graph density, and whether edge weights may be negative.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model and Representations

For this comparison, assume a weighted directed graph; an undirected graph can be represented by adding edges in both directions. An unweighted graph is the special case where every edge has weight 1.

  • Adjacency matrix: stores weights in a two-dimensional array and requires Θ(V²) space. It supports direct O(1) edge lookup but is expensive for sparse graphs.

  • Adjacency list: uses a structure such as dict[node, list] and requires Θ(V + E) space. It is normally preferred for sparse graphs and Dijkstra-based algorithms.

  • Edge list: stores each edge once and requires Θ(V + E) space; algorithms using it generally also build an adjacency list.

  • APSP output: retaining all distances requires a distance matrix of Θ(V²) space.

All space bounds below include the stored input. The standard implementations are iterative, so there is no additional recursion-stack cost.

Complexity Comparison

Algorithm Precondition Time Complexity Space Complexity
Floyd-Warshall No reachable negative cycle O(V³): it considers every intermediate vertex for every ordered pair O(V²): one distance matrix, including the output
Johnson’s algorithm No reachable negative cycle O(VE + V² log V) with a Fibonacci heap: Bellman-Ford is O(VE) and all-source Dijkstra is O(VE + V² log V) O(V + E) working space; O(V²) if all distances are retained
Repeated Dijkstra Non-negative edge weights O(V(V + E) log V) with a binary heap: one Dijkstra per source O(V + E) working space; O(V²) if all distances are retained
Repeated BFS Unweighted graph O(V(V + E)): one BFS per source O(V + E) working space; O(V²) if all distances are retained

These are deterministic worst-case bounds; APSP algorithms do not have a separate conventional average-case bound. Floyd-Warshall remains Θ(V³) in the standard implementation even for sparse inputs. For a connected graph, repeated binary-heap Dijkstra simplifies to O(VE log V).

How the Algorithms Scale

  • Floyd-Warshall uses dynamic programming with the recurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). It supports negative edge weights, but a reachable negative cycle makes the affected shortest-path distances invalid.

  • Johnson’s algorithm first uses Bellman-Ford to compute potentials, reweights the edges so they become non-negative, and then runs Dijkstra from every vertex. It is particularly useful for sparse graphs containing negative edges.

  • Repeated Dijkstra is often simpler when all weights are non-negative, but its time grows by a factor of V because it runs the single-source algorithm from every vertex.

  • Repeated BFS is the unweighted counterpart. Each BFS costs O(V + E), including initialization of the distance array.

Walkthrough and Edge Cases

For directed edges A → B of weight 5 and B → C of weight 1:

  1. Initially, the shortest known distance from A to C is infinity.

  2. When B is considered as an intermediate vertex, dist[A][C] becomes 5 + 1 = 6.

  3. Considering the remaining vertices does not produce a shorter path in this example.

Relevant edge cases include:

  • Empty graph: the distance matrix is empty.

  • One vertex: its distance to itself is 0.

  • Duplicate edges: an adjacency matrix should retain the minimum edge weight.

  • Negative edges: these are valid when no reachable negative cycle exists.

  • Already sorted input: ordering has no effect on the result.

  • Disconnected graph: unreachable pairs remain infinity.

  • Cycles: positive and zero-weight cycles are harmless; reachable negative cycles invalidate the shortest paths.

Common Pitfalls

  • Do not confuse one Dijkstra run, O((V + E) log V), with running it from every vertex.

  • Distinguish working space from the O(V²) space needed to retain every source’s distances.

  • Use an infinity value or a safely checked sentinel; an arbitrary large constant can overflow or collide with legitimate path lengths.

  • Detect or exclude reachable negative cycles before interpreting the result as shortest-path distances.

23

Why does BFS often use more memory than DFS?

BFS often uses more memory than DFS because its queue retains a broad frontier of discovered vertices, while DFS usually keeps a narrower path or a smaller set of pending branches. However, both use O(V) auxiliary space in the worst case, so BFS is not asymptotically more memory-intensive.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model

The example uses an undirected, unweighted graph represented by an adjacency list: dict[node, list[node]].

  • The same traversal and memory behavior applies to directed graphs.

  • An adjacency list requires O(V + E) space.

  • An adjacency matrix requires O(V²) space and changes traversal time to O(V²).

  • BFS finds shortest paths by edge count only for an unweighted graph. For weighted graphs, use Dijkstra’s algorithm or another appropriate shortest-path algorithm.

Why BFS Retains More Memory

BFS processes vertices level by level. Its queue contains discovered vertices that are waiting to be processed, potentially including an entire level of the graph.

DFS follows one branch before backtracking. Its explicit stack usually contains fewer pending vertices, while a recursive DFS stores the active path in the call stack.

The difference is not guaranteed: an iterative DFS can place many siblings on its stack, while a small BFS queue might remain compact. The key distinction is that BFS is intentionally optimized to retain a wide frontier.

Complexity

Algorithm Best, Average, and Worst Time Auxiliary Space Input Counted?
BFS O(V + E) O(V) for visited and the queue No
DFS O(V + E) O(V) for visited and the stack or recursion stack No

Both algorithms process each vertex and adjacency-list entry once, assuming expected O(1) hash-set operations. If the adjacency list and returned traversal order are included, total space is O(V + E) for either algorithm.

For the example graph below:

  • BFS order: 1, 2, 3, 4, 5, 6; maximum queue size is 3.

  • DFS order: 1, 2, 4, 3, 5, 6; maximum stack size is 2.

Step BFS: Emitted, Pending DFS: Emitted, Pending
1 1, [2, 3] 1, [3, 2]
2 2, [3, 4] 2, [3, 4]
3 3, [4, 5, 6] 4, [3]
4 4, [5, 6] 3, [6, 5]
5 5, [6] 5, [6]
6 6, [] 6, []

Common Pitfalls

  • Incorrect complexity claim: BFS is often larger in practice, but both BFS and DFS have O(V) worst-case auxiliary space.

  • Assuming DFS always uses O(1) space: Its stack or recursion stack can contain O(V) vertices.

  • Forgetting visited: Cycles or repeated edges can cause repeated processing or infinite traversal.

  • Ignoring disconnected components: The outer loop over all graph keys is necessary.

  • Recursion depth: Recursive DFS can exceed Python’s default recursion limit on long paths; the iterative version avoids that issue.

  • Edge cases: Empty input returns []; one vertex returns that vertex; duplicate neighbors are processed once; negative node labels are supported; input insertion order affects traversal order but requires no sorting.

  • Weighted graphs: Negative weights invalidate ordinary BFS-based shortest-path reasoning; use an algorithm designed for the graph’s weights.

24

How does peak memory usage differ between DFS and BFS?

Peak memory consumption is usually governed by the algorithm’s live frontier: DFS stores pending vertices in a stack, while BFS stores pending vertices in a queue. Both require O(V) auxiliary space in the worst case, but their actual peaks depend on the graph’s shape.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Memory Model

For an undirected, unweighted graph represented by an adjacency list dict[node, list]:

  • The adjacency list itself occupies O(V + E) space.

  • DFS uses a visited set and a stack containing discovered but unprocessed vertices.

  • BFS uses a visited set and a queue containing discovered but unprocessed vertices.

  • Each discovered vertex is stored once when it is marked as visited.

Algorithm Time Auxiliary space Total space including input Main memory driver
DFS O(V + E) O(V) worst case O(V + E) Maximum stack size
BFS O(V + E) O(V) worst case O(V + E) Maximum queue size

The time bound is O(V + E) for both average and worst cases because each vertex is processed once and each adjacency-list entry is examined once. For an empty graph, both take O(1) time.

The auxiliary space is O(V) because both the visited set and frontier can contain up to V vertices. The input graph is not included in the auxiliary-space figure.

DFS Versus BFS Peaks

DFS often resembles a deep, narrow path, especially when implemented recursively. Its call stack is proportional to the path depth, although an iterative DFS stack can also contain pending sibling vertices.

BFS is organized by graph distance. Its queue can become large when many vertices appear at the same distance from the starting vertex.

This means neither algorithm always consumes more memory:

  • A deep graph may produce a large DFS stack but a small BFS queue.

  • A wide graph may produce a large BFS queue but a smaller DFS stack.

  • A balanced graph can produce similar peaks for both.

Actual byte usage depends on the programming language and runtime, but the structural frontier size is usually the relevant interview metric.

Step-by-Step Example

Consider these connections, represented as an adjacency list:

A: B, C
B: A, D, E
C: A, F, G
D: B
E: B
F: C
G: C

Starting at A:

Algorithm State after processing Frontier
DFS A Stack: [B, C]
DFS C Stack: [B, F, G], peak size 3
BFS A Queue: [B, C]
BFS B Queue: [C, D, E]
BFS C Queue: [D, E, F, G], peak size 4

DFS reaches C first because it removes the most recently discovered vertex from the stack. BFS reaches C only after processing B.

Code Example

The following runnable function compares the maximum number of vertex references held simultaneously by the DFS stack and BFS queue. It does not attempt to measure interpreter-specific bytes.

from collections import deque

Graph = dict[str, list[str]]


def peak_frontier_sizes(graph: Graph) -> tuple[int, int]:
    """Return the maximum DFS stack size and BFS queue size."""
    dfs_visited: set[str] = set()
    dfs_stack: list[str] = []
    max_dfs_size = 0

    # Iterate over every node so disconnected graphs are fully traversed.
    for start in graph:
        if start in dfs_visited:
            continue

        dfs_visited.add(start)
        dfs_stack.append(start)

        while dfs_stack:
            max_dfs_size = max(max_dfs_size, len(dfs_stack))
            node = dfs_stack.pop()

            for neighbor in graph.get(node, []):
                if neighbor not in dfs_visited:
                    # Mark on discovery to prevent duplicate stack entries.
                    dfs_visited.add(neighbor)
                    dfs_stack.append(neighbor)

    bfs_visited: set[str] = set()
    bfs_queue: deque[str] = deque()
    max_bfs_size = 0

    for start in graph:
        if start in bfs_visited:
            continue

        bfs_visited.add(start)
        bfs_queue.append(start)

        while bfs_queue:
            max_bfs_size = max(max_bfs_size, len(bfs_queue))
            node = bfs_queue.popleft()

            for neighbor in graph.get(node, []):
                if neighbor not in bfs_visited:
                    bfs_visited.add(neighbor)
                    bfs_queue.append(neighbor)

    return max_dfs_size, max_bfs_size


graph: Graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
    "D": ["B"],
    "E": ["B"],
    "F": ["C"],
    "G": ["C"],
}

print(peak_frontier_sizes(graph))  # Expected output: (3, 4)

Common Pitfalls

  • Do not claim that BFS always uses more memory or that DFS always uses less; graph structure determines the peaks.

  • Mark vertices as visited when discovered. Marking only when removed can place duplicate vertices in the frontier and increase auxiliary space to O(E).

  • Recursive DFS can exceed Python’s default recursion limit of roughly 1,000 nested calls; the iterative version avoids that issue.

  • A traversal must loop over all nodes to handle disconnected graphs.

  • When reporting memory, distinguish O(V) auxiliary space from O(V + E) total space including the adjacency list.

25

How can graph data structures improve cache locality?

Cache locality in graph processing can be improved by storing sparse graphs in compressed sparse row (CSR) format, where each vertex’s neighbors occupy a contiguous range of an array. Renumbering vertices, using compact integer identifiers, and choosing an adjacency matrix for dense graphs can further reduce pointer chasing and memory-access overhead.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model and Representations

The optimization depends on the graph and workload:

  • Directed or undirected: CSR supports both. For an undirected graph, store each edge in both directions.

  • Weighted or unweighted: Unweighted CSR stores neighbor IDs. Weighted CSR stores neighbor IDs and weights, preferably in separate contiguous arrays.

  • Sparse graphs: Represented as an adjacency list or CSR with O(V + E) space, where V is the number of vertices and E is the number of edges.

  • Dense graphs: An adjacency matrix uses O(V²) space but provides predictable row-major access.

Representation Neighbor storage Main trade-off
Dictionary of lists Separate, pointer-based lists per vertex Flexible, but allocations and pointer chasing reduce locality
CSR One contiguous neighbor array plus offsets Efficient traversal, but expensive updates
Adjacency matrix Contiguous matrix rows Efficient for dense graphs, wasteful for sparse graphs

Cache-Locality Optimizations

  • Use CSR for read-heavy graphs: offsets[v] through offsets[v + 1] - 1 identify all neighbors of v in one contiguous range.

  • Renumber and rebuild: Relabel vertices using graph-aware ordering, such as traversal order or community detection, then rebuild CSR. Grouping related vertices can make subsequently accessed rows closer in memory.

  • Use compact integer arrays: Machine-sized integer arrays avoid the pointer and object overhead of lists of Python integer objects.

  • Separate targets and weights: For weighted graphs, parallel arrays can avoid padding and keep frequently accessed target IDs compact.

  • Choose CSR by update frequency: Inserting an edge into CSR may require shifting O(E) entries. Dynamically changing graphs are often better represented with adjacency lists or another mutable structure.

  • Use matrices for dense graphs: Scanning one row is cache-friendly, although traversal becomes O(V²) rather than O(V + E).

CSR improves locality but does not change the asymptotic complexity of graph traversal.

Complexity

Approach Best time Average time Worst time Space
CSR construction and BFS O(V + E) O(V + E) O(V + E) O(V + E) including CSR
Dictionary adjacency-list BFS O(V + E) O(V + E) O(V + E) O(V + E) including adjacency lists
Adjacency-matrix BFS O(V²) O(V²) O(V²) O(V²)

For CSR-based traversal:

  • Time: Construction and traversal are O(V + E) in all cases.

  • Space, excluding the input: CSR uses O(V + E); the visited set, queue, and traversal output use O(V) additional space.

  • Space, including the input: O(V + E) overall.

  • Recursion stack: O(1) because the traversal is iterative.

Common Pitfalls

  • Confusing contiguity with global ordering: Each vertex’s neighbors are contiguous, but consecutive visited vertices may still be far apart. Rebuilding CSR after renumbering can help.

  • Forgetting disconnected components: BFS and DFS must start an unvisited traversal from every vertex.

  • Assuming visited can be omitted: Duplicate edges, self-loops, and cycles otherwise cause repeated processing.

  • Ignoring update costs: CSR is excellent for repeated traversals but costly for frequent insertions and deletions.

  • Using CSR for very dense graphs: An adjacency matrix may be simpler and more cache-efficient when nearly every possible edge exists.

  • Misrepresenting complexity: Better locality improves constants and cache misses; it does not reduce BFS or DFS below O(V + E).

26

How can memory usage be reduced in graph representations?

CSR (Compressed Sparse Row) and other compact representations can substantially reduce the memory overhead of storing a graph, especially when the graph is sparse. The best choice depends on graph density, whether it is weighted or directed, and which operations must remain fast.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Types and Representation Costs

Unless stated otherwise, this answer describes an undirected, unweighted graph represented as an adjacency list: dict[int, list[int]]. For a graph with V vertices and E undirected edges, the adjacency list stores 2E neighbor entries because each edge appears in both endpoint lists.

Representation Space Typical operation costs Best use
Adjacency list O(V + E) Neighbor scan: O(deg(v)) Sparse graphs
CSR arrays O(V + E) Neighbor scan: O(deg(v)) Large, mostly immutable sparse graphs
Edge list O(E) edge records Unsorted edge lookup: O(E) Streaming or batch processing
Adjacency matrix O(V²) entries Edge lookup: O(1) Dense graphs
Bitset matrix O(V² / w) machine words Bit lookup: O(1) Dense graphs and frequent membership tests

Here, w is the number of bits in a machine word. Add O(V) if an edge-list application must separately retain isolated vertices or other vertex metadata.

Compact Storage Techniques

  • Use CSR: Store neighbor IDs in one contiguous array and each vertex’s starting position in an offsets array. This removes per-vertex Python list and dictionary overhead.

  • Use primitive arrays: Store indices and offsets in fixed-width integer arrays instead of Python integer objects. array("q") stores signed long-long integers with a minimum item size of 8 bytes.

  • Remap string or object IDs: Convert arbitrary labels to consecutive integer IDs before constructing the graph. Retain the label-to-index mapping only when needed.

  • Separate fields: For weighted graphs, store neighbor IDs and weights in parallel arrays. This is usually more compact than lists of tuples.

  • Remove unnecessary edges: Deduplicate repeated edges and omit self-loops when the application semantics permit it.

  • Use edge lists or streaming construction: For graphs larger than memory, process edges from disk or a stream instead of constructing a complete adjacency list.

  • Choose bitsets for dense graphs: Packed bitsets reduce matrix storage but are usually unsuitable for sparse graphs.

  • Release the original representation: After conversion, discard the original lists when possible. Conversion has a temporary peak cost, so very large graphs may require edge-list or chunked construction.

Code Example

This converts an undirected adjacency list into CSR arrays without modifying the input:

from __future__ import annotations

from array import array


def build_csr(
    graph: dict[int, list[int]],
) -> tuple[array, array, dict[int, int]]:
    """Convert an undirected adjacency list into compact CSR arrays."""
    node_to_index = {
        node: index
        for index, node in enumerate(graph)
    }

    degrees = array("q", (len(neighbors) for neighbors in graph.values()))

    # offsets[index] is the first CSR position belonging to that vertex.
    offsets = array("q", [0])
    for degree in degrees:
        offsets.append(offsets[-1] + degree)

    total_entries = offsets[-1]
    neighbors = array("q", [0]) * total_entries
    cursor = array("q", offsets[:-1])

    for node, node_neighbors in graph.items():
        source = node_to_index[node]

        for neighbor in node_neighbors:
            target = node_to_index[neighbor]
            neighbors[cursor[source]] = target
            cursor[source] += 1

    return offsets, neighbors, node_to_index


graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1],
}

offsets, neighbors, node_to_index = build_csr(graph)
print(offsets.tolist(), neighbors.tolist(), node_to_index)
# Expected output: [0, 2, 4, 6] [1, 2, 0, 2, 0, 1] {0: 0, 1: 1, 2: 2}

For CSR vertex i, its neighbors occupy neighbors[offsets[i]:offsets[i + 1]]. Every neighbor ID must also be a key in a valid undirected adjacency list. The returned mapping associates original IDs with CSR indices and can be omitted when IDs are already contiguous from 0 to V - 1.

Step-by-step for the example:

  1. The degrees are [2, 2, 2], producing offsets [0, 2, 4, 6].

  2. Mapping 0 → 0, 1 → 1, and 2 → 2 converts the flattened lists to [1, 2, 0, 2, 0, 1].

  3. The slices [0:2], [2:4], and [4:6] recover each vertex’s neighbors.

Complexity and Edge Cases

  • CSR construction: Best and average time are O(V + E) with expected constant-time dictionary access. Under adversarial hash collisions, worst-case time is O(V² + VE).

  • CSR storage: The output uses O(V + E) space. Construction uses O(V) auxiliary space beyond the output; including the input graph and output, peak space remains O(V + E). There is no recursion stack.

  • CSR traversal: A complete traversal takes O(V + E) time and O(V) additional space for a visited set and an iterative stack or queue.

  • Empty graph: Produces offsets [0] and an empty neighbor array.

  • One isolated vertex: Produces offsets [0, 0].

  • Negative IDs: Are supported; the returned mapping preserves their relationship to CSR indices.

  • Already sorted input: Is accepted, and each vertex’s neighbor order is preserved.

  • Duplicates and self-loops: Are preserved; remove them separately if the graph must be simple.

  • Disconnected graphs and cycles: Are represented correctly, but traversals must use a visited set and start from every unvisited vertex.

Common Pitfalls and Interview Tips

  • Off-by-one errors: CSR requires V + 1 offsets, and vertex i ends at offsets[i + 1].

  • Integer overflow: Ensure offsets, remapped IDs, and weights fit the selected fixed-width types; similar overflow can occur in other languages.

  • Input mutation: The example only reads the adjacency list. Discard it after conversion only when the original representation is no longer needed.

  • Do not use an adjacency matrix for a sparse graph unless constant-time edge lookup justifies its O(V²) cost.

  • Do not forget the visited set when traversing disconnected or cyclic graphs.

  • Expect follow-up questions about CSR conversion, adjacency lists versus matrices, weighted layouts, and disconnected or cyclic traversal.

27

BFS vs Dijkstra shortest path difference

BFS finds the shortest path in unweighted graphs (or graphs where every edge has the same weight) by exploring level by level, while Dijkstra’s algorithm finds the shortest path in weighted graphs with non-negative weights by always expanding the currently known closest node using a priority queue.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Types and Representations

  • BFS applies to unweighted graphs (directed or undirected). Dijkstra applies to weighted graphs with non-negative edges (directed or undirected).

  • Common representations:

  • Adjacency list (dict[node, list] of neighbours): space O(V + E)

  • Adjacency matrix: space O(V²)

  • Edge list: space O(E)

  • BFS and Dijkstra are typically implemented with an adjacency list, so the complexities below assume O(V + E) space for the graph itself.

How Each Algorithm Works

  • BFS (Breadth-First Search): Starts at the source node, visits all neighbours at distance 1, then all neighbours at distance 2, and so on. The first time a node is dequeued, the path used to reach it has the fewest edges. Uses a FIFO queue (collections.deque).

  • Dijkstra’s Algorithm: Maintains a tentative distance for every node, initially infinity except the source (0). Repeatedly extracts the unvisited node with the smallest tentative distance (min-heap), then relaxes its outgoing edges. The first time a node is extracted, its distance is final.

Key Differences

Aspect BFS Dijkstra
Graph type Unweighted (or equal weights) Weighted, non-negative edges
Data structure Queue (FIFO) Min-heap / priority queue
Distance measure Number of edges (hops) Sum of edge weights
Time complexity O(V + E) — each node and edge visited once O((V + E) log V) — each node and edge processed, heap ops are log V
Space complexity O(V) for queue + visited (input not counted) O(V + E) with a lazy heap that keeps stale entries, or O(V) with a decrease-key heap, plus distances and visited (input not counted)
Precondition None No negative-weight edges
Typical use Grid maze, social degrees, word ladder Road networks, network delay, weighted routing

When to Use Which

  • Use BFS when every step has the same cost: unweighted graphs, grids with uniform movement cost, finding the minimum number of edges between nodes, bipartite checking, level-order traversal.

  • Use Dijkstra when edges have different non-negative costs: road maps with distances or travel times, network routing with latency, any weighted graph where you need the minimum total weight.

  • Do not use Dijkstra if negative weights exist; use Bellman-Ford (O(V·E)) or SPFA instead. For all-pairs shortest paths on dense graphs, consider Floyd-Warshall (O(V³)).

Step-by-Step Trace (Small Example)

Graph: A–(1)–B–(2)–C, A–(4)–C (undirected, weighted). Source = A.

BFS (treats all edges as weight 1): 1. Queue: [A], dist[A]=0 2. Dequeue A → enqueue B, C. dist[B]=1, dist[C]=1 3. Dequeue B → neighbour C already visited 4. Dequeue C → done. BFS reports A→C in 1 hop (incorrect for weighted shortest path).

Dijkstra: 1. Heap: [(0, A)], dist[A]=0 2. Pop A (0) → relax A→B (1), A→C (4). Heap: [(1, B), (4, C)] 3. Pop B (1) → relax B→C (1+2=3 < 4). Update dist[C]=3. Heap: [(3, C), (4, C)] 4. Pop C (3) → done. Shortest path A→B→C with total weight 3.

Common Pitfalls

  • Running BFS on a weighted graph and expecting the minimum-weight path; BFS minimizes hop count, not total weight.

  • Using Dijkstra with negative edges; it can produce wrong results because a node extracted from the heap may later be reached via a negative-weight edge that reduces its distance.

  • Forgetting the visited set in either algorithm, causing infinite loops on cycles or repeated work.

  • Using list.pop(0) for the BFS queue in Python; it is O(n). Always use collections.deque with popleft().

  • Not handling disconnected graphs: loop over all nodes and start a new search from each unvisited node if you need all components.

  • Interview follow-up: “How would you modify Dijkstra to also return the actual path?” (Maintain a parent dict during relaxation and reconstruct by backtracking from the target.) “What if the graph is a DAG?” (Topological order + single relaxation pass gives O(V + E).)

28

How do you implement Dijkstra’s algorithm for shortest paths in a weighted graph?

Dijkstra’s algorithm finds shortest paths from one source in a weighted graph by repeatedly finalizing the unsettled node with the smallest tentative distance. It requires non-negative edge weights; negative weights require Bellman-Ford instead.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The implementation uses a directed, weighted graph represented as an adjacency list:

dict[node, list[tuple[neighbor, weight]]]

For an undirected graph, add every edge in both directions.

Dijkstra’s algorithm maintains:

  • Distances: the best-known distance from the source to each node.

  • Previous nodes: predecessors used to reconstruct the shortest path.

  • Visited set: nodes whose shortest distance has been finalized.

  • Min-heap: the next node to process, ordered by tentative distance.

When a shorter route to a neighbor is discovered, its distance and predecessor are updated, and a new heap entry is inserted. A visited set prevents cycles from causing a node to be processed repeatedly.

Step-by-Step Example

Using the graph from the code example:

graph = {
    "A": [("B", 4.0), ("C", 2.0)],
    "B": [("C", 1.0), ("D", 5.0)],
    "C": [("B", 1.0), ("D", 8.0)],
    "D": [],
}

Source = “A”, Target = “D”. The algorithm proceeds as follows:

Step Popped (dist) Visited Distances (best known) Heap after pushes (dist, node) Notes
0 – {} A:0 (0, A) Initial state
1 A (0) {A} A:0, B:4, C:2 (2, C), (4, B) Relax A→B (4), A→C (2)
2 C (2) {A,C} A:0, B:3, C:2, D:10 (3, B), (4, B), (10, D) Relax C→B (2+1=3 < 4), C→D (2+8=10)
3 B (3) {A,C,B} A:0, B:3, C:2, D:8 (4, B), (8, D), (10, D) Relax B→D (3+5=8 < 10)
4 B (4) {A,C,B} unchanged (8, D), (10, D) Stale entry, ignored
5 D (8) {A,C,B,D} A:0, B:3, C:2, D:8 (10, D) Target reached, stop

Path reconstruction: D ← B ← C ← A → [“A”, “C”, “B”, “D”] with total distance 8.0.

Code Example

from heapq import heappop, heappush

Graph = dict[str, list[tuple[str, float]]]


def dijkstra_shortest_path(
    graph: Graph,
    source: str,
    target: str,
) -> tuple[list[str], float] | None:
    """Return the shortest source-to-target path and distance, or None."""
    # Validate the non-negative-weight precondition.
    for neighbors in graph.values():
        for _, weight in neighbors:
            if weight < 0:
                raise ValueError(
                    "Dijkstra's algorithm requires non-negative edge weights."
                )

    if source not in graph or target not in graph:
        return None

    if source == target:
        return [source], 0.0

    distances: dict[str, float] = {source: 0.0}
    previous: dict[str, str] = {}
    visited: set[str] = set()
    heap: list[tuple[float, str]] = [(0.0, source)]

    while heap:
        current_distance, node = heappop(heap)

        # Ignore outdated heap entries.
        if node in visited:
            continue

        visited.add(node)

        if node == target:
            break

        for neighbor, weight in graph[node]:
            if neighbor not in graph:
                raise ValueError("Every adjacent node must be a graph key.")

            candidate_distance = current_distance + weight

            if candidate_distance < distances.get(neighbor, float("inf")):
                distances[neighbor] = candidate_distance
                previous[neighbor] = node
                heappush(heap, (candidate_distance, neighbor))

    if target not in distances:
        return None

    # Reconstruct the path from target back to source.
    path = [target]
    while path[-1] != source:
        path.append(previous[path[-1]])

    path.reverse()
    return path, distances[target]


graph: Graph = {
    "A": [("B", 4.0), ("C", 2.0)],
    "B": [("C", 1.0), ("D", 5.0)],
    "C": [("B", 1.0), ("D", 8.0)],
    "D": [],
}

result = dijkstra_shortest_path(graph, "A", "D")
print(result)
# Expected output: (['A', 'C', 'B', 'D'], 8.0)

Complexity

Let V be the number of vertices and E the number of edges.

  • Time: O((V + E) log V) for the standard binary-heap analysis. Each edge is examined at most once when its source is finalized, and heap operations cost O(log V).

  • Space: O(V + E) auxiliary space. Distances, predecessors, and the visited set require O(V), while the lazy heap can contain O(E) entries. Including the input graph, total space is also O(V + E).

  • Recursion stack: O(1), because the implementation is iterative.

  • Best, average, and worst case: the standard bound is O((V + E) log V); early termination can reduce the actual work, but does not change the worst-case complexity.

Common Pitfalls

  • Negative edge weights: Dijkstra’s algorithm is invalid for them. The code raises ValueError instead.

  • Empty or missing vertices: If the source or target is absent, the function returns None.

  • One-node graph: Searching from a node to itself returns ([node], 0.0).

  • Disconnected graphs: An unreachable target returns None.

  • Duplicate edges: Every edge is considered; the shorter route wins automatically.

  • Cycles: With non-negative weights, revisiting finalized nodes cannot improve their shortest distances.

  • Input ordering: The order of adjacency-list entries does not affect the result because the min-heap determines processing order.

  • Forgetting visited: Without it, stale heap entries can cause unnecessary work and complicate cycle handling.

29

Bellman-Ford vs Dijkstra: when should you use Bellman-Ford?

Bellman–Ford computes single-source shortest paths even when edge weights are negative and can detect reachable negative cycles. Dijkstra’s algorithm is faster under its non-negative-weight requirement, but cannot safely handle negative edge weights.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Algorithm Differences

The comparison assumes a directed, weighted graph:

  • Bellman–Ford uses an edge list such as [(u, v, weight), ...].

  • Dijkstra uses an adjacency list such as {node: [(neighbor, weight), ...]}.

  • For an undirected graph, store each edge in both directions. However, any negative-weight undirected edge creates a negative cycle, because it can be traversed in both directions.

Property Bellman–Ford Dijkstra
Negative edge weights Supported, provided no reachable negative cycle exists Unsupported
Negative-cycle detection Supported Not supported
Precondition A source and weighted graph All relevant edge weights must be non-negative
Time Best O(V + E) with early termination; average/worst upper bound O(V · E) O((V + E) log V) with a binary heap
Auxiliary space O(V), excluding the input edge list O(V) for distances plus up to O(E) heap entries
Total space including graph input O(V + E) O(V + E)

These space bounds include queues, heaps, and auxiliary arrays. Neither implementation uses recursion, so there is no recursion-stack cost.

How Bellman–Ford Works

Bellman–Ford repeatedly relaxes every edge:

  1. Set the source distance to 0 and all other distances to infinity or None.

  2. For each edge (u, v, weight), update v when distance[u] + weight is smaller.

  3. Repeat this process for at most V - 1 passes.

  4. Check the edges once more. If another improvement is possible, a reachable negative cycle exists.

The V - 1 passes are sufficient because a shortest path without repeated cycles contains at most V - 1 edges.

For example, consider the ordered edges:

(0, 3, 10), (2, 3, 2), (1, 2, -3), (0, 1, 1)
State Distance to 0 Distance to 1 Distance to 2 Distance to 3
Initial 0 ∞ ∞ ∞
Pass 1 0 1 ∞ 10
Pass 2 0 1 -2 10
Pass 3 0 1 -2 0

The final distance to node 3 is 0, using the path 0 → 1 → 2 → 3.

Complexity and Preconditions

  • Bellman–Ford time: O(V · E) in the worst case because it performs up to V - 1 passes over E edges. Early termination can reduce a particular run to O(V + E).

  • Dijkstra time: O((V + E) log V) with a binary heap, making it preferable for large graphs with non-negative weights.

  • Bellman–Ford space: O(V) auxiliary space for distances and predecessors. The input edge list adds O(E) if the graph representation is included.

  • Dijkstra space: O(V + E) auxiliary space with a lazy binary heap, excluding the adjacency-list input.

Bellman–Ford can detect negative cycles only when they are reachable from the source. It does not require the entire graph to be connected.

When to Use Bellman–Ford

Use Bellman–Ford when:

  • Edge weights may be negative, such as financial adjustments, rebates, credits, or transactional costs.

  • You need to determine whether a reachable negative cycle exists.

  • Negative cycles would invalidate shortest-path assumptions.

  • The graph is small enough for O(V · E) to be acceptable.

Use Dijkstra when all edge weights are non-negative and performance is important. Examples include road networks with positive distances, unweighted graphs, and dependency networks modeled with zero or positive costs.

Code Example

from typing import Optional


def bellman_ford(
    vertex_count: int,
    source: int,
    edges: list[tuple[int, int, int]],
) -> tuple[list[Optional[float]], list[Optional[int]], bool]:
    """Return distances, predecessors, and reachable-negative-cycle status."""
    if vertex_count <= 0:
        raise ValueError("vertex_count must be positive")
    if not 0 <= source < vertex_count:
        raise ValueError("source must be a valid vertex")
    if any(
        not 0 <= start < vertex_count or not 0 <= end < vertex_count
        for start, end, _ in edges
    ):
        raise ValueError("edge contains an invalid vertex")

    distances: list[Optional[float]] = [None] * vertex_count
    predecessors: list[Optional[int]] = [None] * vertex_count
    distances[source] = 0

    # Relax all edges at most V - 1 times.
    for _ in range(vertex_count - 1):
        changed = False

        for start, end, weight in edges:
            start_distance = distances[start]
            if start_distance is None:
                continue

            candidate = start_distance + weight
            end_distance = distances[end]

            if end_distance is None or candidate < end_distance:
                distances[end] = candidate
                predecessors[end] = start
                changed = True

        if not changed:
            break

    # Any further improvement implies a reachable negative cycle.
    has_negative_cycle = False
    for start, end, weight in edges:
        start_distance = distances[start]
        if start_distance is None:
            continue

        end_distance = distances[end]
        if end_distance is None or start_distance + weight < end_distance:
            has_negative_cycle = True
            break

    return distances, predecessors, has_negative_cycle


distances, predecessors, has_negative_cycle = bellman_ford(
    4,
    0,
    [(0, 3, 10), (2, 3, 2), (1, 2, -3), (0, 1, 1)],
)

print(distances)             # [0, 1, -2, 0]
print(predecessors)          # [None, 0, 1, 2]
print(has_negative_cycle)   # False

Common Pitfalls

  • Using Dijkstra with negative weights: Dijkstra may finalize a node before a later negative edge could improve its distance.

  • Ignoring reachability: A negative cycle outside the source’s connected component is not reported by this implementation.

  • Undirected negative edges: Storing both directions makes such an edge a negative cycle.

  • Misreading unreachable vertices: None means the vertex was not reached; it is different from a reachable distance of infinity.

  • Edge-order dependence: Edge order affects how many passes are needed, but not the final result when no reachable negative cycle exists.

  • Other languages and overflow: Use a numeric type wide enough for the largest possible path cost.

Common interview follow-ups include implementing negative-cycle detection, explaining why V - 1 passes suffice, and contrasting Bellman–Ford with Dijkstra and Floyd–Warshall.

30

How does Floyd–Warshall compute all-pairs shortest paths?

The Floyd–Warshall algorithm computes the shortest-path distance between every pair of vertices in a weighted graph using dynamic programming. It is especially useful for dense graphs, negative edge weights, and all-pairs shortest-path queries.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

The algorithm models a directed, weighted graph using an adjacency list such as dict[node, list[(neighbor, weight)]]. Internally, it creates a V × V distance matrix.

  • distance[u][v] initially contains the direct edge weight from u to v.

  • distance[u][u] is initialized to 0.

  • Missing edges are initialized to infinity.

  • For an undirected graph, add every edge in both directions.

  • For an unweighted graph, assign every edge a weight of 1.

For each possible intermediate vertex k, it applies:

[ distance[i][j] = min(distance[i][j],\ distance[i][k] + distance[k][j]) ]

The question is whether reaching j through k is shorter than the currently known route from i to j.

Preconditions and Usage

  • Negative edges: Supported, provided the graph has no negative-weight cycle.

  • Negative cycles: Detectable because distance[v][v] becomes negative. No meaningful shortest path exists for vertices affected by such a cycle.

  • Disconnected graphs: Supported; unreachable pairs retain an infinite distance.

  • Ordinary cycles: Floyd–Warshall does not perform general cycle detection; it detects negative cycles through diagonal distances.

  • Typical uses: Network routing, dependency analysis, reachability, travel-cost matrices, and graphs containing negative edges.

For a sparse graph with non-negative weights, running Dijkstra from each vertex may be faster. Floyd–Warshall is usually preferable when the graph is dense or negative edges are present.

Approach Time Space When to use
Floyd–Warshall O(V³) O(V²) Dense graphs or negative edges
Dijkstra from every vertex O(V(V + E) log V) O(V²) for results Sparse, non-negative graphs

Complexity

  • Best, average, and worst-case time: O(V³). There are three nested loops over vertices, regardless of edge distribution.

  • Auxiliary space: O(V²) for the distance matrix.

  • Recursion stack: O(1) because the implementation is iterative.

  • Including the input: O(V² + E); for a simple graph, this is O(V²).

Example Walkthrough

For the directed edges A → B with weight 2, B → C with weight 3, and A → C with weight 10:

  1. Initially, distance[A][C] = 10.

  2. When k = B, the route A → B → C costs 2 + 3 = 5.

  3. The algorithm updates distance[A][C] to 5.

Code Example

from math import inf

type Graph = dict[str, list[tuple[str, float]]]


def floyd_warshall(graph: Graph) -> dict[str, dict[str, float]]:
    """Return all-pairs shortest-path distances for a directed weighted graph."""
    nodes = set(graph)
    for edges in graph.values():
        for neighbor, _ in edges:
            nodes.add(neighbor)

    distance = {
        source: {target: inf for target in nodes}
        for source in nodes
    }

    for node in nodes:
        distance[node][node] = 0.0

    for source, edges in graph.items():
        for target, weight in edges:
            distance[source][target] = min(
                distance[source][target], float(weight)
            )

    for intermediate in nodes:
        for source in nodes:
            for target in nodes:
                distance[source][target] = min(
                    distance[source][target],
                    distance[source][intermediate]
                    + distance[intermediate][target],
                )

    if any(distance[node][node] < 0 for node in nodes):
        raise ValueError("The graph contains a negative-weight cycle")

    return distance


graph = {
    "A": [("B", 2), ("C", 10)],
    "B": [("C", 3)],
    "C": [],
}

print(floyd_warshall(graph)["A"]["C"])  # 5.0

Common Pitfalls

  • Forgetting that Floyd–Warshall handles directed graphs by default; undirected edges must be inserted in both directions.

  • Initializing diagonal entries incorrectly; they must be 0, except when detecting a negative self-loop.

  • Using 0 instead of infinity for missing edges, which can create nonexistent paths.

  • Assuming Dijkstra supports negative edges; it does not.

  • Overlooking disconnected graphs; infinity correctly represents unreachable pairs.

  • Expecting useful shortest paths in a graph containing a negative-weight cycle; the implementation raises an error for this case.

31

What is the A* search algorithm in graph theory?

A* search is an informed graph-search algorithm that combines the cost already traveled with a heuristic estimate of the remaining cost. Under suitable conditions on the edge costs and heuristic, it finds a minimum-cost path in a weighted graph.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

A* maintains a frontier ordered by:

f(n) = g(n) + h(n)

  • g(n): the best-known cost from the start node to n.

  • h(n): the estimated cost from n to the goal.

  • f(n): the estimated total cost of a path through n.

For example, in a road network, g(n) might represent distance already traveled, while h(n) could be straight-line distance to the destination. When h(n) = 0, A* behaves like Dijkstra’s algorithm; a useful heuristic can reduce the number of nodes explored.

Preconditions and Optimality

The graph may be directed or undirected and is normally weighted, although unit edge costs are also valid.

  • Edge costs must be non-negative.

  • The heuristic should be admissible: it must never overestimate the remaining cost.

  • For graph search without reopening nodes, the heuristic should also be consistent:

h(n) <= edge_cost(n, neighbor) + h(neighbor)

  • The goal normally has h(goal) = 0.

With non-negative edge costs and a consistent heuristic, when a node is removed from the priority queue with its current best cost, that cost is optimal and the node can safely be added to the closed set. A merely admissible but inconsistent heuristic requires reopening previously closed nodes when a better path is found.

Graph Representation and Complexity

The usual representation is an adjacency list such as dict[node, list[(neighbor, cost)]]. The following bounds assume a simple graph and a binary-heap frontier:

  • Best-case time: O(1) when the start and goal are the same.

  • Average case: no standard tighter general bound exists; performance depends on heuristic quality and graph structure and can approach the worst case.

  • Worst-case time: O((V + E) log V). With a consistent heuristic, each node is expanded at most once and each edge is examined once; heap insertions and removals cost O(log V) in a simple graph.

  • Worst-case auxiliary space: O(V + E), excluding the input, for distance maps, parent pointers, the closed set, and heap entries. An iterative implementation has an O(1) recursion stack.

  • Best-case auxiliary space: O(1) for an immediate start-goal match.

  • Input space: O(V + E) for the adjacency list.

  • Total space including input: O(V + E).

In a tree-search formulation, A* can take O(b^d) time and O(b^d) auxiliary space in the worst case, where b is the branching factor and d is the solution depth.

Example Walkthrough

Consider directed edges A → B with cost 1, A → C with cost 4, B → C with cost 1, and C → D with cost 1. Use the consistent heuristic h(A) = 3, h(B) = 2, h(C) = 1, and h(D) = 0.

  1. Start at A: g(A) = 0, so f(A) = 3.

  2. Expand A: reach B with g(B) = 1 and f(B) = 3, and C with g(C) = 4 and f(C) = 5.

  3. Expand B: find a better route to C, giving g(C) = 2 and f(C) = 3.

  4. Expand C: reach D with g(D) = 3 and f(D) = 3.

  5. Expand D and reconstruct the path A → B → C → D, whose total cost is 3.

Common Pitfalls and Interview Tips

  • Inconsistent or overestimating heuristics can cause a non-optimal path; an admissible inconsistent heuristic requires reopening closed nodes.

  • Negative edge costs invalidate standard A* under these conditions; use Bellman–Ford or another algorithm designed for negative weights.

  • Check whether the goal has been removed from the priority queue, not merely discovered, before declaring success.

  • Forgetting the closed set can cause repeated expansion; cycles must not make the search loop indefinitely.

  • Empty graphs, missing start or goal nodes, and disconnected graphs need explicit handling. A start equal to the goal has a zero-cost path.

  • Watch for path-reconstruction off-by-one errors and missing parent pointers. In languages with fixed-width integers, ensure g and f calculations cannot overflow.

  • Do not mutate the adjacency list while searching.

  • A common follow-up asks how A* differs from Dijkstra: A* uses g + h, while Dijkstra uses only g.

34

Implement Greedy Best-First Search and compare to A*

Greedy Best-First Search is a graph traversal algorithm that always expands the node with the lowest heuristic estimate to the goal, using a priority queue ordered by the heuristic function h(n) only. A* improves on this by combining the actual path cost g(n) with the heuristic, using f(n) = g(n) + h(n), which guarantees an optimal path when the heuristic is admissible.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Greedy Best-First Search Works

The algorithm maintains a priority queue of frontier nodes sorted by their heuristic value h(n), which estimates the cost from the node to the goal. It pops the node with the lowest h(n), checks whether it is the goal, and expands its neighbors. Each unvisited neighbor is marked as visited and pushed onto the queue with its own heuristic value. Because it only considers the heuristic, it is fast but not guaranteed to find the shortest path.

  • Time complexity: O(b^m) worst case, where b is the branching factor and m is the maximum search depth. The heuristic directs the search, but in the worst case it explores the entire tree.

  • Space complexity: O(b^m) worst case, since the priority queue can hold all frontier nodes. In terms of graph size, the open and visited sets are bounded by O(V).

How A* Differs

A* evaluates nodes using f(n) = g(n) + h(n), where g(n) is the actual cost from the start node to the current node. This makes A* a best-first search over total estimated path cost rather than just the heuristic estimate.

  • Time complexity: O(b^m) worst case, same exponential bound as greedy search.

  • Space complexity: O(b^m) worst case for the open set; O(V) in terms of graph size.

  • Optimality: A* finds the optimal path if the heuristic is admissible (never overestimates the true cost). Greedy Best-First Search does not guarantee optimality.

Comparison

Property Greedy Best-First Search A* Search
Priority function h(n) f(n) = g(n) + h(n)
Optimal path No Yes, if heuristic is admissible
Speed Faster per node Slower per node
Memory O(b^m) O(b^m)
Best use case When speed matters more than optimality When the shortest path is required

Code Example

import heapq
from typing import Callable, Optional

def greedy_best_first_search(
    graph: dict[str, list[str]],
    start: str,
    goal: str,
    heuristic: Callable[[str], float],
) -> Optional[list[str]]:
    """
    Greedy Best-First Search expands the node with the lowest heuristic
    estimate to the goal. Returns the path or None if unreachable.
    """
    if start == goal:
        return [start]

    open_set = [(heuristic(start), start)]
    visited = {start}
    parent = {start: None}

    while open_set:
        _, node = heapq.heappop(open_set)

        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                heapq.heappush(open_set, (heuristic(neighbor), neighbor))

    return None


def a_star_search(
    graph: dict[str, list[str]],
    start: str,
    goal: str,
    heuristic: Callable[[str], float],
    edge_cost: Callable[[str, str], float] = lambda n1, n2: 1,
) -> Optional[list[str]]:
    """
    A* Search expands the node with the lowest f(n) = g(n) + h(n).
    Returns the optimal path or None if unreachable.
    """
    if start == goal:
        return [start]

    open_set = [(heuristic(start), 0, start)]
    closed_set = set()
    g_score = {start: 0}
    parent = {start: None}

    while open_set:
        _, g, node = heapq.heappop(open_set)

        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]

        if node in closed_set:
            continue
        closed_set.add(node)

        for neighbor in graph.get(node, []):
            if neighbor in closed_set:
                continue

            tentative_g = g + edge_cost(node, neighbor)
            if neighbor not in g_score or tentative_g < g_score[neighbor]:
                g_score[neighbor] = tentative_g
                parent[neighbor] = node
                heapq.heappush(open_set, (tentative_g + heuristic(neighbor), tentative_g, neighbor))

    return None


# Example: graph where greedy search takes a longer path
graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "D": ["Goal"],
    "C": ["Goal"],
}
# Admissible: no estimate exceeds the true remaining cost.
heuristic = {"A": 1.5, "B": 0.5, "C": 1, "D": 0.5, "Goal": 0}

# greedy_best_first_search(graph, "A", "Goal", lambda n: heuristic[n])
# -> ['A', 'B', 'D', 'Goal'] (cost 3, not optimal)

# a_star_search(graph, "A", "Goal", lambda n: heuristic[n], lambda n1, n2: 1)
# -> ['A', 'C', 'Goal'] (cost 2, optimal)

Common Pitfalls

  • Forgetting the visited/closed set: Without it, the search loops forever on cycles in directed or undirected graphs.

  • *Using an inadmissible heuristic in A:** If h(n) overestimates the true cost, A* is no longer guaranteed to find the optimal path.

  • Confusing greedy with A* priority: Greedy uses only h(n); A* uses g(n) + h(n). Mixing them up changes correctness guarantees.

  • Disconnected graphs: Both algorithms start from a single node. If the goal is in an unreachable component, they return None. Loop over all nodes only when the task requires full traversal, not pathfinding.

  • *Revisiting nodes in A:** A* must allow re-opening a node if a better g-score is found before it is closed. The implementation above handles this by skipping closed nodes after popping.

  • Interview follow-up: Expect questions on whether A* is optimal with an admissible heuristic, how to make a heuristic consistent, and when greedy search is preferred for speed.

35

How can A* search solve a Sudoku puzzle?

Adapt A* search by treating each valid partial Sudoku grid as a state and each legal digit placement as a cost-1 edge. An admissible heuristic such as the number of empty cells guides the search, while minimum remaining values (MRV) reduces branching by expanding the most constrained cell first.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Modeling Sudoku as a Graph

The Sudoku state graph has these properties:

  • Directed: placing a digit creates a child state, but the reverse placement is not automatically allowed.

  • Unweighted: every digit placement costs one action.

  • Implicit adjacency list: neighbors are generated on demand rather than storing every possible transition.

  • State representation: an immutable 81-element tuple containing 0 for empty cells and 1 through 9 for filled cells.

  • Goal state: a complete grid containing no zeros.

An explicit adjacency-list representation, dict[node, list], would require O(V + E) space, where V is the number of valid partial grids and E is the number of legal digit-placement transitions. The implementation below generates neighbors implicitly.

Heuristic and Search Strategy

Use:

h(state) = number of empty cells

This heuristic is admissible because each remaining cell requires at least one placement. It is also consistent: after placing one digit, the cost increases by one while the heuristic decreases by one, so h(state) ≤ 1 + h(neighbor).

MRV is a search-ordering strategy rather than part of the heuristic. At each expansion, select the empty cell with the fewest legal digits. If any empty cell has no legal digit, the branch is a dead end.

A small trace is:

  1. The initial puzzle has 51 empty cells, so h = 51 and f = g + h = 51.

  2. MRV selects an empty cell with only two legal digits.

  3. Placing one digit creates a child with g = 1 and h = 50, giving f = 51.

  4. Search continues until it reaches a child with h = 0, which is the goal.

Complexity and Alternatives

  • Best case: O(d log(d + 1)), where d is the number of empty cells, if search follows a solution with constant branching.

  • Average case: instance-dependent; there is no standard average distribution for arbitrary Sudoku puzzles.

  • Worst case: O((V + E) log V) with a binary heap. For Sudoku, the reachable state space can be exponential in the number of blanks.

  • Auxiliary space: O(V + E) including the heap, closed set, and best_cost dictionary. There is no recursion stack. The input puzzle is not counted; it adds a constant 81 cells for standard Sudoku.

Approach Time Space When to use
Brute-force backtracking Worst O(9^d) O(d) including the recursion stack Simpler implementation and lower memory usage
A* with a binary heap Worst O((V + E) log V) O(V + E) Graph-search framework or a stronger admissible heuristic

For standard Sudoku, MRV-based backtracking is often more memory-efficient than A. A becomes more attractive when using stronger admissible lower bounds, constraint propagation, or pattern databases.

Code Example

from heapq import heappop, heappush

type State = tuple[int, ...]
type QueueItem = tuple[int, int, int, State]


def solve_sudoku(puzzle: str) -> str:
    """Solve a 9x9 Sudoku puzzle using A* search with MRV."""
    text = "".join(puzzle.split())
    if len(text) != 81 or any(ch not in ".0123456789" for ch in text):
        raise ValueError("Puzzle must contain exactly 81 valid characters.")

    initial: State = tuple(
        0 if char == "." else int(char) for char in text
    )

    def legal_values(state: State, position: int) -> tuple[int, ...]:
        row, column = divmod(position, 9)
        box_row = (row // 3) * 3
        box_column = (column // 3) * 3

        used = set(state[row * 9:(row + 1) * 9])
        used.update(state[column::9])
        used.update(
            state[(box_row + dr) * 9 + box_column + dc]
            for dr in range(3)
            for dc in range(3)
        )
        return tuple(value for value in range(1, 10) if value not in used)

    # Validate the original givens.
    for position, value in enumerate(initial):
        if value == 0:
            continue

        row, column = divmod(position, 9)
        box_row = (row // 3) * 3
        box_column = (column // 3) * 3

        row_values = initial[row * 9:(row + 1) * 9]
        column_values = initial[column::9]
        box_values = [
            initial[(box_row + dr) * 9 + box_column + dc]
            for dr in range(3)
            for dc in range(3)
        ]

        if (
            row_values.count(value) > 1
            or column_values.count(value) > 1
            or box_values.count(value) > 1
        ):
            raise ValueError("The puzzle contains conflicting givens.")

    blank_count = sum(value == 0 for value in initial)
    frontier: list[QueueItem] = [(blank_count, 0, 0, initial)]
    closed: set[State] = set()
    best_cost: dict[State, int] = {initial: 0}
    serial = 0

    while frontier:
        _, negative_cost, _, state = heappop(frontier)
        if state in closed:
            continue

        closed.add(state)
        cost = -negative_cost

        options: dict[int, tuple[int, ...]] = {}
        dead_end = False
        for position, value in enumerate(state):
            if value == 0:
                values = legal_values(state, position)
                if not values:
                    dead_end = True
                    break
                options[position] = values

        if dead_end:
            continue
        if not options:
            return "\n".join(
                "".join(str(state[row * 9 + column]) for column in range(9))
                for row in range(9)
            )

        # Expand the most constrained cell first.
        position = min(options, key=lambda index: len(options[index]))

        for digit in options[position]:
            child = state[:position] + (digit,) + state[position + 1:]
            if child in closed:
                continue

            child_cost = cost + 1
            previous_cost = best_cost.get(child)
            if previous_cost is not None and previous_cost <= child_cost:
                continue

            best_cost[child] = child_cost
            child_blanks = sum(value == 0 for value in child)
            serial += 1

            # Negative cost favors deeper states when f-values tie.
            heappush(
                frontier,
                (child_cost + child_blanks, -child_cost, serial, child),
            )

    raise RuntimeError("The Sudoku puzzle has no solution.")


print(solve_sudoku(
    "530070000600195000098000060800060003400803001"
    "700020006060000280000419005000080079"
))
# Expected output:
# 534678912
# 672195348
# 198342567
# 859761423
# 426853791
# 713924856
# 961537284
# 287419635
# 345286179

Common Pitfalls

  • Weak heuristic: The empty-cell heuristic is safe but does not indicate which digit is correct. A stronger heuristic must remain admissible; simply summing candidate counts can overestimate the remaining work.

  • Ignoring MRV: Always filling the first empty cell causes unnecessary branching.

  • Missing validation: Duplicate givens must be rejected before searching.

  • Unbounded memory: A* may retain many frontier states, so MRV backtracking is often preferable for ordinary Sudoku puzzles.

  • Common follow-up questions: Interviewers may ask why the heuristic is admissible, how an unsatisfiable puzzle is handled, or how constraint propagation and DLX differ from A*.

36

Where are graphs used in real-world systems?

Graph theory models systems as vertices connected by edges, making it useful for routing, dependency management, network analysis, recommendations, and scheduling. The appropriate graph type and algorithm depend on whether relationships are directed, weighted, acyclic, or cyclic.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Types and Representations

  • Directed graph: Edges have direction, such as A → B. Common for dependencies, web links, and task scheduling.

  • Undirected graph: Edges connect nodes both ways, such as friendships or physical roads.

  • Weighted graph: Edges have costs, distances, capacities, or strengths.

  • Unweighted graph: Every edge has equal cost.

  • DAG (directed acyclic graph): A directed graph without cycles; useful for prerequisites and build systems.

  • Adjacency list: dict[node, list] representation using O(V + E) space.

  • Adjacency matrix: An n × n matrix using O(V²) space, but offering constant-time edge lookup.

  • Edge list: A list of (source, destination) or (source, destination, weight) tuples using O(E) space.

Here, V is the number of vertices and E is the number of edges.

Real-World Applications

Application Graph model Typical algorithms
Road navigation and maps Weighted, usually undirected graph Dijkstra, A*, Floyd-Warshall
Social networks Directed or undirected graph BFS, DFS, community detection
Dependency and build systems Directed acyclic graph Topological sort
Internet and telecommunications Weighted graph Shortest paths, minimum spanning trees, max flow
Recommendation systems Weighted bipartite graph Similarity search, path finding
Task and resource scheduling Directed graph or state graph Topological sort, BFS, constraint solving
Fraud detection Transaction graph Anomaly detection, community detection
Biology Molecular interaction graph Graph search, clustering, network analysis

For example, a map can represent intersections as vertices and roads as weighted edges. A package manager can represent packages as vertices and dependencies as directed edges, allowing topological sorting to determine installation order.

Algorithm Complexity

Algorithm Time Space Reason and preconditions
BFS/DFS O(V + E) O(V) auxiliary Each vertex and edge is processed once; disconnected graphs require an outer loop over all vertices
Dijkstra with binary heap O((V + E) log V) O(V + E) total Edge relaxation uses heap operations; requires non-negative weights
Bellman-Ford O(V × E) O(V) auxiliary Every edge is relaxed up to V - 1 times; detects negative cycles
Floyd-Warshall O(V³) O(V²) total It computes all-pairs shortest paths
Kruskal O(E log E) O(V + E) total Edges are sorted, then selected using union-find
Prim O(E log V) O(V + E) total A frontier heap grows the minimum spanning tree
Topological sort O(V + E) O(V) auxiliary Requires a DAG and processes every vertex and edge

Auxiliary space excludes the input representation. Including the adjacency list, traversal algorithms use O(V + E) total space.

Common Pitfalls

  • Forgetting to maintain a visited set can cause infinite loops in cyclic graphs.

  • Traversing only one start vertex misses components in disconnected graphs.

  • Using Dijkstra with negative edge weights produces incorrect results; use Bellman-Ford instead.

  • Topological sorting cannot be applied to graphs containing cycles.

  • Choosing an adjacency matrix for a sparse graph wastes O(V²) space.

  • Removing an edge from an undirected adjacency list requires removing both directions.

  • Interviewers commonly ask how the graph type changes for roads, dependencies, friendships, and recommendations, and which algorithm you would select.

37

What are practical uses of DFS versus BFS in graph problems?

Breadth-First Search (BFS) explores a graph level by level, while Depth-First Search (DFS) follows one branch as deeply as possible before backtracking. BFS is usually preferred for shortest paths in equal-cost graphs, whereas DFS is useful for connected components, cycle detection, topological sorting, exhaustive search, and backtracking.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

Algorithm Data structure Exploration order Typical use
BFS Queue, commonly collections.deque Nodes in increasing distance from the start Shortest paths in equal-cost graphs
DFS Stack or recursion One path at a time before backtracking Components, cycle detection, backtracking

Both algorithms maintain a visited set so that each node is processed only once. An iterative DFS uses an explicit stack and does not consume Python’s recursion stack.

Practical Uses

The examples use an undirected, unweighted graph represented as an adjacency list, dict[node, list[node]]. For a directed graph, each list contains only outgoing edges. For a weighted graph, each list can contain (neighbor, weight) pairs. In every representation, the adjacency list occupies O(V + E) space.

Problem Preferred approach Reason
Find a shortest route when every edge has equal cost BFS Nodes are discovered in increasing hop distance from the start
Find minimum moves in a puzzle or state graph BFS Every transition has equal cost
Identify connected components DFS or BFS Both find every vertex reachable from each unvisited start
Detect cycles in a directed graph DFS with three colors Tracks unvisited, active, and finished vertices
Detect cycles in an undirected graph DFS with parent tracking or union-find Distinguishes a parent edge from a genuine cycle
Produce a topological ordering DFS post-order or Kahn’s algorithm Requires a directed acyclic graph
Exhaustively explore a maze or solution space DFS with backtracking Explores one route deeply before trying alternatives
Check whether a graph is bipartite BFS or DFS with two colors Assigns alternating colors across every edge

For weighted graphs, BFS minimizes the number of edges, not their total weight. Use Dijkstra’s algorithm instead when all edge weights are non-negative.

How Traversal Differs

Consider an undirected graph with the edges A-C, A-B, B-D, C-F, D-E, and E-F.

  1. DFS can follow A-B-D-E-F before returning to explore A-C. The exact branch depends on adjacency order and whether the implementation uses recursion or a stack.

  2. BFS discovers C and B at distance 1 from A.

  3. On the next level, it discovers F through C and D through B.

  4. It then discovers E at distance 3.

Thus, BFS can establish the shortest path A-C-F, while DFS can find a valid path but does not generally guarantee the shortest one.

Complexity and Preconditions

Let V be the number of vertices and E the number of edges.

Operation Best Average Worst Auxiliary space
Full DFS or BFS O(V + E) O(V + E) O(V + E) O(V)
BFS shortest path O(1) when start equals goal O(V + E) O(V + E) O(V)
  • Time: Each vertex is processed once, and each adjacency-list entry is examined once. An undirected edge appears at both endpoints, so both entries may be examined.

  • Auxiliary space: The visited set and stack or queue contain O(V) entries. Only shortest-path BFS also uses an O(V) predecessor map for path reconstruction.

  • Input storage: The adjacency list occupies O(V + E) space. Including the input, total space is O(V + E).

  • Directed cycle detection takes O(V + E) time and O(V) auxiliary space.

  • Topological sorting takes O(V + E) time and O(V) auxiliary space and requires a DAG.

  • Dijkstra’s algorithm with a binary heap takes O((V + E) log V) time and O(V) auxiliary space and requires non-negative edge weights.

Interview Tips

  • Use BFS when the result must minimize edge count and all edges have equal cost.

  • Use DFS when the task needs exhaustive exploration, backtracking, finishing order, or structural analysis.

  • Always maintain a visited set; on a cyclic graph, omitting it can cause an infinite traversal.

  • For disconnected graphs, loop over every vertex when the task must process all components.

  • An empty graph produces no components, while a one-vertex graph produces one component and a one-element shortest path when start equals goal.

  • Duplicate adjacency entries are harmless under the visited-set rule, although they can cause redundant scanning.

  • Negative vertex labels do not affect traversal; negative edge weights do matter when finding a minimum-weight path.

  • Recursive DFS needs O(V) recursion-stack space and can exceed Python’s default recursion limit, so an explicit stack is safer for large graphs.

  • Common follow-up questions include shortest paths, cycle detection, topological sorting, bipartite checking, and the space cost of the queue or recursion stack.

38

How do social networks use graphs for friend suggestions and recommendations?

Social networks model users, content, groups, and interactions as a graph, allowing the system to discover relationships, generate candidates, and rank recommendations. In practice, graph signals are usually combined with content-based filtering, collaborative filtering, and business rules.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model

A social graph contains:

  • Vertices: users, posts, products, groups, or events.

  • Edges: friendships, follows, likes, shares, messages, or co-memberships.

  • Weights: interaction frequency, recency, or strength when edges are weighted.

Different features use different graph types:

  • Friendship graph: undirected and unweighted; a mutual friendship creates edges in both directions.

  • Follow graph: directed because following is not necessarily reciprocal.

  • Interaction graph: usually directed and weighted to distinguish likes, comments, and shares.

The example uses an undirected, unweighted friendship graph represented as an adjacency list: dict[node, list]. With (V) vertices and (E) adjacency entries:

  • Adjacency-list storage uses (O(V + E)) space.

  • An adjacency matrix uses (O(V^2)) space.

  • An edge list uses (O(E)) space.

Recommendations and Product Features

A typical recommendation pipeline works as follows:

  1. Generate candidates: Retrieve friends-of-friends, members of shared communities, users connected through popular interactions, or predicted connections.

  2. Compute graph features: Count mutual connections, measure shortest-path distance, identify shared communities, and calculate interaction strength.

  3. Rank candidates: Combine graph signals with content similarity, popularity, recency, and personalization.

  4. Filter and diversify: Remove blocked, duplicate, low-quality, or overly similar recommendations.

  5. Learn from feedback: Update rankings when users accept, ignore, or hide recommendations.

Other graph-powered features include:

  • Feed ranking: Personalized PageRank propagates preferences over a user-content interaction graph. With (K) iterations, a sparse implementation takes (O(K(V+E))) time and (O(V)) auxiliary space.

  • Community detection: Connected clusters can represent schools, workplaces, or interest groups.

  • Link prediction: Missing edges are predicted from shared neighbors, communities, and behavioral similarity.

  • Reachability and moderation: Shortest-path distances measure connection closeness, while centrality, PageRank, and propagation models identify influential accounts. Dense or repetitive interaction patterns can help flag coordinated behavior.

  • Shortest-path suggestions: On a weighted interaction graph, Dijkstra’s algorithm finds minimum-cost paths when all weights are non-negative. Interpreting weights as dissimilarity makes a lower-cost path indicate a stronger connection.

Complexity and Design Choices

Approach Time Auxiliary space Reason When to use
All-pairs shortest paths using BFS (O(V(V+E))) (O(V)) Run BFS from every vertex, scanning each adjacency list per source Offline global distance analysis
Local friend-of-friend BFS (O(V+E)) (O(V)) Each reachable vertex is queued once and each scanned edge is processed once Suggestions during a request
Dijkstra with a binary heap (O((V+E)log V)) (O(V+E)) worst case Relax edges and perform logarithmic heap operations; a lazy heap may hold (O(E)) entries Weighted connection strength
PageRank for (K) iterations (O(K(V+E))) (O(V)) Perform (K) sparse passes over vertices and edges using score arrays Ranking content or influential nodes

The listed space is auxiliary and excludes the input graph and returned recommendations. Including the adjacency list, total storage is (O(V+E)). Large platforms commonly precompute communities, candidate lists, and graph embeddings instead of running unrestricted traversals for every request.

Code Example

The following function suggests users exactly two friendship edges away, such as a friend of a friend. It uses collections.deque for BFS and a visited set to handle cycles and duplicate neighbors.

from collections import deque


def suggest_friends(
    graph: dict[str, list[str]],
    user: str,
    limit: int = 5,
) -> list[str]:
    """Return up to limit friends-of-friends for an undirected graph."""
    if limit <= 0 or user not in graph:
        return []

    visited = {user}
    queue = deque([(user, 0)])
    suggestions: list[str] = []

    while queue:
        current, distance = queue.popleft()

        # Do not search beyond the requested distance.
        if distance >= 2:
            continue

        for neighbor in graph.get(current, []):
            if neighbor == user or neighbor in visited:
                continue

            visited.add(neighbor)

            if distance == 1:
                suggestions.append(neighbor)
            else:
                queue.append((neighbor, distance + 1))

    return suggestions[:limit]


social_graph = {
    "A": ["B", "C", "B"],  # Duplicate neighbor
    "B": ["A"],
    "C": ["A"],
    "D": ["B", "C"],
    "E": [],              # Disconnected user
}

print(suggest_friends(social_graph, "A"))  # Expected output: ['D']

Example Walkthrough

  1. Start at A with distance 0 and mark A as visited.

  2. Discover B and C at distance 1; skip the duplicate B.

  3. Expand B and discover D at distance 2.

  4. Expand C; D is already visited, so it is not duplicated.

  5. E is unreachable, and D is returned as the only suggestion.

Common Pitfalls

  • Cycles and duplicate edges: Always use a visited set and avoid counting the same edge repeatedly.

  • Disconnected components: Global traversals must loop over every vertex; a request-local BFS naturally visits only the starting user’s component.

  • Directed relationships: Treating a follow as a mutual friendship produces incorrect mutual-friend features.

  • Weight assumptions: Dijkstra requires non-negative weights; Bellman–Ford handles negative weights and can detect negative cycles.

  • Input mutation: Do not modify adjacency lists while traversing them.

  • Edge cases: An empty graph, missing user, or one-user graph returns no suggestions. Duplicate neighbors are ignored, disconnected users are omitted, and cycles terminate correctly. Negative numbers and pre-sorted input are not applicable to this unweighted, string-ID example.

  • Ranking quality: Graph proximity alone can reinforce popularity bias or expose sensitive relationships, so privacy, fairness, and diversity checks are important.

39

How do GPS navigation systems use graph algorithms?

A GPS navigation system represents roads as a directed, weighted graph and uses shortest-path algorithms to calculate routes. In production, it may also use specialized indexes and live traffic data to reduce search time and improve route quality.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model

For this answer, the graph is:

  • Directed because one-way streets and turn restrictions make travel asymmetric.

  • Weighted because each edge can represent travel time, distance, tolls, or a combination.

  • Stored as an adjacency list, represented by dict[node, list[(neighbor, weight)]].

For example, an edge ("B", 4.5) means that the current node has a directed connection to "B" with a weight of 4.5.

Representation Space Typical operation
Adjacency list O(V + E) Traverse neighbors in O(degree)
Adjacency matrix O(V²) Check an edge in O(1)
Edge list O(V + E) Find an edge in O(E) without another index

An adjacency list is usually practical for road networks because maps are sparse: most intersections are not directly connected to every other intersection.

Algorithms Used by GPS

  • Dijkstra’s algorithm: Finds the minimum-weight route when all edge weights are non-negative. Travel times, distances, and tolls satisfy this requirement.

  • A* search: Uses an admissible and consistent estimate of the remaining distance, such as straight-line distance, to explore fewer intersections than Dijkstra while preserving optimality.

  • Dynamic rerouting: When traffic changes, edge weights are updated and the route is recalculated. Closing a road is modeled by removing its edge rather than assigning it a negative weight.

  • Connectivity analysis: Traversing every node identifies unreachable areas and disconnected components.

  • Map matching: Compares the GPS trace with possible roads in the graph to determine which road the vehicle is likely following.

Dijkstra’s algorithm has the following complexity for an adjacency-list graph:

Case Time
Best O((V + E) log V)
Average O((V + E) log V)
Worst O((V + E) log V)

The heap supports edge relaxations and frontier operations efficiently. Total space is O(V + E), including the input graph, distances, predecessors, and the lazy heap.

Common Pitfalls

  • Ignoring directionality: Adding both directions for a one-way street produces invalid routes.

  • Using negative weights: Dijkstra requires non-negative edge weights; negative travel costs are invalid.

  • Forgetting stale heap entries: A node can appear in the heap multiple times after its distance improves.

  • Assuming the graph is connected: An unreachable destination returns None; graph-wide traversals must start from every unvisited node.

  • Ignoring duplicates: Repeated edges are valid alternatives, and relaxation keeps the cheapest route.

  • Edge cases: An empty graph returns None; when start == goal, the result is ([start], 0.0); cycles are safe with non-negative weights.

  • Ignoring turn restrictions: Real navigation graphs may require separate nodes or edge costs for restricted turns.

Common follow-up questions ask why Dijkstra requires non-negative weights, how A* differs, how traffic changes affect routing, and how production systems scale to large road networks.

40

What is graph embedding, and how is it used in machine learning?

A graph embedding is a learned vector representation of a graph’s nodes, edges, or entire structure. It transforms sparse relational data into vectors that machine-learning models can use for tasks such as node classification, link prediction, recommendation, clustering, and similarity search.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Type and Representation

A graph is commonly written as (G=(V,E)), where (V) is the set of nodes and (E) is the set of relationships:

  • Directed or undirected: Edges may represent one-way relationships such as “follows” or two-way relationships such as “is connected to.”

  • Weighted or unweighted: Each edge may contain a numeric weight, such as transaction amount, distance, or interaction frequency.

  • Node and edge features: Nodes can include attributes such as age or product category, while edges can include attributes such as relationship type.

Common representations and their full storage costs are:

Representation Space Main Characteristic
Adjacency list dict[node, list] (O(V+E)) Efficient for sparse graphs
Adjacency matrix (O(V^2)) Fast edge lookup, but wasteful for sparse graphs
Edge list (O(E)) Compact, but repeated neighbor lookups may be slower

An adjacency list is usually the best choice for large, sparse machine-learning graphs. A directed edge occupies one adjacency entry, while an undirected edge normally occupies two—one in each endpoint’s list.

How Graph Embedding Works

Given a graph and optional features, an encoder produces vectors such as:

  • Node embedding: (z_v in mathbb{R}^d) for every node.

  • Edge embedding: A vector describing a relationship between two nodes.

  • Graph embedding: A pooled vector representing the entire graph.

The learned vectors should place structurally or semantically similar nodes near one another. Common methods include:

  • Random-walk methods, such as node2vec and DeepWalk: Generate node-context pairs from walks and learn vectors with a skip-gram-style objective.

  • Matrix factorization: Factorize an adjacency matrix so related nodes obtain similar vectors.

  • Graph neural networks: Aggregate information from neighboring nodes to produce context-aware embeddings.

  • Graph autoencoders: Reconstruct graph structure or features to train self-supervised embeddings.

A graph embedding is different from a mathematical planar embedding, which draws a graph on a surface without crossing edges.

Machine-Learning Applications

  • Node classification: Predict a label for one node, such as classifying a transaction as fraudulent in a directed transaction graph.

  • Link prediction: Score missing relationships between nodes, such as predicting which users may become friends.

  • Recommendation systems: Represent users and items as vectors in a user-item bipartite graph, then predict preferences from vector similarity.

  • Clustering and community detection: Group nodes whose embeddings are close.

  • Similarity search: Find structurally similar users, products, molecules, or networks.

  • Graph classification: Pool node embeddings into one vector and predict properties of the entire graph.

For example, in an undirected, weighted user-item graph, user and item embeddings can support nearest-neighbor recommendations based on learned purchasing relationships.

Complexity

Let (V) be the number of nodes, (E) the number of edges, (d) the embedding dimension, ® the number of walks per node, and (l) the walk length. Unless noted otherwise, space below excludes the input graph and fixed model parameters while counting generated outputs and auxiliary structures.

Operation Time Space Reason
Build adjacency list (O(V+E)) (O(V+E)) Each directed edge creates one entry; each undirected edge creates two
DFS or BFS over all components (O(V+E)) (O(V)) auxiliary A visited set records processed nodes; input excluded
Generate node2vec walks (O(Vrl)) (O(Vrl)) if stored Each of (Vr) walks contains (O(l)) nodes
Store node embeddings (O(Vd)) (O(Vd)) output One (d)-dimensional vector per node
Store edge embeddings (O(Ed)) (O(Ed)) output One (d)-dimensional vector per edge
Store a graph-level embedding (O(d)) (O(d)) output One vector represents the graph
Representative GNN layer (O((V+E)d)) (O(Vd)) activations Simple aggregation processes edges and transforms node states
Pool a graph with streaming mean or sum (O(Vd)) (O(d)) output Existing node embeddings are read without being copied

The DFS/BFS bounds are the same in the best, average, and worst cases. Hash-table neighbor lookup is expected (O(1)) but can degrade toward (O(V)) under pathological collisions. Training cost depends on the encoder, batch size, negative sampling, and number of GNN layers, so it cannot be specified universally.

Common Pitfalls

  • Ignoring direction or weights: Converting a directed graph into an undirected one can introduce false relationships.

  • Ignoring disconnected components: Isolated nodes still need embeddings, and ordinary traversals should start an outer loop over every node.

  • Misusing visited sets: DFS/BFS needs a visited set, but random walks may revisit nodes intentionally, and GNN message passing follows the model architecture rather than a global visited set.

  • Confusing adjacency with similarity: Two nodes can be close in embedding space because of shared features even if they lack direct edges.

  • Data leakage: Features derived from future edges or test labels can make evaluation results unrealistic.

  • Ignoring scale: Dense matrices become impractical for very large graphs; adjacency lists or sparse matrix formats are usually preferable.

41

What is the Min-Cut Max-Flow Theorem in network flow problems?

The Min-Cut Max-Flow Theorem states that the maximum feasible flow from a source to a sink equals the minimum capacity of any source–sink cut. This equivalence gives an optimality certificate and connects maximum-flow algorithms with the extraction of a minimum cut.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Network Model

Consider a directed, weighted capacity network:

  • The source is s, and the sink is t, with s != t.

  • Each directed edge has a nonnegative capacity.

  • A feasible flow respects edge capacities and flow conservation at intermediate vertices.

  • A cut (S, T) partitions the vertices so that s ∈ S and t ∈ T.

The capacity of a cut is:

cut_capacity(S, T) = sum of capacities of all edges directed from S to T

Only edges crossing from S to T contribute to directed cut capacity.

The theorem is stated for directed arcs. An undirected edge of capacity c can be modeled by opposite arcs of capacity c, with simultaneous opposite flows canceled so the net flow respects the shared capacity.

Relevant edge cases include:

  • Empty or single-vertex input: No valid distinct source–sink instance exists.

  • Parallel edges: They may be stored separately or combined by summing their capacities.

  • Negative capacities: These fall outside the standard flow model.

  • Input ordering: Vertex or adjacency-list order, including already sorted input, does not affect the theorem.

  • Disconnected graphs: If no s-to-t path exists, maximum flow and minimum-cut capacity are both 0.

  • Cycles: Directed cycles are allowed and do not invalidate the theorem.

Core Theorem and Why It Holds

For every feasible flow f and every source–sink cut (S, T):

flow_value(f) ≤ cut_capacity(S, T)

Therefore:

maximum_flow(s, t) = minimum_cut_capacity(s, t)

The result follows from two complementary observations:

  1. Every cut is an upper bound.
    The net flow leaving S equals the flow value. Net flow is at most the total capacity of edges directed from S to T; flow crossing backward from T to S can only reduce it.

  2. A maximum flow produces an equal-capacity cut.
    After computing a maximum flow, let S contain all vertices reachable from s in the residual graph, and let T contain the remaining vertices. Since the flow is maximum, t is not reachable. Every original edge from S to T is saturated, and the cut capacity equals the flow value.

This also explains why augmenting-flow algorithms terminate: while an augmenting path exists in the residual graph, the flow is not yet maximum.

Small Example

Consider these directed capacities:

  • s → a: 2

  • s → b: 1

  • a → b: 1

  • a → t: 1

  • b → t: 2

A feasible flow of value 3 is:

  • s → a → t: 1

  • s → a → b → t: 1

  • s → b → t: 1

For S = {s, a, b} and T = {t}, the cut capacity is:

capacity(a → t) + capacity(b → t) = 1 + 2 = 3

Thus, the maximum flow and minimum cut both have value 3.

Significance and Applications

  • Optimality certificate: A feasible flow and a cut with equal value prove both are optimal.

  • Capacity planning: The minimum cut identifies a current bottleneck, although upgrading only one of several minimum cuts may not increase the maximum flow.

  • Network reliability: If edge-failure costs equal capacities, the minimum cut identifies a cheapest set of failures that disconnects the source from the sink.

  • Edge-disjoint paths: With unit edge capacities, integral maximum flow equals the maximum number of edge-disjoint source–sink paths.

  • Bipartite matching: A standard flow-network reduction solves maximum-cardinality matching.

  • Reduction framework: Scheduling, transportation, segmentation, and other combinatorial problems can be modeled as flows.

  • Bounds: Every explicit cut provides an upper bound, while every feasible flow provides a lower bound on the maximum achievable flow.

Complexity

For V vertices and E edges, represented by an adjacency list dict[node, list], the input graph occupies O(V + E) space.

Algorithm Preconditions Time Space When to use
Edmonds–Karp Nonnegative capacities O(V × E²) worst case O(V) auxiliary; O(V + E) including input Simple implementation or small networks
Dinic’s algorithm Nonnegative capacities O(V² × E) worst case O(V) auxiliary, including the O(V) recursion stack; O(V + E) including input General networks and many practical cases
Residual BFS for minimum-cut extraction A maximum flow has been computed O(V + E) worst case O(V) auxiliary; O(V + E) including input Recovering a minimum cut

The table assumes residual edges are stored in the graph structure, so they remain O(V + E) overall; auxiliary space counts only additional arrays, queues, and recursion state.

Common Pitfalls and Interview Tips

  • Forgetting the residual graph: Reversed residual edges are essential for rerouting existing flow.

  • Using the wrong cut direction: Directed cut capacity counts edges from S to T, not every edge crossing the partition.

  • Ignoring disconnected cases: If no source–sink path exists, both optimum values are 0.

  • Upgrading only one minimum cut: Multiple minimum cuts may exist, so a capacity increase must address the relevant bottlenecks.

  • Confusing cuts and paths: A minimum cut is a vertex partition, while an augmenting path is a route through residual edges.

  • Common follow-ups: Interviewers may ask how to recover the minimum cut, why the theorem proves optimality, how capacities map to bandwidths, or how the result changes with unit, integral, or negative capacities.

42

What are edge coloring and its graph applications?

Edge coloring assigns colors to a graph’s edges so that no two edges sharing a vertex receive the same color. The minimum number of colors required is the graph’s edge chromatic number, which models conflicts such as simultaneous resource use, channel interference, or incompatible tasks.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Edge Coloring Fundamentals

Assume a finite, loopless, undirected graph (G=(V,E)), represented by an adjacency list such as dict[node, list]. Each undirected edge is stored at both endpoints, requiring (O(V+E)) space for the graph itself.

  • Each color class is a matching: a set of edges with no shared endpoints.

  • Every edge incident to the same vertex must have a different color.

  • Edge weights do not affect ordinary edge coloring; colors represent conflicts or resource categories rather than weights.

  • Directed graphs have several arc-coloring conventions, so the conflict relation must be specified; the principal results below concern undirected graphs.

Important Properties

Let (Delta) be the graph’s maximum degree and (chi’(G)) its chromatic index.

  • Lower bound: (chi’(G)geqDelta), because all (Delta) edges incident to a maximum-degree vertex require distinct colors.

  • Bipartite graphs: By König’s line coloring theorem, (chi’(G)=Delta).

  • Simple graphs: Vizing’s theorem guarantees (Deltaleqchi’(G)leqDelta+1).

  • Loopless multigraphs: Shannon’s theorem guarantees (chi’(G)leqlfloor3Delta/2rfloor).

  • Complete graphs: For (K_n) with (ngeq2), (chi’(K_n)=n) when (n) is odd and (n-1) when (n) is even.

Finding a minimum edge coloring in a general graph is NP-hard, including for some cubic graphs. For bipartite graphs, matching-based algorithms construct a minimum coloring with exactly (Delta) colors.

Applications

  • Scheduling: Represent tasks as vertices and conflicting tasks as edges. Colors become time slots, allowing mutually compatible tasks to run concurrently.

  • Frequency assignment: Represent communication links as edges and devices as vertices. Adjacent links sharing a device receive different channels.

  • Round-robin tournaments: A one-factorization partitions the edges of a suitable graph into perfect matchings. Each matching can represent a round in which every participant plays exactly once.

  • Parallel processing: When edges represent conflicting operations, all operations in one color class can execute concurrently.

  • Conflict resolution: If edges represent conflicts between people, rooms, or resources, colors identify groups that can be assigned together.

Complexity and Preconditions

Task or approach Time complexity Space complexity Reason and preconditions
Build an adjacency list (O(V+E)) (O(V+E)), including input Every vertex and edge is stored a constant number of times; applies to any graph type
Greedy edge coloring with endpoint-color sets (O(EDelta)) worst case (O(V+E)), including input and color assignments An edge shares endpoints with at most (2Delta-2) others, so at most (2Delta-1) candidate colors are tested per edge; works on any loopless graph but may use up to (2Delta-1) colors
Hopcroft–Karp maximum matching (O(Esqrt V)) worst case (O(V+E)), including input and matching output Alternating-path phases bound the search; requires a bipartite graph
Exhaustive enumeration (O(E(Delta+1)^E)) worst case for (E>0) (O(V+E)), including input, recursion stack, and assignment It tries up to (Delta+1) colors per edge (enough for simple graphs by Vizing’s theorem; multigraphs may need up to (lfloor3Delta/2rfloor)) and checks conflicts

For greedy coloring, the best case is (O(E)), while its average case depends on the graph and edge order. For exhaustive enumeration, the best case is (O(E)) if an optimal assignment is found immediately; its average case likewise depends on the search order.

Common Pitfalls

  • Confusing edge and vertex coloring: Edge coloring separates incident edges; vertex coloring separates adjacent vertices.

  • Assuming greedy is optimal: Greedy may use (Delta+1) colors even when (Delta) colors suffice.

  • Ignoring graph type: Bipartite, simple, and multigraph guarantees differ.

  • Empty graph or one isolated vertex: The chromatic index is 0 because there are no edges.

  • Isolated vertices: They do not affect the chromatic index, although they contribute to (V).

  • Disconnected graphs: Components can be colored independently; the graph’s chromatic index is the maximum component index.

  • Parallel edges: They are distinct edges and must receive different colors because they share endpoints.

  • Loops: Ordinary matching-based edge coloring assumes no loops; a loop requires a separate convention.

  • Cycles: A cycle (C_n) has chromatic index 2 for even (n) and 3 for odd (ngeq3).

43

How do you implement Kruskal’s algorithm for finding a minimum spanning tree?

A minimum spanning tree (MST) is a subset of edges connecting every vertex in an undirected weighted graph with the smallest possible total weight and without cycles. Kruskal’s algorithm builds this tree by processing edges from lowest to highest weight and accepting an edge only when it joins two different components.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model and Algorithm Choice

This implementation assumes an undirected, weighted graph represented by an edge list. Each edge is a tuple (source, target, weight), where vertices use integer labels from 0 through vertex_count - 1.

  • Edge-list representation: Stores E edges and requires O(E) graph storage.

  • Adjacency-list representation: Stores O(V + E) graph data and supports Prim’s algorithm.

  • Adjacency-matrix representation: Requires O(V²) storage and is mainly useful for dense graphs.

Algorithm Time Auxiliary Space Best Suited For
Kruskal O(E log E) O(V + E) Sparse graphs and edge-list representations
Prim O(E log V) O(V + E) Graphs represented by adjacency lists

A standard MST exists only for a connected, undirected graph. Negative or zero edge weights are valid.

How Kruskal Works

Kruskal’s algorithm uses a disjoint-set union (DSU) structure to track connected components:

  1. Sort all edges by increasing weight.

  2. Initially, every vertex belongs to its own component.

  3. For each edge in sorted order:

  4. If its endpoints are already connected, reject it because it would create a cycle.

  5. Otherwise, accept it and merge the endpoint components.

  6. Stop after selecting V - 1 edges.

This is safe because of the cut property: the lowest-weight edge crossing any cut between components can belong to an MST.

Complexity

For a connected graph with V vertices and E edges:

  • Best, average, and worst-case time: O(E log E) because sorting the edges dominates the algorithm’s work.

  • DSU work: O(E α(V)) amortized, where α is the inverse Ackermann function and is effectively constant.

  • Auxiliary space: O(V + E) for the DSU and sorted edge list, excluding the input.

  • Total space including input: O(V + E).

  • Recursion stack: O(1) because the implementation is entirely iterative.

Example Walkthrough

For the example graph, the sorted edges are:

Edge Weight Decision
(0, 2) 1 Accept; components become {0, 2} and {1}, {3}
(2, 3) 2 Accept; components become {0, 2, 3} and {1}
(1, 2) 3 Accept; all vertices are connected
(0, 1) 4 Reject; it would create a cycle

The resulting MST contains three edges with total weight 1 + 2 + 3 = 6.

Code Example

from collections.abc import Iterable

WeightedEdge = tuple[int, int, int]


class DisjointSet:
    def __init__(self, size: int) -> None:
        self.parent = list(range(size))
        self.component_size = [1] * size

    def find(self, node: int) -> int:
        # Iterative path compression avoids recursion.
        while self.parent[node] != node:
            self.parent[node] = self.parent[self.parent[node]]
            node = self.parent[node]
        return node

    def union(self, left: int, right: int) -> bool:
        left_root = self.find(left)
        right_root = self.find(right)

        if left_root == right_root:
            return False

        # Attach the smaller component to the larger one.
        if self.component_size[left_root] < self.component_size[right_root]:
            left_root, right_root = right_root, left_root

        self.parent[right_root] = left_root
        self.component_size[left_root] += self.component_size[right_root]
        return True


def minimum_spanning_tree(
    vertex_count: int,
    edges: Iterable[WeightedEdge],
) -> list[WeightedEdge]:
    """Return an MST for a connected, undirected, weighted graph."""
    if vertex_count < 0:
        raise ValueError("vertex_count cannot be negative")

    edge_list = list(edges)

    for source, target, _ in edge_list:
        if not (0 <= source < vertex_count and 0 <= target < vertex_count):
            raise ValueError("Edge endpoint is outside the valid vertex range")

    if vertex_count <= 1:
        return []

    # Sort a copy so the caller's input is not mutated.
    sorted_edges = sorted(
        edge_list,
        key=lambda edge: (edge[2], edge[0], edge[1]),
    )

    disjoint_set = DisjointSet(vertex_count)
    selected_edges: list[WeightedEdge] = []

    for edge in sorted_edges:
        source, target, _ = edge

        if disjoint_set.union(source, target):
            selected_edges.append(edge)

            if len(selected_edges) == vertex_count - 1:
                break

    if len(selected_edges) != vertex_count - 1:
        raise ValueError("Graph is disconnected; no spanning tree exists")

    return selected_edges


edges = [
    (0, 1, 4),
    (1, 2, 3),
    (0, 2, 1),
    (2, 3, 2),
    (1, 3, 7),
]

print(minimum_spanning_tree(4, edges))
# Expected output: [(0, 2, 1), (2, 3, 2), (1, 2, 3)]

Interview Tips and Common Pitfalls

  • An MST minimizes total edge weight; it does not minimize the distance between every pair of vertices.

  • Always check whether endpoints are already connected before accepting an edge.

  • Handle disconnected graphs explicitly. This implementation raises an error; a minimum spanning forest can be returned instead if that is the required behavior.

  • Duplicate edges and self-loops are safe: duplicate edges compete normally, while self-loops are rejected by the DSU.

  • Equal-weight edges may produce different but equally optimal MSTs.

  • Mention that DSU operations are amortized near-constant time and that union by size with path compression is used for efficiency.

44

Graph databases vs. relational databases: when to use each?

Graph databases model entities and their relationships as nodes and edges, making relationship-heavy queries and multi-hop traversals a primary concern. They are especially useful when connected data is more valuable than fixed tabular records, while relational databases remain stronger for predictable schemas, transactional workloads, and analytical reporting.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model and Representation

A graph database generally uses a property graph model:

  • Nodes represent entities such as users, products, accounts, or devices.

  • Edges represent relationships such as FOLLOWS, PURCHASED, or OWNS.

  • Properties store attributes on nodes or edges, including timestamps, categories, confidence scores, and weights.

Graph databases can represent both directed and undirected relationships. They can also represent weighted or unweighted graphs by storing a numeric weight as an edge property.

The conceptual representation is usually adjacency-list-oriented: node -> [(neighbor, edge_properties), ...]. Its logical space is O(V + E), where V is the number of nodes and E is the number of edges. Property storage and indexes add space proportional to their contents. An adjacency-matrix representation instead requires O(V²) space, so adjacency-list structures are generally preferable for sparse graphs.

Why Graph Databases Matter

Relationships are first-class data rather than something reconstructed through multiple table joins. This matters when a query must traverse several relationship levels, such as finding every account indirectly connected to a suspicious account.

Common use cases include:

  • Fraud detection: Identifying unusual paths between accounts, devices, addresses, and transactions.

  • Recommendations: Traversing user, item, and similarity relationships.

  • Knowledge graphs: Connecting entities across documents, datasets, and domains.

  • Network and dependency analysis: Modeling infrastructure, service calls, or software dependencies.

  • Identity resolution: Linking records through shared attributes and relationships.

  • Supply-chain analysis: Tracing products, suppliers, facilities, and shipments.

The main advantage is not merely “fast queries.” It is a more natural way to express connected-data problems and often less query-planning work for multi-hop traversals.

Relational Versus Graph Model

Aspect Graph database Relational database
Primary model Nodes, edges, and properties Tables, rows, columns, and keys
Relationships Explicit edges Foreign keys interpreted through joins
Schema Often flexible or schema-optional Usually fixed and strongly defined
Multi-hop traversal Natural path and relationship queries Usually expressed with recursive CTEs or multiple joins
Typical storage Adjacency-list-oriented, O(V + E) Rows and indexes, often O(R + I) for R records and index entries I
Best fit Highly connected, relationship-heavy data Structured business records and reporting
Reporting Possible, but varies by product Generally mature and predictable
Transactions Supported by many products, with feature differences Long-established, broadly standardized transactional behavior

Neither representation is automatically superior. A relational database can use indexes and materialized views to support graph-like queries, while a graph database can still store nodes and properties that resemble tabular records.

Performance and Complexity

At the abstract graph level, a visited-set traversal that visits every reachable node and scans its adjacency lists takes O(V + E) time. For complete traversals, best, average, and worst time are generally O(V + E); empty and one-vertex inputs take O(1).

  • Auxiliary space: O(V) for the visited set and traversal state.

  • Recursive DFS stack: O(V), included in auxiliary space; an iterative traversal avoids Python’s recursion-depth limit.

  • Disconnected graphs: Iterate over every vertex while retaining one shared visited set.

  • Cycles: The visited set prevents repeated processing.

  • Materialized results: O(S) space for S returned results. Storing one reconstructed path requires O(V) space, while the total number of distinct paths can be exponential.

Weighted shortest-path algorithms have additional requirements:

  • Dijkstra with a binary heap takes O((V + E) log V) time and requires non-negative edge weights. A lazy heap implementation can require O(V + E) auxiliary space; a decrease-key implementation uses O(V).

  • Bellman–Ford takes O(V × E) time and O(V) auxiliary space, and can detect negative cycles.

Relational query complexity is plan-dependent and cannot be represented by one universal Big-O bound. An indexed lookup may examine O(log R) index levels, but joins may process many matching rows. A multi-table join can therefore be significantly more expensive than a direct graph traversal, especially when several levels must be joined.

Selecting the Right Database

Choose a graph database when relationships are dynamic, deeply nested, or central to the application’s queries. Typical signals include recursive relationship exploration, changing relationship types, and many multi-hop path queries.

Choose a relational database when entities have stable fields, transactions dominate the workload, reporting queries are central, or the organization depends on mature SQL tooling and standards. Some systems use both: a relational database for transactional records and a graph database for projections such as recommendation or fraud-analysis networks.

Common Pitfalls

  • Assuming every graph database is automatically faster: Query performance depends on indexes, cardinality, data locality, and query planning.

  • Duplicating relationships without controls: Use explicit direction, relationship types, uniqueness rules, and property validation.

  • Ignoring analytics requirements: Graph traversal excels at connected queries, whereas SQL aggregation and reporting tools are usually more mature.

  • Forgetting negative weights: Dijkstra’s algorithm is invalid when negative-weight edges are present; use Bellman–Ford or another suitable algorithm.

  • Neglecting visited-node tracking: Without a visited set, cyclic graphs can cause repeated work or an infinite traversal.

  • Underestimating denormalization costs: Materialized graph projections improve traversal speed but require synchronization and consistency planning.

45

How do algorithms differ for weighted versus unweighted graphs

The choice of graph algorithm depends fundamentally on whether edges carry weights, since weighted edges enable shortest-path and minimum-spanning-tree computations that unweighted graphs cannot express. Unweighted graphs allow simpler traversal-based approaches, while weighted graphs require algorithms that account for edge costs.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference Between Graph Types

A weighted graph assigns a numeric cost to each edge, while an unweighted graph treats every edge as equal. This distinction changes which algorithms are applicable:

  • Weighted directed: edges have direction and cost (e.g. road networks with distances)

  • Weighted undirected: edges have cost but no direction (e.g. network connections)

  • Unweighted directed: edges have direction only (e.g. task dependencies)

  • Unweighted undirected: edges have neither direction nor cost (e.g. social connections)

Graphs are typically represented as an adjacency list (dict mapping node to list of neighbors), an adjacency matrix, or an edge list. Adjacency lists use O(V + E) space, adjacency matrices use O(V²), and edge lists use O(E).

Algorithm Selection by Graph Type

Unweighted graphs rely on traversal:

  • BFS finds the shortest path in terms of edge count, running in O(V + E) time

  • DFS determines connectivity and detects cycles using a visited set

Weighted graphs require cost-aware algorithms:

  • Dijkstra computes shortest paths from a single source, but requires non-negative weights, running in O((V + E) log V) with a binary heap

  • Bellman-Ford handles negative weights and detects negative cycles, running in O(V * E)

  • Floyd-Warshall computes all-pairs shortest paths in O(V³)

  • Kruskal and Prim find minimum spanning trees in O(E log E) and O(E log V) respectively

  • Topological sort orders DAG nodes in O(V + E), but only works on directed acyclic graphs

Complexity Comparison

Algorithm Graph Type Time Complexity Space Complexity
BFS Unweighted O(V + E) O(V)
DFS Unweighted O(V + E) O(V)
Dijkstra Weighted (non-negative) O((V + E) log V) O(V)
Bellman-Ford Weighted (any) O(V * E) O(V)
Floyd-Warshall Weighted (any) O(V³) O(V²)
Kruskal Weighted O(E log E) O(V + E)
Prim Weighted O(E log V) O(V)
Topological Sort Directed acyclic O(V + E) O(V)

When to Use Which Approach

Use BFS when you need the minimum number of edges between nodes and the graph is unweighted. Use Dijkstra when edge costs are non-negative and you need the minimum total cost. Use Bellman-Ford when negative weights exist or you need to detect negative cycles. Use Floyd-Warshall for all-pairs shortest paths on small graphs. Use Kruskal or Prim for minimum spanning trees. Use topological sort for dependency ordering in DAGs.

Common Pitfalls

  • Applying Dijkstra to graphs with negative weights produces incorrect results

  • Forgetting the visited set in DFS or BFS leads to infinite loops on cyclic graphs

  • Treating a directed graph as undirected (or vice versa) changes reachability

  • Running topological sort on a graph with a cycle fails and requires cycle detection first

  • Interviewers often follow up by asking how to handle negative edge weights or disconnected components

46

What differs between algorithms for directed and undirected graphs?

The key distinction is that a directed graph treats u → v and v → u as different edges, while an undirected graph treats them as one bidirectional relationship. This affects edge construction, traversal, cycle detection, pathfinding, and algorithm preconditions.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Semantic Differences

Aspect Directed graph Undirected graph
Edge meaning u → v allows travel from u to v only An edge permits travel in either direction
Adjacency-list insertion Add the edge under u only Add it under both u and v
Reachability May exist from u to v without the reverse path If u can reach v, v can also reach u
Cycle detection Requires active-path tracking, such as three colours or a recursion stack Can use parent-edge tracking or union-find
Strong connectivity Relevant; concerns mutually reachable vertices Not normally used; ordinary connectivity applies
Classic algorithms Topological sorting, SCC algorithms, directed MST variants Connected components, bridges, bipartite checks, MST

For weighted graphs, store (neighbor, weight) pairs instead of just neighbors. Weighted versus unweighted graphs changes the algorithm needed for shortest paths, but not the asymptotic space cost of an adjacency list.

Representation and Complexity

Represent the graph as an adjacency list, dict[node, list].

  • Directed edge u → v: append v only to graph[u].

  • Undirected edge {u, v}: append v to graph[u] and u to graph[v].

  • Input storage: An adjacency list uses O(V + E) space.

  • Auxiliary space: A visited set, queue, or stack uses O(V). Recursive DFS includes an O(V) recursion stack in this bound.

  • Total space: O(V + E) when the input graph is counted.

  • Adjacency matrix: Uses O(V²) input space, plus O(V) auxiliary space for traversal state.

  • Edge list: Uses O(V + E) space when vertices are also stored.

Algorithm Time Space Precondition or purpose
DFS or BFS O(V + E) O(V) auxiliary Reachability and connected components
Dijkstra with a binary heap O((V + E) log V) O(V + E) total Non-negative edge weights
Bellman-Ford O(V × E) O(V) auxiliary Handles negative weights and detects negative cycles
Floyd-Warshall O(V³) O(V²) All-pairs shortest paths
Topological sort O(V + E) O(V) auxiliary Directed acyclic graph only
Kruskal O(E log E) O(V + E) total Minimum spanning forest on an undirected graph
Prim O(E log V) O(V + E) total Minimum spanning tree on a connected undirected graph

Algorithm-Specific Preconditions

  • Shortest paths: Dijkstra is valid only when every edge weight is non-negative. A negative undirected edge creates a negative cycle because the edge can be traversed back and forth.

  • Topological sorting: The graph must be a directed acyclic graph. It has no meaning for an undirected graph in its standard form.

  • Minimum spanning trees: MST algorithms apply to undirected graphs. On a disconnected graph, Kruskal can produce a minimum spanning forest; Prim normally requires one connected component.

  • Cycle detection: In an undirected DFS, skip only the exact edge used to reach the current vertex. In a directed DFS, track active recursion-stack vertices or use unvisited, active, and finished states to identify back edges.

  • Traversal coverage: Always keep a visited marker and start a traversal from every unvisited vertex so disconnected components are included.

Small Example

Consider edges u → v and v → w.

  1. In the directed graph, starting at u reaches v, then w.

  2. There is no directed path from w back to u, so the graph is not strongly connected.

  3. In the undirected interpretation, the same connections are u—v and v—w.

  4. Starting at u reaches v and w, and every visited vertex can also reach u.

  5. During DFS, u is visited when v examines the reverse connection, preventing repeated processing.

The underlying vertex and edge counts are the same, but the reachable states differ because edge direction changes traversal behavior.

Common Pitfalls

  • Adding an undirected edge only once causes the graph to behave incorrectly as directed.

  • Confusing strongly connected components in directed graphs with connected components in undirected graphs.

  • Using DFS visited markers alone for directed cycle detection; active recursion-stack information is necessary.

  • Skipping every edge to the parent in an undirected graph, which can miss cycles caused by parallel edges. Track the parent edge ID rather than only the parent vertex.

  • Assuming topological sorting can handle cycles or apply to undirected graphs.

  • Forgetting self-loops, parallel edges, negative weights, negative cycles, or disconnected components.

  • Mutating the input graph while adding reverse edges; build the required representation separately when the original must remain unchanged.

47

How do you find articulation points in a graph?

Articulation points (also called cut vertices) are vertices whose removal increases the number of connected components. Use Tarjan’s algorithm, implemented with a DFS forest, to find all of them in O(V + E) time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Graph type: an undirected graph, weighted or unweighted; edge weights do not affect articulation points. The representation is an adjacency list dict[node, list[node]], occupying O(V + E) space.

  • Discovery time: disc[node] records when node is first visited.

  • Low-link value: low[node] is the minimum discovery time reachable from node‘s DFS subtree using tree edges followed by at most one back edge.

  • DFS root: a root is an articulation point if it has more than one DFS-tree child.

  • Non-root: node is an articulation point if some DFS child neighbor satisfies low[neighbor] >= disc[node], meaning that child’s subtree cannot reach an ancestor of node without passing through node.

  • Parent tracking: ignore the edge to the immediate parent in a simple undirected graph.

  • Disconnected graphs: start a new DFS from every unvisited vertex, forming a DFS forest.

Complexity

  • Time: O(V + E) because every vertex and adjacency-list entry is scanned once.

  • Auxiliary space: O(V) for discovery times, low-link values, parents, the articulation-point set, and the recursion stack. This excludes the input adjacency list; total space including the representation is O(V + E).

Brute Force vs Tarjan’s

Approach Time Auxiliary space Total space When to use
Remove each vertex and search the graph O(V(V + E)) O(V) O(V + E) Teaching or very small graphs
Tarjan’s DFS forest O(V + E) O(V) O(V + E) Production and interviews

Code Example

def find_articulation_points(graph: dict[int, list[int]]) -> list[int]:
    """Return sorted articulation points of an undirected integer-labeled graph.

    Each undirected edge must appear in both endpoints' adjacency lists.
    """
    if not graph:
        return []

    discovery: dict[int, int] = {}
    low: dict[int, int] = {}
    parent: dict[int, int] = {}
    visited: set[int] = set()
    articulation_points: set[int] = set()
    timer = 0

    def dfs(node: int) -> None:
        nonlocal timer

        visited.add(node)
        discovery[node] = low[node] = timer
        timer += 1
        child_count = 0

        for neighbor in graph[node]:
            parent_node = parent.get(node)
            if parent_node is not None and neighbor == parent_node:
                continue

            if neighbor in visited:
                low[node] = min(low[node], discovery[neighbor])
            else:
                child_count += 1
                parent[neighbor] = node
                dfs(neighbor)
                low[node] = min(low[node], low[neighbor])

                if node not in parent and child_count > 1:
                    articulation_points.add(node)

                if node in parent and low[neighbor] >= discovery[node]:
                    articulation_points.add(node)

    # Process every component in the graph.
    for node in graph:
        if node not in visited:
            dfs(node)

    return sorted(articulation_points)


# Example:
print(find_articulation_points({0: [1, 2], 1: [0], 2: [0]}))  # [0]

Walkthrough

For {0: [1, 2], 1: [0], 2: [0], 3: [4], 4: [3]}:

  1. DFS starts at 0, setting disc[0] = 0 and low[0] = 0.

  2. Visiting 1 gives disc[1] = low[1] = 1. On returning, low[1] >= disc[0], but the root uses the separate child-count rule.

  3. Visiting 2 similarly gives disc[2] = low[2] = 2.

  4. Root 0 now has two DFS children, so it is an articulation point.

  5. The separate component {3, 4} is a single edge, so it has no articulation point.

The result is [0].

Common Pitfalls

  • Forgetting the visited set: cycles or duplicate edges can cause repeated processing.

  • Starting DFS from only one vertex: disconnected components remain unprocessed.

  • Misapplying the root condition: DFS roots are identified by child count, not degree or low-link values.

  • Ignoring back edges: low-link values would be incorrect without them.

  • Recursion depth: this recursive version can exceed Python’s roughly 1,000-call default limit; use an explicit stack or raise the limit for deeper graphs.

  • Edge cases: empty and one-vertex graphs return no articulation points; cycles, self-loops, and duplicate adjacency entries are handled; negative or noncontiguous integer labels work; neighbor ordering, including already sorted input, does not affect the result.

48

How do you solve the Knight’s tour with graph traversal?

A knight’s tour can be found using depth-first search (DFS) with backtracking over the board’s move graph. The search constructs a path that visits every square exactly once, while Warnsdorff’s degree heuristic improves move ordering without sacrificing completeness.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Graph Model

  • Represent each board square as a vertex and each legal knight move as an edge.

  • The graph is undirected and unweighted, because a move can be reversed and all moves have equal cost.

  • With an (n times n) board, there are (V=n^2) vertices. Every vertex has at most eight neighbors, so (E le 4V).

  • The code uses an adjacency list represented as dict[Square, list[Square]]. Its storage is (O(V+E)=O(V)).

DFS Backtracking Strategy

  1. Build the graph of legal knight moves.

  2. Choose a starting square and mark it as visited.

  3. Use DFS to move only to unvisited, valid neighbors.

  4. If a move cannot lead to a complete tour, remove that square from the current path and try another neighbor.

  5. Try every starting square if necessary.

Moves are ordered by their number of onward unvisited neighbors. This is Warnsdorff’s heuristic: visiting constrained squares first often finds a tour without backtracking. Because it changes only the search order, the algorithm remains exhaustive.

On a (5 times 5) board, for example:

  1. Starting at (0, 0), the legal moves include (1, 2) and (2, 1).

  2. From (1, 2), (0, 4) has only one onward unvisited neighbor, so it is selected early.

  3. From (0, 4), the only unvisited neighbor is (2, 3).

  4. If that branch eventually fails, DFS backtracks and explores the next candidate.

Complexity

  • Best case: (O(V+E)=O(V)), because the first explored path visits every square without backtracking.

  • Average case: Input and ordering dependent; the heuristic often approaches the best case, but there is no guaranteed polynomial bound.

  • Worst case: (O(V cdot 8^V)), because DFS may explore exponentially many paths and may try all (V) starting squares.

  • Space: (O(V)), including the adjacency list, visited set, current path, and explicit DFS stack. The input is only an integer, so no board-sized input storage is counted.

Code Example

Square = tuple[int, int]


def knights_tour(board_size: int) -> list[Square] | None:
    """Return one knight's tour, or None if no complete tour exists."""
    if board_size < 1:
        raise ValueError("board_size must be positive")

    total_squares = board_size * board_size
    if total_squares == 1:
        return [(0, 0)]

    knight_moves = (
        (-2, -1), (-2, 1), (-1, -2), (-1, 2),
        (1, -2), (1, 2), (2, -1), (2, 1),
    )

    # Undirected, unweighted graph stored as an adjacency list.
    adjacency: dict[Square, list[Square]] = {}

    for row in range(board_size):
        for column in range(board_size):
            square = (row, column)
            neighbors: list[Square] = []

            for row_change, column_change in knight_moves:
                next_row = row + row_change
                next_column = column + column_change

                if (
                    0 <= next_row < board_size
                    and 0 <= next_column < board_size
                ):
                    neighbors.append((next_row, next_column))

            adjacency[square] = neighbors

    for start in adjacency:
        visited: set[Square] = {start}
        path: list[Square] = [start]

        def ordered_neighbors(square: Square) -> list[Square]:
            candidates = [
                neighbor
                for neighbor in adjacency[square]
                if neighbor not in visited
            ]

            # Warnsdorff: try squares with fewer onward moves first.
            candidates.sort(
                key=lambda candidate: sum(
                    neighbor not in visited
                    for neighbor in adjacency[candidate]
                )
            )
            return candidates

        # Each frame stores: current square, candidates, next candidate index.
        stack: list[tuple[Square, list[Square], int]] = [
            (start, ordered_neighbors(start), 0)
        ]

        while stack:
            current, candidates, next_index = stack[-1]

            if next_index == len(candidates):
                # No remaining branch: backtrack and unvisit this square.
                stack.pop()
                visited.remove(current)
                path.pop()
                continue

            stack[-1] = (current, candidates, next_index + 1)
            next_square = candidates[next_index]

            if next_square in visited:
                continue

            visited.add(next_square)
            path.append(next_square)

            if len(path) == total_squares:
                return path

            stack.append((next_square, ordered_neighbors(next_square), 0))

    return None


tour = knights_tour(8)
print(len(tour) if tour is not None else None)  # Expected output: 64

Common Pitfalls

  • Never remove visited squares during ordinary forward traversal. Removal is required only when DFS backtracks.

  • Check every generated coordinate. Negative coordinates and moves beyond the board edges are invalid.

  • Try disconnected graphs carefully. Small boards can have disconnected move graphs, making a complete tour impossible.

  • Handle cycles with the visited set. A knight can revisit squares through different paths, but a tour itself may not revisit a square.

  • Use an explicit stack for large boards. This implementation avoids Python’s recursion-depth limit.

  • Do not claim Warnsdorff always succeeds without backtracking. It is a heuristic; backtracking guarantees completeness.

49

How do you find connected components in an undirected graph?

Connected components are maximal groups of vertices where every pair is connected by a path. In an undirected graph, find them by running BFS or DFS from each vertex that has not yet been visited.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach and Correctness

This answer uses an unweighted, undirected graph represented by an adjacency list, dict[node, list[node]]. Each undirected edge appears in both endpoints’ adjacency lists. If the graph has weights, they do not affect connectivity and can be ignored during traversal.

  1. Create an empty visited set.

  2. Iterate over every vertex in the graph.

  3. If a vertex is unvisited, start BFS from it.

  4. BFS visits exactly the vertices reachable from its starting vertex, forming one connected component.

  5. Add that component to the result and continue with the next unvisited vertex.

The outer loop is essential because it ensures disconnected graphs are handled. Marking vertices as visited when they enter the queue prevents cycles and duplicate edges from causing repeated processing.

Complexity and Alternatives

Let V be the number of vertices and E the number of edges.

Approach Time Extra space When to use
BFS components O(V + E) O(V) General-purpose implementation
DFS components O(V + E) O(V) Equivalent; use an explicit stack for large graphs because recursive DFS can hit Python’s recursion limit
Union-Find O((V + E) α(V)) amortized O(V) Components must be maintained while edges arrive
Pairwise reachability O(V(V + E)) O(V) Small graphs or baseline comparisons

For the BFS implementation:

  • Best and average time: O(V + E), because every vertex and adjacency-list entry is processed once and hash-set operations average O(1).

  • Worst-case time: O(V(V + E)) in the abstract hash-table model if adversarial hash collisions make membership operations O(V); standard graph analysis normally reports O(V + E).

  • Auxiliary space: O(V) for the visited set, queue and current component, excluding the input. A DFS implementation similarly needs O(V) for its visited set plus either an explicit stack or recursive call stack.

  • Total space including the adjacency list: O(V + E).

  • An adjacency-matrix representation instead requires O(V²) space.

Example Walkthrough

For the graph A—B—C, D—E, and isolated vertex F:

  1. Start BFS at A; visit B and then C.

  2. Store ['A', 'B', 'C'] as one component.

  3. Start BFS at D; visit E.

  4. Store ['D', 'E'] as another component.

  5. Start BFS at F; it has no neighbors.

  6. Store ['F'] as the final component.

Code Example

from collections import deque
from collections.abc import Hashable
from typing import TypeVar

Node = TypeVar("Node", bound=Hashable)


def connected_components(graph: dict[Node, list[Node]]) -> list[list[Node]]:
    """Return the connected components of an undirected adjacency-list graph."""
    visited: set[Node] = set()
    components: list[list[Node]] = []

    # Start a new traversal for every disconnected part of the graph.
    for start in graph:
        if start in visited:
            continue

        visited.add(start)
        queue: deque[Node] = deque([start])
        component: list[Node] = []

        while queue:
            node = queue.popleft()
            component.append(node)

            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    # Mark when enqueued to avoid duplicate queue entries.
                    visited.add(neighbor)
                    queue.append(neighbor)

        components.append(component)

    return components


graph = {
    "A": ["B", "C"],
    "B": ["A", "C"],
    "C": ["A", "B"],
    "D": ["E"],
    "E": ["D"],
    "F": [],
}

print(connected_components(graph))
# Expected output: [['A', 'B', 'C'], ['D', 'E'], ['F']]

Common Pitfalls and Interview Tips

  • Forgetting disconnected graphs: Always loop over all graph vertices, not just one starting point.

  • Missing visited checks: Cycles can cause infinite traversal without a visited set.

  • Incorrect undirected representation: Store each edge in both adjacency lists, or first construct a symmetric adjacency list from an edge list.

  • Duplicate edges: They do not change connectivity and are handled safely by the visited set.

  • Empty input: The function correctly returns [].

  • Isolated vertices: Each appears as a component containing one vertex.

  • Cycles and duplicate neighbors: A vertex is processed only once.

  • Negative node values: Labels may be negative and do not affect connectivity.

  • Input ordering: Results may follow vertex or traversal order, so sort them only if deterministic output is required.

  • Common follow-up: Explain why Union-Find is useful for incrementally adding edges, and distinguish connected components from strongly connected components in directed graphs.

50

How to solve River Crossing Problem using graph BFS?

The River Crossing Problem is solved by modeling each configuration as a node in a state-space graph and using BFS to find the shortest sequence of moves.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Model each bank configuration as a state tuple (farmer, wolf, goat, cabbage), where True means the item is on the starting bank.

  • The goal state is (False, False, False, False).

  • A move consists of the farmer crossing the river alone or with one item, flipping the farmer’s position and the item’s position if they share a bank.

  • A state is safe if the bank without the farmer does not contain the wolf with the goat or the goat with the cabbage.

  • BFS explores states level by level, guaranteeing the shortest solution path.

Graph Representation and Complexity

  • The graph is undirected because every move is reversible.

  • Representation is implicit: neighbors are generated from the current state rather than stored in an adjacency list.

  • Time complexity: O(V + E), where V = 2^n states and E ≤ (n+1)·2^n. For the classic problem with the farmer and three items, V ≤ 16 and E ≤ 32, and only 10 of the 16 states are safe.

  • Space complexity: O(V) for the visited set and parent pointers. This does not count the input itself.

Code Example

from collections import deque
from typing import List, Optional, Tuple

State = Tuple[bool, bool, bool, bool]  # (farmer, wolf, goat, cabbage)

def river_crossing() -> Optional[List[State]]:
    """Find the shortest sequence of moves for the River Crossing Problem."""
    start: State = (True, True, True, True)
    goal: State = (False, False, False, False)
    if start == goal:
        return [start]

    visited: set[State] = {start}
    parent: dict[State, Optional[State]] = {start: None}
    queue: deque[State] = deque([start])

    while queue:
        current = queue.popleft()
        if current == goal:
            path = []
            node = current
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for next_state in get_valid_moves(current):
            if next_state in visited:
                continue
            visited.add(next_state)
            parent[next_state] = current
            queue.append(next_state)
    return None

def get_valid_moves(state: State) -> List[State]:
    """Generate all safe states reachable by one boat move."""
    farmer, wolf, goat, cabbage = state
    moves = []
    # Farmer crosses alone
    moves.append((not farmer, wolf, goat, cabbage))
    # Farmer crosses with an item on the same bank
    if farmer == wolf:
        moves.append((not farmer, not wolf, goat, cabbage))
    if farmer == goat:
        moves.append((not farmer, wolf, not goat, cabbage))
    if farmer == cabbage:
        moves.append((not farmer, wolf, goat, not cabbage))
    return [m for m in moves if is_safe(m)]

def is_safe(state: State) -> bool:
    """Check if the bank without the farmer is safe."""
    farmer, wolf, goat, cabbage = state
    if farmer:
        # Farmer is on the left; check the right bank
        bank = (not wolf, not goat, not cabbage)
    else:
        # Farmer is on the right; check the left bank
        bank = (wolf, goat, cabbage)
    wolf, goat, cabbage = bank
    return not (wolf and goat) and not (goat and cabbage)

# Example usage
if __name__ == "__main__":
    solution = river_crossing()
    print(solution)  # [(True, True, True, True), (False, True, False, True), ...]

Common Pitfalls

  • Forgetting to check safety on the bank without the farmer.

  • Generating moves for items on the opposite bank.

  • Using a recursive DFS without a visited set, which can cause infinite loops in cyclic graphs.

  • Storing full paths in the BFS queue, which increases space complexity to O(V²).

  • Not handling the case where no solution exists; BFS returns None in that scenario.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 50 Graph Theory answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects