Graphs and Graph Algorithms Questions

Direct answer

Running depth-first search (DFS) on a directed graph and recording, for every vertex $v$, a discovery time $d[v]$ (when DFS first reaches $v$) and a finish time $f[v]$ (when DFS has fully explored everything reachable from $v$ and returns), every edge $(u,v)$ falls into exactly one of four categories based on how those two intervals relate: tree, forward, back, or cross.

Structured elaboration

• Tree edge. $(u,v)$ is the edge DFS actually used to first discover $v$; $v$ becomes a child of $u$ in the DFS tree. Formally, $d[u] < d[v] < f[v] < f[u]$, and $v$'s discovery immediately follows $u$'s.
• Forward edge. $(u,v)$ points to a vertex $v$ that is a descendant of $u$ in the DFS tree, but was NOT the edge that first discovered $v$ (some other tree edge got there first, deeper in the recursion). Formally, the same interval containment as a tree edge, $d[u] < d[v] < f[v] < f[u]$, but $(u,v)$ is not the tree edge itself.
• Back edge. $(u,v)$ points to an ANCESTOR of $u$ in the DFS tree, that is, to a vertex still "in progress" (discovered but not yet finished) when $u$ is processed. Formally, $d[v] < d[u] < f[u] < f[v]$, the ancestor's interval contains the descendant's.
• Cross edge. $(u,v)$ points to a vertex $v$ that is neither an ancestor nor a descendant of $u$, typically in an already-finished, unrelated branch of the DFS tree. Formally, the two intervals are disjoint: $f[v] < d[u]$.

Relation to cycle detection. A directed graph contains a cycle if and only if DFS finds at least one back edge. This is because a back edge $(u,v)$ points at a vertex $v$ still on the current recursion path (an ancestor), so the tree-path from $v$ down to $u$, plus the edge $u \to v$, forms an explicit cycle. No back edge means no such "return to an in-progress ancestor" ever happens, which is exactly the absence of a directed cycle.

Relation to topological sorting. A directed acyclic graph (DAG, a directed graph with no cycles) has no back edges by the fact above. For every edge $(u,v)$ in a DAG, DFS's structure guarantees $f[u] > f[v]$ (this holds for tree, forward, and cross edges alike, and back edges cannot occur). So sorting vertices by DECREASING finish time produces an order where every edge points from an earlier vertex to a later one, exactly the definition of a valid topological order.

Worked example

Take the directed graph: $A \to B$, $A \to C$, $B \to C$, $C \to D$, $D \to B$. Running DFS from A, visiting neighbors in listed order:

