Graphs and Graph Algorithms Questions

Direct answer

This is tree DP: root the tree at any node, and for each node compute two values, the best achievable weight of an independent set in that node's subtree WHEN the node itself is included, and the best when it is EXCLUDED. If a node is included, none of its direct children may be included (so each child contributes its own "excluded" value), and if a node is excluded, each child is free to contribute whichever of its own two values is larger. The answer is the max of the root's two values, computed bottom-up in a single post-order depth-first search (DFS), giving $O(N)$ time since each node is visited once and does $O(1)$ work beyond its recursive calls.

Structured elaboration

Why "included" and "excluded" as the two DP states. An independent set on a tree forbids any two ADJACENT nodes both being chosen. On a tree, adjacency is exactly the parent-child relationship, so the only constraint that ever needs enforcing at any node is between that node and its direct children, not any deeper relationship (a node and its grandchild are never adjacent, so no constraint links them directly; the constraint propagates only through the recursive excluded values, correctly capturing that a grandchild's INCLUSION is not blocked by the root's inclusion, only a direct child's is).

Recurrence. For node u with children c_1, ..., c_k:
$\text{incl}(u) = w(u) + \sum_{i} \text{excl}(c_i)$
$\text{excl}(u) = \sum_{i} \max(\text{incl}(c_i), \text{excl}(c_i))$
The base case (a leaf with no children) is incl(leaf) = w(leaf), excl(leaf) = 0 (both sums over an empty child list are 0, so the general recurrence already handles leaves correctly without a separate base case).

Why a single post-order pass suffices, no memoization table needed beyond the two per-node values. Each node's incl/excl values depend only on its CHILDREN's incl/excl values, never on anything computed later in a different subtree, so a straightforward post-order DFS (compute all children first, then the current node) naturally produces every value exactly once, in the right dependency order, with no need for a separate memo dictionary keyed by subproblem, unlike DP on a general DAG where multiple paths to the same subproblem can require explicit memoization to avoid recomputation.

Worked example

import sys
from typing import Dict, List

def max_independent_set(adj: Dict[int, List[int]], weights: Dict[int, int]) -> int:
    sys.setrecursionlimit(10000)
    root = next(iter(adj))
    visited = {root}

    def dfs(u):
        incl = weights[u]
        excl = 0
        for v in adj.get(u, []):
            if v in visited:
                continue
            visited.add(v)
            child_incl, child_excl = dfs(v)
            incl += child_excl
            excl += max(child_incl, child_excl)
        return incl, excl

    incl_root, excl_root = dfs(root)
    return max(incl_root, excl_root)

if __name__ == "__main__":
    #        0(w=6)
    #       /      \
    #    1(w=8)    2(w=5)
    #     |          \
    #   3(w=3)       4(w=9)
    adj = {0: [1, 2], 1: [0, 3], 2: [0, 4], 3: [1], 4: [2]}
    weights = {0: 6, 1: 8, 2: 5, 3: 3, 4: 9}
    result = max_independent_set(adj, weights)
    print("weights:", weights)
    print("max independent set weight:", result)

Output:

weights: {0: 6, 1: 8, 2: 5, 3: 3, 4: 9}
max independent set weight: 18

Trace: leaves 3 and 4 have incl=3, excl=0 and incl=9, excl=0 respectively. Node 1: incl = 8 + excl(3) = 8 + 0 = 8, excl = max(incl(3), excl(3)) = max(3, 0) = 3. Node 2: incl = 5 + excl(4) = 5 + 0 = 5, excl = max(incl(4), excl(4)) = max(9, 0) = 9. Root 0: incl = 6 + excl(1) + excl(2) = 6 + 3 + 9 = 18, excl = max(incl(1),excl(1)) + max(incl(2),excl(2)) = max(8,3) + max(5,9) = 8 + 9 = 17. Final answer max(18, 17) = 18, matching the printed output; the optimal set turns out to be {0, 3, 4} (root plus both "excluded child" leaves, weight 6+3+9=18), correctly skipping the higher-weight node 4's parent 2 in favor of taking node 4 itself rather than its parent.

Trade-offs and pitfalls

• Correctness cross-check performed against brute force: for this 5-node tree, every one of the $2^5=32$ possible node subsets was enumerated, independence was checked against all 4 tree edges, and the maximum-weight valid subset was found by brute force to also be 18, confirming the DP's answer exactly matches exhaustive search on this instance.
• Common mistake: writing excl(u) = max of all children's incl, or all children's excl (picking one branch for ALL children uniformly) instead of taking the max INDEPENDENTLY per child. Each child's contribution to excl(u) should be max(incl(c_i), excl(c_i)) computed separately for each child, since different children can independently be in their own best state; forcing a single uniform choice across all children would understate the achievable weight whenever the best choice differs child to child.
• Recursion depth is $O(\text{height})$, which is $O(N)$ in the worst case (a tree that degenerates into a long chain); a production implementation accepting untrusted or adversarially shaped trees should convert this to an iterative post-order traversal with an explicit stack to avoid a RecursionError on a deep, path-like tree.
• This recurrence is specific to TREES (a graph with no cycles and a single path between any two nodes). On a general graph, maximum weight independent set is NP-hard; the polynomial-time DP here relies entirely on the tree structure guaranteeing that removing the root splits the problem into completely independent subproblems (the children's subtrees), a decomposition that does not exist for a graph with cycles.

Direct answer

A recursive depth-first search (DFS) visits a start node, marks it visited, then recurses into each unvisited neighbor in turn; a visited set is what makes it safe on graphs with cycles and self-loops, since a node already in the set is simply skipped rather than recursed into again.

Structured elaboration

The function needs to satisfy three things at once: return nodes in discovery order (the order each node is FIRST reached), handle graphs that contain cycles or self-loops without infinite recursion, and handle a node referenced as a neighbor but missing as its own key in the adjacency dict. All three fall out of the same small set of choices: check visited before doing anything else (this is what stops both cycles and self-loops from causing infinite recursion), append to the output list at the moment a node is first marked visited (this is what makes the order a true discovery order), and use graph.get(node, []) instead of graph[node] when looking up neighbors (this is what tolerates a node that appears only as someone else's neighbor).

Worked example

from typing import Dict, List, Set

def dfs(graph: Dict[int, List[int]], start: int) -> List[int]:
    visited: Set[int] = set()
    order: List[int] = []
    def visit(node: int):
        if node in visited:
            return
        visited.add(node)
        order.append(node)
        for nbr in graph.get(node, []):
            visit(nbr)
    visit(start)
    return order

if __name__ == "__main__":
    # Graph with a self-loop on 2, a cycle 3 <-> 4, and node 5 present only as a
    # neighbor (no key of its own in the dict) to exercise the "missing node" path.
    graph = {
        0: [1, 2],
        1: [2],
        2: [2, 3],   # self-loop
        3: [4],
        4: [3, 5],   # cycle back to 3, plus an edge to the key-less node 5
    }
    order = dfs(graph, 0)
    print("DFS discovery order from 0:", order)
    print("terminated without infinite recursion despite the self-loop at 2 and the 3<->4 cycle:", True)
    print("node 5 (no key in graph dict) still appears in discovery order:", 5 in order)
    print("all reachable nodes visited exactly once, order length == 6:", len(order) == 6)

Output (actually executed with python3):

DFS discovery order from 0: [0, 1, 2, 3, 4, 5]
terminated without infinite recursion despite the self-loop at 2 and the 3<->4 cycle: True
node 5 (no key in graph dict) still appears in discovery order: True
all reachable nodes visited exactly once, order length == 6: True

Complexity

• Time: $O(V + E)$ for the reachable portion of the graph, each reachable node is visited exactly once, each of its adjacency entries examined once.
• Space: $O(V)$ for the visited set plus the recursion call stack, which in the worst case (a long chain) also grows to $O(V)$.

Edge cases

• Empty graph or start unreachable from anything: returns [start] alone if start itself is a valid node, otherwise an empty adjacency lookup via .get just means no further recursion happens.
• start not present as a key: graph.get(start, []) still works when visit(start) first runs, it simply finds no neighbors and returns [start].
• Very deep graphs: recursion depth grows with the reachable graph's depth; a production system facing potentially deep or adversarial graphs should switch to an iterative version with an explicit stack rather than raising the interpreter's recursion limit.

Trade-offs and pitfalls

• Common mistake: checking visited only inside the loop over neighbors rather than at the top of visit itself; without the top-of-function check, a node could be appended to order more than once if it is reachable via two different call paths that both reach it before either has finished, timing that can genuinely happen in a graph with multiple incoming edges to the same node.
• Common mistake: using graph[node] instead of graph.get(node, []), which raises a KeyError the moment the traversal reaches any node that was never a top-level key, exactly the situation node 5 exercises above.
• This function returns PREORDER discovery order (append on entry). A different, less common requirement, POSTORDER (append after all descendants are fully explored, useful for topological sort by finish time), needs the append moved to after the for loop instead of before it, a one-line change with a materially different algorithmic use.

Direct answer

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

Structured elaboration

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

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

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

Worked example

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

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

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

Trade-offs and pitfalls

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

Direct answer

(a) City road routing with non-negative weights and frequent repeated queries: Dijkstra's algorithm as the baseline, but for a system serving many queries against a largely static road network, layer on precomputation (Contraction Hierarchies or a bidirectional/ALT search) rather than running plain Dijkstra fresh per query. (b) A currency exchange graph where arbitrage implies negative cycles: Bellman-Ford, specifically because it is the standard algorithm that both handles negative edge weights and can detect a negative cycle's existence, which is the actual signal being searched for (an arbitrage opportunity IS a negative cycle in a graph where edge weights are the negative log of exchange rates). (c) Pairwise social network distances on unweighted graphs: breadth-first search (BFS) from each source, since with unweighted edges the fewest-edges path IS the shortest path, and BFS finds it in strictly less work than any weighted algorithm would need to do.

Structured elaboration

(a) City road routing. Every edge weight is non-negative (travel time or distance cannot be negative), which is exactly Dijkstra's precondition. For a ONE-OFF query, plain Dijkstra with a binary heap is $O((V+E) \log V)$ and is the right default. For a system answering MANY queries against a road network that changes rarely (new roads open occasionally; traffic-based weight updates happen far more often than the topology itself changes), the standard production approach precomputes shortcuts once (Contraction Hierarchies) so that individual queries run in a fraction of the cost of a from-scratch Dijkstra, or uses bidirectional search (searching simultaneously from both source and destination and stopping when the two frontiers meet) to roughly halve the effective search radius. The key judgment call the question is testing: recognizing that "frequent queries" changes the right answer from "which single-query algorithm" to "what should be precomputed once, before any query arrives."

(b) Currency arbitrage. Model each currency as a node and each exchange rate as a directed edge weighted by $-\log(\text{rate})$. Under this transform, a product of exchange rates greater than 1 (a profitable arbitrage loop) becomes a SUM of edge weights less than 0 (a negative cycle), because $\log$ turns multiplication into addition and the sign flip turns "greater than 1" into "less than 0." Dijkstra cannot be used here at all: it assumes non-negative weights and produces silently wrong results (not even a detectable error) if given negative edges, because its greedy "finalize the closest unvisited node" strategy assumes no later relaxation could ever improve an already-finalized node, an assumption negative edges break. Bellman-Ford handles negative edges correctly by relaxing every edge up to $V-1$ times, and its cycle-detection extension (checking whether any edge can still be relaxed on a $V$-th pass) is exactly the mechanism for detecting that a negative cycle, and therefore an arbitrage opportunity, exists.

(c) Unweighted social-network distances. With every edge implicitly weight 1, Dijkstra still gives the correct answer but does unnecessary work maintaining a priority queue and comparing distances that could only ever increase by exactly 1 per edge. BFS achieves the same correct shortest-path distances using a plain FIFO queue, exploiting the fact that BFS naturally visits nodes in increasing order of edge count, which is precisely the shortest-path order when every edge costs the same.

Worked example

Complexity comparison, $V$ = number of nodes, $E$ = number of edges:

Concrete arbitrage instance for (b): three currencies USD, EUR, JPY with exchange rates USD to EUR = 0.9, EUR to JPY = 130, JPY to USD = 0.0086. The round-trip product is $0.9 \times 130 \times 0.0086 = 1.0062$, greater than 1, meaning one unit of USD converted around the full loop back to USD returns 1.0062 units, a 0.62 percent arbitrage. Under the negative-log transform: edge weights become $-\ln(0.9) \approx 0.1054$, $-\ln(130) \approx -4.8675$, $-\ln(0.0086) \approx 4.7560$, summing to $0.1054 - 4.8675 + 4.7560 = -0.0061$, which matches $-\ln(1.0062) \approx -0.0062$ (the small residual is rounding in the 4-decimal edge weights). A negative cycle total, matching the arbitrage: a negative sum of log-weights corresponds to a product greater than 1.

Trade-offs and pitfalls

• Common mistake: reaching for Dijkstra in scenario (b) because "it's the standard shortest-path algorithm." Dijkstra's core greedy step, permanently finalizing the shortest known distance to a node once popped, is provably wrong in the presence of negative edges, since a later negative edge could still improve a distance that was already treated as final. This is not a performance trade-off, it is a correctness failure, and it fails silently (no exception, no error) rather than crashing, which makes it a genuinely dangerous mistake to make in a financial context.
• Common mistake: reaching for Bellman-Ford in scenario (c) "to be safe." It gives the correct answer but at $O(VE)$ instead of BFS's $O(V+E)$, a real cost difference at scale on a large social graph, for no benefit since there are no negative weights to worry about.
• Common mistake in scenario (a): treating "frequent queries" as irrelevant to the algorithm choice. A system that reruns plain Dijkstra from scratch for every query is leaving a large, well-known optimization on the table (precomputation amortized across queries) that specifically becomes worthwhile once query volume is high enough to justify the one-time preprocessing cost.
• The negative-cycle DETECTION step in scenario (b) is not optional flavor, it is the actual point of the exercise: finding shortest paths in a graph that HAS a negative cycle is not even well-defined (you could loop the cycle infinitely to make the "shortest path" arbitrarily negative), so the correct behavior is to detect and report the cycle's existence, not to return some finite distance as if the graph were well-behaved.

Direct answer

is_bipartite(graph) runs a BFS two-coloring pass from every not-yet-colored node (handling disconnected input), assigning each newly discovered node the opposite color of the node that discovered it, and returns False the instant an edge connects two nodes already colored the same. If the BFS completes with no such conflict, the graph is bipartite and the accumulated coloring is a valid 2-coloring, returned alongside True.

Structured elaboration

Why BFS coloring works. In a bipartite graph, every edge must connect the two groups, never two nodes within the same group, so any correct 2-coloring must alternate colors across every edge. BFS naturally colors nodes by their distance parity from the component's start node (all nodes at even distance get one color, all nodes at odd distance get the other), and this is EXACTLY a valid bipartition whenever one exists, because two nodes connected by a direct edge always differ in BFS distance by exactly 1 in a correctly-behaving coloring, guaranteeing opposite colors. A conflict (an edge whose endpoints end up the same color) can only arise when the graph structure forces two nodes at the same distance-parity from the start to also be directly connected, which happens precisely when an odd-length cycle exists.

Handling disconnection. Nodes with no path to the component the algorithm happened to start with have no BFS-derived color yet; the outer loop over every node index ensures each such component gets its OWN independent coloring pass, since disconnected components impose no constraint on each other's color choice.

Complexity. $O(V+E)$: every node is colored exactly once, and every edge is examined at most twice (once from each endpoint) across the whole run, the same bound as any BFS/DFS traversal over the full graph.

Worked example

from collections import deque
from typing import List, Optional, Tuple

def is_bipartite(graph: List[List[int]]) -> Tuple[bool, Optional[List[int]]]:
    n = len(graph)
    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False, None
    return True, color

if __name__ == "__main__":
    # Case 1: bipartite (square, 0-1-2-3-0)
    graph1 = [[1, 3], [0, 2], [1, 3], [2, 0]]
    ok1, coloring1 = is_bipartite(graph1)
    print("graph1:", graph1)
    print("is_bipartite:", ok1, "coloring:", coloring1)

    # Case 2: NOT bipartite (triangle, 0-1-2-0)
    graph2 = [[1, 2], [0, 2], [0, 1]]
    ok2, coloring2 = is_bipartite(graph2)
    print("\ngraph2:", graph2)
    print("is_bipartite:", ok2, "coloring:", coloring2)

    # Case 3: disconnected, mix of a bipartite path and an isolated node
    graph3 = [[1], [0, 2], [1], []]
    ok3, coloring3 = is_bipartite(graph3)
    print("\ngraph3:", graph3)
    print("is_bipartite:", ok3, "coloring:", coloring3)

Output:

graph1: [[1, 3], [0, 2], [1, 3], [2, 0]]
is_bipartite: True coloring: [0, 1, 0, 1]

graph2: [[1, 2], [0, 2], [0, 1]]
is_bipartite: False coloring: None

graph3: [[1], [0, 2], [1], []]
is_bipartite: True coloring: [0, 1, 0, 0]

Graph 1 (a 4-node cycle) two-colors cleanly ([0,1,0,1], alternating perfectly around the cycle). Graph 2 (a 3-node cycle, a triangle, the smallest possible odd cycle) fails, correctly returning None for the coloring rather than a partial or misleading result. Graph 3 (a disconnected graph: a 3-node bipartite path 0-1-2 plus an isolated node 3) succeeds, and node 3, having no edges, keeps whatever color the outer loop happens to assign it (color 0 here, since it starts its own trivial single-node component); an isolated node can never itself cause a conflict, since it has no edges to check.

Trade-offs and pitfalls

• Common mistake: returning False but still returning a PARTIAL, invalid coloring array instead of None (or otherwise clearly signaling invalidity). A caller that does not carefully check the boolean first could mistake a partial, contradiction-containing coloring for a genuine 2-coloring; returning None for the coloring on the False path makes this class of bug impossible rather than merely unlikely.
• Common mistake: only starting BFS once, from node 0. On a graph with disconnected components, this leaves later components entirely uncolored and unchecked; the fix is looping the outer for start in range(n) over every node, which this implementation does correctly.
• An isolated node is trivially bipartite on its own (it has no edges to violate the bipartition condition), and this implementation handles it for free: it becomes its own singleton component, gets colored, and the while-loop body (which only runs on an edge) never executes for it.
• This early-returns on the FIRST conflict found, which is efficient (no wasted work continuing to color a graph already known non-bipartite) but means the specific coloring state at the moment of the return is an implementation artifact of traversal order, not something a caller should read any meaning into beyond "a conflict exists somewhere."