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

Serialize by writing every node exactly once (iterate the graph's key set, not a traversal frontier, so there is nothing to loop forever on) along with its adjacency list, then deserialize by rebuilding all declared nodes first and filling in adjacency second. The cycle-safety comes entirely from never using recursion or a visited-during-DFS approach to drive the writing process; a flat iteration over "all nodes I know about" has no notion of "currently in progress" to loop back into.

Structured elaboration

Why a DFS-style walk is the wrong approach here. A naive serializer that recursively follows edges to decide what to write next needs a visited set to avoid infinite recursion on a cycle, and even then it complicates the "avoid duplicating nodes" requirement (you would need to make sure a node visited via one path is not re-emitted via another). Iterating the graph's own node set sidesteps this entirely: every node is a top-level key in the input, so there is exactly one place each node's adjacency list gets written, independent of how many cycles or how much fan-in the graph contains.

Preserving node identity. Each node keeps its original id as its map key in the serialized form; deserialization uses that same id both when creating the node and when resolving every neighbor reference, so two edges pointing at the same node in the original graph point at the same reconstructed node afterward, not two independent copies.

Disconnected graphs. Because serialization iterates every key in the input dict, a node with no incoming edges (isolated, or the root of its own separate component) is still visited and written with an empty (or non-empty) adjacency list; nothing about the approach depends on reachability from a single starting point.

Worked example

import json
from typing import Dict, List, Any

def serialize(graph: Dict[Any, List[Any]]) -> str:
    '''Serialize a directed graph (possibly with cycles) to a JSON string.
    Each node is written exactly once; disconnected nodes (present as keys
    with no incoming edges) are preserved because we iterate graph.keys(),
    not a traversal frontier, so there is no traversal to loop forever on.'''
    node_ids = sorted(graph.keys(), key=str)
    payload = {
        "nodes": [str(n) for n in node_ids],
        "edges": {str(n): [str(v) for v in graph[n]] for n in node_ids},
    }
    return json.dumps(payload, separators=(",", ":"), sort_keys=True)

def deserialize(s: str) -> Dict[str, List[str]]:
    data = json.loads(s)
    nodes = [str(n) for n in data["nodes"]]
    edges = {str(k): [str(v) for v in vs] for k, vs in data["edges"].items()}
    graph: Dict[str, List[str]] = {n: edges.get(n, []) for n in nodes}
    # any node referenced only as a target gets an empty adjacency entry
    for src, nbrs in edges.items():
        for nb in nbrs:
            if nb not in graph:
                graph[nb] = []
    return graph

if __name__ == "__main__":
    # Directed graph WITH a cycle (A -> B -> C -> A) plus a disconnected node D
    g = {"A": ["B"], "B": ["C"], "C": ["A", "B"], "D": []}
    s = serialize(g)
    print("Serialized:", s)

    g2 = deserialize(s)
    print("Deserialized:", g2)

    same_edges = {k: sorted(v) for k, v in g.items()} == {k: sorted(v) for k, v in g2.items()}
    print("Round-trip preserves adjacency exactly:", same_edges)
    print("Disconnected node D preserved with empty list:", g2.get("D") == [])

    # Larger cyclic graph, confirm serialization terminates and is idempotent
    big = {str(i): [str((i + 1) % 500), str((i + 250) % 500)] for i in range(500)}
    s_big = serialize(big)
    g_big = deserialize(s_big)
    print("500-node cyclic graph round-trips:", g_big == big)
    print("Serialized length (chars) for 500-node graph:", len(s_big))

Output (actually executed with python3):

Serialized: {"edges":{"A":["B"],"B":["C"],"C":["A","B"],"D":[]},"nodes":["A","B","C","D"]}
Deserialized: {'A': ['B'], 'B': ['C'], 'C': ['A', 'B'], 'D': []}
Round-trip preserves adjacency exactly: True
Disconnected node D preserved with empty list: True
500-node cyclic graph round-trips: True
Serialized length (chars) for 500-node graph: 12581

Complexity

• Serialize: $O(V + E)$ time (visit every node once, every adjacency entry once), $O(V + E)$ output size.
• Deserialize: $O(V + E)$ time to parse and rebuild both the node set and every adjacency entry.

Edge cases

• Self-loops (a node listing itself as a neighbor): serialized and deserialized like any other edge, no special handling needed since nothing here depends on traversal state.
• Node ids that are not strings: cast to strings at serialization time so they are valid JSON object keys, and cast back only if the caller's original id type is known; the example above keeps everything as strings after a round trip, which the caller should account for if the original graph used integer ids.
• A neighbor referenced in some node's adjacency list but never itself a top-level key in the input: still gets an empty adjacency entry on deserialize, so the reconstructed graph is never missing a node that any edge points at.

Trade-offs and pitfalls

• Versioning and security when parsing. Once this format is used across service boundaries or persisted to disk, add an explicit "version" field to the payload so a future format change can be detected and migrated rather than silently misparsed, and treat json.loads output as untrusted input, cap the maximum nodes/edges accepted before deserializing fully, and validate that every neighbor id referenced actually resolves, rather than trusting the payload's internal consistency.
• Large graphs. The approach above builds the full JSON string in memory. For graphs that do not fit in memory as one object, switch to NDJSON (one node's record per line) or a streaming JSON writer that emits nodes incrementally, and a streaming parser on the read side; this keeps the same "iterate the full node set once" property without requiring the whole graph to be materialized as one string at once.
• Common mistake: trying to serialize via a DFS/BFS traversal starting from an arbitrary root, which will miss any node not reachable from that root (silently dropping disconnected components) unless the code explicitly restarts the traversal from every unvisited node, at which point it has reinvented "iterate the full node set," just with extra steps and extra cycle-safety bookkeeping that iterating the node set directly never needed in the first place.

Direct answer

Run breadth-first search (BFS) from the source, but instead of expanding until the queue empties, process the graph one full layer ("hop") at a time and stop after $k$ layers. A single visited set shared across all layers guarantees each node is discovered exactly once, at its true minimum hop distance, even when it has multiple potential parents.

Structured elaboration

The layer-by-layer discipline is what makes both outputs correct simultaneously: counts_per_hop[i] needs to be exactly the number of NEW nodes discovered at hop $i$, and the flattened list needs each node exactly once. Both fall out of processing the current frontier completely before starting the next one, and marking a node visited the moment it is first discovered (not when it is later expanded), so a node reachable from two different nodes in the current frontier is still only counted and appended once, whichever edge reaches it first in iteration order.

Worked example

from collections import deque
from typing import Dict, Iterable, List, Tuple

def k_hop_neighbors(graph: Dict[int, Iterable[int]], source: int, k: int) -> Tuple[List[int], List[int]]:
    '''Returns (counts_per_hop, flattened_nodes_within_k_hops); counts_per_hop[0] is the source itself.'''
    if k < 0:
        raise ValueError("k must be non-negative")
    visited = {source}
    frontier = [source]
    counts_per_hop = [1]
    flattened = [source]
    for _ in range(k):
        next_frontier = []
        for node in frontier:
            for nb in graph.get(node, ()):
                if nb not in visited:
                    visited.add(nb)
                    next_frontier.append(nb)
        counts_per_hop.append(len(next_frontier))
        flattened.extend(next_frontier)
        frontier = next_frontier
        if not frontier:
            counts_per_hop.extend([0] * (k - len(counts_per_hop) + 1))
            break
    return counts_per_hop, flattened

if __name__ == "__main__":
    # Diamond shape: nodes 3 and 4 both connect to 5, testing that 5 is discovered once, not twice
    graph = {
        0: [1], 1: [0, 2], 2: [1, 3, 4], 3: [2, 5], 4: [2, 5], 5: [3, 4, 6], 6: [5],
    }
    counts, flat = k_hop_neighbors(graph, source=0, k=10)
    print("counts_per_hop (hop 0..6, then zeros once exhausted):", counts)
    print("all reachable nodes, flattened:", sorted(flat))
    print("sum of counts equals total reachable nodes:", sum(counts) == len(graph))
    print("node 5 (reachable via both 3 and 4) counted at hop 4, exactly once, not twice:", counts[4] == 1)

Output (actually executed with python3):

counts_per_hop (hop 0..6, then zeros once exhausted): [1, 1, 1, 2, 1, 1, 0, 0, 0, 0, 0]
all reachable nodes, flattened: [0, 1, 2, 3, 4, 5, 6]
sum of counts equals total reachable nodes: True
node 5 (reachable via both 3 and 4) counted at hop 4, exactly once, not twice: True

Complexity

• Time: $O(V + E)$ across the full traversal (each node is added to a frontier once, each edge examined at most once from each endpoint), independent of $k$ except that a smaller $k$ can stop early and touch fewer nodes.
• Space: $O(V)$ for the visited set and the largest single frontier.

Edge cases

• k = 0: returns ([1], [source]), only the source itself, no neighbors examined.
• Source not present as a key in the graph: graph.get(source, ()) on the first expansion attempt simply yields nothing further, so the function returns just the source with all subsequent hop counts at 0, rather than raising.
• Graph exhausted before reaching $k$ hops (a small or disconnected component): the loop detects an empty next_frontier and pads the remaining hop counts with 0 instead of continuing to iterate uselessly.
• Cycles and nodes with multiple parents in the current frontier: handled by the shared visited set, demonstrated above with node 5.

Trade-offs and pitfalls

• Common mistake: using a single global BFS without per-layer boundaries and trying to infer hop counts from insertion order after the fact; this is fragile and error-prone compared to explicitly processing one frontier at a time.
• Common mistake: checking visited only when a node is DEQUEUED rather than when it is first discovered and added to next_frontier; that allows the same node to be pushed multiple times within a single layer whenever it has more than one parent in the current frontier, corrupting the hop counts (this is exactly the diamond case tested above).
• For repeated queries with different sources on the same static graph, a batch multi-source BFS or a precomputed all-pairs structure (or, for large-scale feature engineering, sparse matrix powers) avoids repeating the same $O(V+E)$ work per query.
• If the frontier can grow explosively (a highly connected graph and a large $k$), consider capping the total node budget or sampling the frontier rather than letting a single call materialize an unbounded flattened list.

Direct answer

Marking a node visited when it is first DISCOVERED (enqueued, or pushed) versus when it is actually PROCESSED (dequeued, or popped) is not a stylistic choice, it changes correctness. Discovery-time marking guarantees each node enters the frontier exactly once, which is what breadth-first search (BFS) needs for its shortest-path guarantee to hold and what any traversal needs to bound total work to $O(V+E)$. Processing-time marking lets the same node be enqueued multiple times by different discoverers before any of those copies is ever processed, wasting work and, in a concurrent setting, creating a real race.

Structured elaboration

Mark-on-discovery (enqueue/push time). The moment a neighbor is first seen, it is marked visited and added to the frontier, before the algorithm ever looks at it again. Correctness: guarantees each node is scheduled exactly once, since every subsequent discovery of the same node is rejected by the visited check before it can be re-added. Duplicate work: none, by construction. Cycle detection: sufficient for BFS (an infinite loop on a cycle is prevented because a cycle's nodes are never rediscovered), but NOT sufficient on its own for detecting a directed cycle during DFS, since a plain boolean "seen" flag cannot distinguish a node that is still being explored (on the current path) from one that finished long ago. Multi-source: trivial, mark every source visited before the traversal begins, so no source is ever re-added by another source's exploration. Parallel traversals: safer, since the mark-and-claim step happens once, before any work is dispatched, so an atomic compare-and-set on the visited marker is enough to guarantee two workers never both claim the same node.

Mark-on-processing (dequeue/pop time). A node is only marked visited once the algorithm actually gets around to working on it. Correctness: still eventually correct for a simple existence/reachability check, but WRONG for BFS's shortest-path guarantee under certain implementations, since a node can be enqueued multiple times (once per discoverer) before any copy is processed, and depending on queue order, a node might get its distance recorded from a LATER, longer discovery rather than the first, shortest one, if the implementation naively overwrites distance on every dequeue rather than checking a distance already set. Duplicate work: real and often significant, since the same node can sit in the queue multiple times, each copy doing a full "look at my neighbors" pass when eventually processed. Cycle detection: also insufficient alone, for the same white/gray/black reason below. Multi-source: risk of the same node being queued once per source that reaches it, inflating queue size unnecessarily. Parallel traversals: genuinely problematic, since two workers can both see a node as "not yet marked" and both dispatch work on it before either finishes marking it, a textbook race condition requiring an explicit atomic claim step to fix, which mark-on-discovery gets for free by marking BEFORE dispatching any work.

Color states (white, gray, black), the mechanism that fixes what plain marking cannot. White: undiscovered. Gray: discovered, currently being explored (on the active depth-first search path). Black: fully finished, nothing reachable from it remains unexplored. This is strictly more informative than a boolean visited flag: a boolean can only say "seen or not," while color additionally distinguishes "seen and still in progress" from "seen and done." That distinction is exactly what directed-cycle detection needs: encountering an edge into a GRAY node (one still on the current path) means a back edge into an ancestor, a genuine cycle; encountering an edge into a BLACK node means the target was already fully explored via some other path, not a cycle. A plain visited-on-discovery boolean cannot tell these two cases apart, which is why cycle detection specifically needs the three-state version, not merely "was this node marked."

Worked example

Consider a small directed graph: $0 \to 1$, $0 \to 2$, $1 \to 3$, $2 \to 3$, $3 \to 1$ (a back edge creating the cycle $1 \to 3 \to 1$).

Running DFS from 0 with color states: visit 0 (white to gray), visit 1 (white to gray), visit 3 (white to gray), examine 3's edge to 1: 1 is currently GRAY (still on the active path, 0 to 1 to 3), so this is a back edge, a cycle is correctly reported. Contrast with a plain boolean visited-on-discovery DFS: visit 0 (mark visited), visit 1 (mark visited), visit 3 (mark visited), examine 3's edge to 1: 1 is marked visited, and a naive boolean check alone cannot tell whether that means "1 is an ancestor on my current path" (a cycle) or "1 was already fully explored via some unrelated path" (not a cycle); it would need the color distinction, or an equivalent explicit "currently on stack" set, to tell the two apart correctly.

Trade-offs and pitfalls

• Common mistake: using a plain visited set for DFS cycle detection and expecting it to work like BFS's visited set does. BFS never needs the three-state distinction because BFS has no notion of "still in progress on the current path" the way DFS's call stack does; a boolean is genuinely sufficient there. Porting that same boolean pattern to DFS cycle detection is the single most common source of an "our cycle detector missed a real cycle" or "false-positived on a shared-descendant DAG" bug.
• Common mistake: implementing recursive DFS with a single shared visited set across the whole traversal but forgetting to distinguish "in the current recursion's ancestor chain" from "visited by an earlier, now-finished sibling call." The gray/black split (or an explicit in_progress set that gets removed on backtrack, functionally equivalent) is exactly what an iterative, explicit-stack DFS must also replicate correctly; converting recursive DFS to iterative and dropping this distinction along the way is a real, easy-to-introduce regression.
• Parallel or distributed traversals. Beyond the local correctness question, dispatching work to multiple workers needs the CLAIM step itself to be atomic (a compare-and-set on a shared visited marker, or a lease with an expiry), not merely "check then mark" as two separate, non-atomic operations; two workers can both pass the check before either performs the mark, exactly the race mark-on-discovery avoids only if the mark itself is atomic with respect to the check.
• Recursion-vs-iterative equivalence. A recursive DFS's own call stack implicitly IS the gray set (a node is on the call stack exactly while it is gray); converting to an iterative, explicit-stack version requires either maintaining an explicit gray set alongside the stack or, if the stack contents alone are used as a proxy for "in progress," being careful that a node popped off the explicit stack for backtracking purposes is correctly treated as no longer gray, not still considered in-progress.

Direct answer

Plain Kahn's algorithm with a FIFO queue produces a valid topological order, but which one depends on insertion order among tied, simultaneously-available vertices. To force the lexicographically smallest valid order (smallest by node id, compared position by position), replace the queue with a min-heap: at every step, among all vertices currently free of unmet dependencies, always emit the smallest id. This is a small structural change with a real complexity cost: $O((V+E)\log V)$ instead of $O(V+E)$, because every insertion and extraction on the heap costs $O(\log V)$.

Structured elaboration

The algorithm is Kahn's algorithm verbatim except for one substitution: swap deque for heapq. Correctness for cycle detection is unchanged (a cycle still means some vertices never reach in-degree 0, so the output stays short); the only new property is that whenever more than one vertex is simultaneously eligible, the heap always yields the smallest one first, which is exactly the greedy rule that produces the lexicographically smallest sequence: committing to the smallest available choice at every position, given that any later choice is still available to be picked in a later position if it becomes newly eligible.

Why greedy-smallest-first is provably correct here (not just plausible). Suppose the true lexicographically smallest valid order picks vertex $x$ at some position, but $x$ is not the smallest currently-eligible vertex; call the smallest eligible one $y < x$. Since $y$ has no unmet dependency, nothing prevents placing $y$ at that position instead, and $y$'s own dependents only become eligible later regardless of whether $y$ is placed now or later, so swapping $y$ into that earlier position can only make the sequence lexicographically smaller or equal, never invalid. This is the standard exchange argument for greedy algorithms; it is why the heap substitution alone (no other logic change) is sufficient.

Worked example

import heapq
from typing import Dict, List, Optional

def topo_lex(graph: Dict[int, List[int]]) -> Optional[List[int]]:
    # Kahn's algorithm with a min-heap instead of a FIFO queue: among all
    # nodes currently available (indegree 0), always pop the smallest id.
    # Returns the lexicographically smallest valid topological order, or
    # None if the graph has a cycle.
    indegree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1

    heap = [u for u in graph if indegree[u] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        u = heapq.heappop(heap)
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                heapq.heappush(heap, v)

    if len(order) != len(graph):
        return None
    return order

if __name__ == "__main__":
    dag = {5: [2, 0], 4: [0, 1], 2: [3], 3: [1], 0: [], 1: []}
    result = topo_lex(dict(dag))
    print("Lexicographically smallest order:", result)

    def is_valid_topo(order, graph):
        pos = {n: i for i, n in enumerate(order)}
        return all(pos[u] < pos[v] for u in graph for v in graph[u])
    print("Valid topological order:", is_valid_topo(result, dag))

    from itertools import permutations
    nodes = list(dag.keys())
    valid_orders = [list(p) for p in permutations(nodes) if is_valid_topo(list(p), dag)]
    brute_min = min(valid_orders)
    print("Brute-force minimum over all valid orders:", brute_min)
    print("Matches heap-based result:", brute_min == result)

    cyclic = {0: [1], 1: [2], 2: [0]}
    print("Cyclic graph result:", topo_lex(dict(cyclic)))

Output (actually executed with python3):

Lexicographically smallest order: [4, 5, 0, 2, 3, 1]
Valid topological order: True
Brute-force minimum over all valid orders: [4, 5, 0, 2, 3, 1]
Matches heap-based result: True
Cyclic graph result: None

The brute-force check enumerates every permutation of the six vertices, keeps only the ones that respect every edge, and takes the minimum by standard list (lexicographic) comparison. This is only feasible for the toy example ($6! = 720$ permutations) and exists purely to independently confirm the heap-based algorithm's exchange argument holds on a real case, not as a scalable approach in itself.

Complexity

Time $O((V+E)\log V)$: every vertex is pushed and popped from the heap once ($O(V \log V)$ total), and every edge triggers at most one additional push when its target's in-degree reaches zero ($O(E \log V)$ total). Space $O(V)$ for the heap and in-degree map, plus $O(V+E)$ for the adjacency list.

Edge cases

• All vertices tied at in-degree 0 (a totally disconnected graph): the heap degenerates to simply popping vertices in ascending id order, which is correct and matches the lexicographically-smallest definition trivially.
• A long single chain ($0\to1\to2\to\dots$): only one vertex is ever eligible at a time, so the heap never actually has a choice to make; the result is forced and identical to what plain Kahn's algorithm would produce.
• Cycle: identical detection to plain Kahn's algorithm, None when the output falls short of len(graph).
• Negative or non-integer ids: the heap comparison works for any totally ordered, hashable type, so this generalizes to string ids (alphabetical order) without changing the algorithm, only the type annotation.

Trade-offs and pitfalls

• Common mistake: assuming a plain, unmodified Kahn's algorithm with a FIFO queue already gives the lexicographically smallest order "because it processes in the order things become available." That is false in general: two vertices can become eligible in the same round, and FIFO preserves insertion order (which reflects the order their prerequisites happened to be processed in), not numeric order. Only replacing the queue's tie-breaking mechanism with an explicit min-heap (or a per-round sort) fixes this.
• Common mistake: sorting the entire vertex list once at the start and iterating in that fixed order while checking in-degree, instead of using a heap. This looks similar but is wrong: a vertex with a smaller id can become eligible several rounds after a vertex with a larger id, and a single static sort pass cannot re-examine a vertex once skipped in an earlier scan, or would need to re-scan the whole list every round, which is $O(V)$ per round instead of $O(\log V)$ per operation.
• This exact technique (a min-heap-based topological sort relying on the same exchange-argument correctness) shows up repeatedly in practice, confirming it is a stable, recognized approach rather than an unusual one-off construction; the min-heap substitution is the standard way this requirement is solved, not a workaround.
• The $O(\log V)$ factor genuinely matters at scale: for a graph with $V=10^6$ vertices, plain Kahn's algorithm and the lexicographic variant differ by roughly a factor of 20, which is worth naming explicitly if a system does not actually need reproducible ordering and is paying this cost for no functional benefit.