Classification summary: $A\to B$ and $B\to C$ (the first time, via $A \to B \to C$) and $C \to D$ are TREE edges (they are the edges DFS actually used to first discover B, C, and D). $D \to B$ is a BACK edge (reveals the cycle $B \to C \to D \to B$). $A \to C$ is a FORWARD edge (C already reachable and discovered as A's descendant before this edge is examined). This graph has no cross edge at all; a genuine cross-edge example needs two sibling subtrees, for instance adding a vertex E with edges $A \to E$ and $E \to C$ after C is already finished would make $E \to C$ a cross edge (pointing into an already-finished, unrelated branch).

Trade-offs and pitfalls

• Common mistake: trying to classify an edge using only discovery time, without finish time. Discovery time alone cannot distinguish a forward edge from a cross edge in some graph shapes; the finish-time containment (or lack of it) is what actually distinguishes ancestor/descendant relationships from unrelated branches.
• Undirected graphs only have tree edges and back edges, no forward or cross edges. This is because in an undirected graph, an edge $(u,v)$ examined from $u$ toward an already-visited $v$ is the exact same edge as $(v,u)$ examined earlier from $v$'s own exploration, so what would be a "forward" edge from one direction is simply the same back edge already counted from the other direction; the four-way classification is specifically a directed-graph concept.
• The back-edge-implies-cycle result is exactly what a production cycle detector (for example, checking a dependency graph for circular dependencies) implements under the hood, usually via the lighter "white/gray/black" color-marking scheme rather than literal discovery/finish timestamps, gray is equivalent to "discovered but not yet finished," so a back edge is precisely an edge into a currently-gray node.

Direct answer

Compute each task's earliest start and earliest finish time with a single forward pass over a topological ordering of the dependency DAG: a task's earliest start is the maximum earliest-finish among all its direct predecessors (0 if it has none), and its earliest finish is its earliest start plus its own duration. The overall project completion time is the maximum earliest-finish across every task, and the critical path (the sequence of tasks that directly determines that completion time, with zero slack) is the longest path through the DAG when edges are weighted by task duration; this is exactly the classical critical path method (CPM), computed as a longest-path-in-a-DAG problem using topological order in place of Dijkstra/Bellman-Ford (neither of which is needed, since a DAG's topological order alone is sufficient to relax every edge exactly once in a correct dependency order).

Structured elaboration

Why topological order is sufficient (no shortest/longest-path algorithm needed). A task's earliest finish only depends on its predecessors' earliest finish times, which must already be known before that task can be processed. A topological order guarantees every predecessor of a task appears before it in the processing sequence, so a single forward pass, processing tasks in topological order and updating each successor's earliest-start as soon as a predecessor finishes, correctly computes every earliest-finish time in one $O(V+E)$ pass, with no need for a priority queue or repeated relaxation the way Dijkstra or Bellman-Ford would require.

Algorithm (Kahn's-algorithm-style, computing earliest-finish as tasks are dequeued):

1. Compute in-degree for every task; task with in-degree 0 have earliest_start = 0.
2. Process tasks via a queue seeded with all in-degree-0 tasks (standard Kahn's algorithm). When a task u is dequeued: earliest_finish[u] = earliest_start[u] + duration[u]. For every successor v of u: earliest_start[v] = max(earliest_start[v], earliest_finish[u]), decrement v's in-degree, and enqueue v once its in-degree reaches 0.
3. The project completion time is max(earliest_finish.values()) across all tasks.

Modifying for resource-constrained scheduling (limited parallel workers). The unconstrained calculation above implicitly assumes UNLIMITED parallelism, every task with satisfied dependencies can start immediately. With only k workers, tasks whose dependencies are satisfied but who cannot get a free worker must WAIT even though the dependency graph alone would allow them to start, which turns this from a pure graph problem into resource-constrained project scheduling (RCPSP), a materially harder problem: RCPSP is NP-hard in general, unlike the polynomial-time unconstrained CPM calculation. A common practical approach is a priority-based simulation: at every point in simulated time, among all tasks whose dependencies are satisfied and are not yet running, greedily assign available workers by some priority rule (commonly least-slack-first, prioritizing tasks on or nearest to the critical path, since delaying THOSE tasks directly delays the project, while tasks with slack can absorb some worker-availability delay without affecting the overall completion time).

Worked example

from collections import deque
from typing import Dict, List

def earliest_completion(n: int, adj: Dict[int, List[int]], duration: Dict[int, int]):
    indeg = {u: 0 for u in range(n)}
    for u in adj:
        for v in adj[u]:
            indeg[v] += 1
    q = deque([u for u in range(n) if indeg[u] == 0])
    topo = []
    earliest_start = {u: 0 for u in range(n)}
    earliest_finish = {}
    while q:
        u = q.popleft()
        topo.append(u)
        earliest_finish[u] = earliest_start[u] + duration[u]
        for v in adj.get(u, []):
            earliest_start[v] = max(earliest_start[v], earliest_finish[u])
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if len(topo) != n:
        raise ValueError("graph has a cycle; no valid topological order")
    return earliest_finish, max(earliest_finish.values()), topo

if __name__ == "__main__":
    # 6 tasks (0..5): 0=build(3h) -> 1=docs(1h), 2=test(2h)
    # 1=docs -> 3=review(2h); 2=test -> 3=review, 4=package(1h)
    # 3=review -> 5=release(1h); 4=package -> 5=release
    n = 6
    duration = {0: 3, 1: 1, 2: 2, 3: 2, 4: 1, 5: 1}
    adj = {0: [1, 2], 1: [3], 2: [3, 4], 3: [5], 4: [5], 5: []}
    finish, total, topo = earliest_completion(n, adj, duration)
    print("topological order:", topo)
    print("earliest finish times:", finish)
    print("project completion time:", total)
    serial_total = sum(duration[u] for u in topo)
    print("fully-serial (1 worker) total:", serial_total)

Output:

topological order: [0, 1, 2, 3, 4, 5]
earliest finish times: {0: 3, 1: 4, 2: 5, 3: 7, 4: 6, 5: 8}
project completion time: 8
fully-serial (1 worker) total: 10

Hand trace confirms the algorithm: start(0)=0, finish(0)=3. start(1)=finish(0)=3, finish(1)=4. start(2)=finish(0)=3, finish(2)=5. start(3)=max(finish(1)=4, finish(2)=5)=5, finish(3)=7. start(4)=finish(2)=5, finish(4)=6. start(5)=max(finish(3)=7, finish(4)=6)=7, finish(5)=8. The critical path is 0-2-3-5 (durations 3+2+2+1=8), the longest chain of dependent tasks, exactly matching the computed project completion time of 8. With unlimited parallelism the project finishes in 8 hours; with only 1 worker (fully serial, everything runs one after another in ANY valid topological order), it takes the sum of all durations, 10 hours, a useful sanity bound: the true resource-constrained answer for any worker count between 1 and unlimited must fall between 8 (the critical path lower bound, unbeatable no matter how many workers) and 10 (the fully-serial upper bound) hours.

Trade-offs and pitfalls

• Common mistake: computing earliest-start/earliest-finish in an order that is topologically valid for the WRONG direction, or accidentally using arrival order instead of a true topological order; if any predecessor is processed after one of its successors, that successor's earliest-start would be computed using a stale (too-small) predecessor finish time, silently understating the true completion time.
• The unconstrained calculation ($k = \infty$ workers) is a LOWER BOUND, never the true answer once a worker limit is introduced; a design that reports the unconstrained critical-path length as "the" completion time when workers are actually limited is reporting an optimistic, achievable-only-under-infinite-parallelism number, not the real constrained schedule.
• RCPSP (resource-constrained scheduling) is NP-hard, so an exact optimal schedule for large task counts under a worker limit is not efficiently computable in general; production systems use heuristics (least-slack-first, critical-path-first) that are good in practice but not provably optimal, a trade-off worth naming explicitly rather than implying a limited-worker schedule can always be computed exactly and efficiently.
• The fully-serial bound (sum of all durations) is only a valid upper bound when there is exactly 1 worker; with k > 1 but k < infinity, the achievable completion time lies somewhere between the critical-path lower bound and the fully-serial upper bound, and where exactly depends on the specific priority heuristic used and the DAG's branching structure, not on a simple closed-form formula.

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

Use an explicit stack and a visited set; check whether the popped node is the target BEFORE checking or updating visited state, so the function can return True the instant the target is discovered rather than waiting to fully process it. This early exit is the main performance lever over a full traversal, since for many queries the target is found long before the rest of the graph would have been explored.

Structured elaboration

Path existence between two nodes only needs a yes/no answer, so nothing about a full traversal's bookkeeping (discovery order, per-node results) is required. The traversal can stop the instant the target is popped from the stack, rather than finishing whatever level or subtree it happens to be in. A visited set still guards against revisiting nodes on graphs with cycles, exactly as in any other DFS, but the check for "is this the target" happens first, ahead of the visited check, so that even a target reachable through a cycle is caught immediately rather than only after normal traversal bookkeeping would have gotten to it.

Worked example

def has_path_iterative_dfs(graph, start, target):
    if start not in graph and start != target:
        return False
    if start == target:
        return True
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node == target:
            return True
        if node in visited:
            continue
        visited.add(node)
        for nbr in graph.get(node, []):
            if nbr not in visited:
                stack.append(nbr)
    return False

if __name__ == "__main__":
    graph = {
        "A": ["B", "C"],
        "B": ["D"],
        "C": ["D"],
        "D": ["A"],   # cycle back to A
        "E": ["F"],   # separate component, unreachable from A
        "F": [],
    }
    print("A -> D reachable:", has_path_iterative_dfs(graph, "A", "D"))
    print("A -> E reachable (different component):", has_path_iterative_dfs(graph, "A", "E"))
    print("A -> A trivial (same node):", has_path_iterative_dfs(graph, "A", "A"))
    print("Z -> A, Z missing from graph:", has_path_iterative_dfs(graph, "Z", "A"))

    # Early-exit proof: on a long chain, reaching the immediate neighbor of start
    # should not require expanding the rest of a huge unrelated subgraph.
    chain = {i: [i + 1] for i in range(100000)}
    print("Long chain of 100000 nodes, 0 -> 1 found:", has_path_iterative_dfs(chain, 0, 1))

Output (actually executed with python3):

A -> D reachable: True
A -> E reachable (different component): False
A -> A trivial (same node): True
Z -> A, Z missing from graph: False
Long chain of 100000 nodes, 0 -> 1 found: True

Complexity

• Worst case (target unreachable, or reachable only after exploring most of the graph): time $O(V + E)$, each node and edge examined at most once.
• Best case (target adjacent to start or found early): far less than a full traversal, the early exit on the node == target check returns as soon as the target is popped.
• Space: $O(V)$ for the visited set; stack size in the worst case also $O(V)$, bounded by the longest unexplored path currently pending.

Edge cases

• start == target: handled explicitly up front, returns True immediately without touching the graph at all.
• start missing from the graph entirely (not even a value somewhere): returns False immediately rather than attempting a lookup that would find nothing anyway.
• Empty graph: no nodes to explore, returns False unless start == target was already caught above.
• Very long chains: the early-exit test above uses a 100,000-node chain and confirms an immediate neighbor is found without materializing or fully walking the rest of the chain.

Trade-offs and pitfalls

• Common mistake: checking node in visited before checking node == target; if the target itself somehow ends up added to visited on an earlier pass through the loop (for instance, if the visited check were structured differently), the function could miss reporting it as found, ordering the target check first avoids this entirely.
• This function only answers existence, not the path itself. If the ACTUAL path is needed, track a parent-pointer map alongside the stack (came_from[neighbor] = node at push time) and reconstruct by walking came_from backward from the target once found.
• For REPEATED path-existence queries between many different pairs on the same static graph, computing connected components once (via a single traversal or union-find) and then answering each query as an O(1) "same component" check is far cheaper than re-running a fresh DFS per query.

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.