Graphs and Graph Algorithms Questions

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

A* extends Dijkstra's algorithm by adding a heuristic estimate $h(n)$ of the remaining cost from node $n$ to the goal, and expanding nodes in order of $f(n) = g(n) + h(n)$ (cost so far plus estimated cost remaining) rather than $g(n)$ alone. When $h$ is admissible (never overestimates the true remaining cost) A* is guaranteed to find an optimal path, exactly like Dijkstra, but typically explores far fewer nodes because the heuristic actively steers the search toward the goal instead of expanding uniformly outward in all directions. A data-engineering example where this matters: map-matching or shortest-route queries over a road or delivery network, where Dijkstra from a single source explores every direction equally, while A* with a straight-line or great-circle distance heuristic concentrates the search toward the destination.

Structured elaboration

Admissibility. $h(n)$ is admissible if $h(n) \le h^*(n)$ for every node $n$, where $h^*(n)$ is the TRUE optimal cost from $n$ to the goal. This is what guarantees A* never prunes away the actual shortest path: since the heuristic never overpromises, a path that looks worse under $f$ can never actually be better in reality than one A* has already committed to exploring first.

Consistency (monotonicity). A stronger property: $h(n) \le \text{cost}(n, n') + h(n')$ for every edge $(n, n')$, i.e., the heuristic obeys its own triangle inequality along every edge. Consistency implies admissibility, and it additionally guarantees that once a node is popped from the open set with its final $g$ value, that value is already optimal and will never be improved later, exactly the same guarantee Dijkstra relies on for non-negative edge weights. Without consistency (an admissible-but-inconsistent heuristic), A* is still correct, but may need to re-open and re-expand a node whose $g$ value improves after it was first popped, which costs extra work without losing correctness.

Designing or validating an admissible heuristic for a road network. Straight-line (Euclidean) or great-circle distance between two points is a standard admissible heuristic for road routing, since no legal road path can ever be shorter than the straight-line distance between its endpoints; it is also consistent, since the triangle inequality holds for straight-line distance by definition. Validating a CANDIDATE heuristic (for example, a learned or precomputed estimate rather than pure geometry) means checking it never exceeds the true shortest-path cost on a representative sample: run exact Dijkstra from a sample of source nodes, compare the heuristic's estimate at every visited node against Dijkstra's own final distance to the goal from that node, and flag any node where the heuristic's estimate exceeds the true cost, since even a single such violation breaks the optimality guarantee for any query that could pass through that node.

Worked example

10x10 unit-cost grid (each step to an orthogonal neighbor costs 1), start at $(0,0)$, goal at $(9,9)$, with a wall at column 5 blocking every row except row 5 (forcing all paths through that single gap), comparing plain Dijkstra ($h = 0$ everywhere) against A* using the Manhattan distance heuristic $h(n) = |n_r - 9| + |n_c - 9|$ (admissible here because Manhattan distance never overestimates unit-step grid cost, and equals the true remaining cost exactly whenever no obstacle lies on the direct path):

import heapq

def neighbors(pos, grid):
    r, c = pos
    rows, cols = len(grid), len(grid[0])
    for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
        nr, nc = r+dr, c+dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
            yield (nr, nc)

def manhattan(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])

def search(grid, start, goal, use_heuristic):
    h = manhattan if use_heuristic else (lambda a, b: 0)
    open_heap = [(h(start, goal), 0, start)]
    best_g = {start: 0}
    expanded = set()
    while open_heap:
        f, g, u = heapq.heappop(open_heap)
        if u in expanded:
            continue
        expanded.add(u)
        if u == goal:
            return g, len(expanded)
        for v in neighbors(u, grid):
            ng = g + 1
            if v not in best_g or ng < best_g[v]:
                best_g[v] = ng
                heapq.heappush(open_heap, (ng + h(v, goal), ng, v))
    return None, len(expanded)

if __name__ == "__main__":
    rows, cols = 10, 10
    grid = [[0]*cols for _ in range(rows)]
    for r in range(rows):
        if r != 5:
            grid[r][5] = 1  # wall column at c=5, gap at row 5

    start, goal = (0, 0), (9, 9)
    d_cost, d_expanded = search(grid, start, goal, use_heuristic=False)
    a_cost, a_expanded = search(grid, start, goal, use_heuristic=True)
    print(f"Dijkstra (h=0): path cost={d_cost}, nodes expanded={d_expanded}")
    print(f"A* (Manhattan h): path cost={a_cost}, nodes expanded={a_expanded}")
    print(f"reduction in nodes expanded: {100*(1 - a_expanded/d_expanded):.1f}%")

Output:

Dijkstra (h=0): path cost=18, nodes expanded=90
A* (Manhattan h): path cost=18, nodes expanded=71
reduction in nodes expanded: 21.1%

Both algorithms agree on the optimal path cost (18 steps), confirming the heuristic did not sacrifice correctness, while A* expanded 71 nodes against Dijkstra's 90, a 21.1 percent reduction, because Manhattan distance actively discourages the search from wasting effort exploring away from the goal, while Dijkstra treats every direction as equally promising until it happens to reach the goal.

Trade-offs and pitfalls

• A only outperforms Dijkstra when the heuristic is genuinely informative.* A degenerate heuristic that is always 0 makes A* mathematically identical to Dijkstra (as shown by the use_heuristic=False branch above, which IS Dijkstra); the benefit is proportional to how tightly the heuristic tracks the true remaining cost, not to using A* as a label.
• An inadmissible heuristic (one that sometimes overestimates) can make A return a suboptimal path*, silently, with no error raised, which is the most dangerous failure mode: the algorithm still terminates and returns SOME path, just not necessarily the shortest one.
• Common mistake: assuming any "reasonable-looking" distance estimate is automatically admissible. A heuristic that accounts for typical road speed (for example, estimating remaining TIME using average highway speed) can easily become inadmissible if the actual route includes a faster-than-average segment, since the estimate could then exceed the true remaining time on that segment; time-based heuristics for road routing need care that pure geometric-distance heuristics do not.
• Bidirectional search and precomputed speedup techniques (Contraction Hierarchies, ALT) typically outperform plain A for production route-finding at scale*, particularly for repeated queries over a largely static road network; A* with a simple geometric heuristic is the right first tool to reach for, but production routing engines usually layer additional preprocessing on top once query volume justifies the added complexity.

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

Depth-first search (DFS) with three color states, white (undiscovered), gray (discovered, still being explored on the current path), black (fully finished), detects a directed cycle by recognizing a BACK EDGE: an edge from the node currently being explored into a node that is still gray, meaning still an ancestor on the active exploration path. A back edge means that ancestor depends, directly or transitively, on the very node now trying to reach it, a genuine circular dependency. This is reliable regardless of graph size or shape, including complex, many-branched pipeline dependency graphs, because the gray marker tracks exactly "currently on my path back to the root," which is precisely the condition a cycle requires.

Structured elaboration

The traversal. Start DFS from every white node (covering disconnected components). On visiting a node, mark it gray, then examine each outgoing edge: if the neighbor is white, recurse into it; if the neighbor is gray, a back edge has been found, a cycle; if the neighbor is black, that edge leads to an already-fully-explored subtree reachable some other way, not a cycle. After all of a node's neighbors are processed, mark it black.

Why gray specifically, and not just "visited." A plain boolean visited flag cannot distinguish "still in progress on my current path" from "finished via some completely unrelated path." Consider a diamond shape, $0 \to 1$, $0 \to 2$, $1 \to 3$, $2 \to 3$: node 3 is reached twice, once via 1 and once via 2, and neither visit is a cycle, since 3 is never an ANCESTOR of either 1 or 2. A boolean visited check alone cannot tell this apart from a genuine cycle case; the three-state color scheme can, because by the time the second path reaches node 3, node 3 has already gone gray to black (fully finished) rather than still being gray, so the algorithm correctly recognizes it as a shared descendant, not a back edge.

Why this is reliable for complex pipeline dependency graphs specifically. A pipeline dependency graph typically has many jobs sharing common upstream stages (many downstream jobs all reading from one shared ingestion stage, for example), which is exactly the diamond shape above at scale. The gray/black distinction is what makes the algorithm correctly ignore all that legitimate sharing while still catching a genuine cycle wherever one exists, independent of how tangled or branching the rest of the graph is, since the check only ever depends on the CURRENT recursion path's gray set, never on the graph's overall shape.

Returning the actual nodes in the detected cycle. Track a parent pointer for every node, set the moment it is first discovered from its immediate predecessor. The instant a back edge $u \to v$ is found ($v$ is gray), walk parent backward starting from $u$ until reaching $v$ itself; that walk, plus $v$ appended again at the end to close the loop, is exactly the cycle, reported as a concrete list of node names rather than a bare "yes, a cycle exists" boolean.

Worked example

def find_cycle(graph):
    color = {v: "white" for v in graph}
    parent = {v: None for v in graph}

    def dfs(u):
        color[u] = "gray"
        for v in graph[u]:
            if color[v] == "white":
                parent[v] = u
                found = dfs(v)
                if found is not None:
                    return found
            elif color[v] == "gray":
                cycle = [v]
                cur = u
                while cur != v:
                    cycle.append(cur)
                    cur = parent[cur]
                cycle.append(v)
                cycle.reverse()
                return cycle
        color[u] = "black"
        return None

    for node in graph:
        if color[node] == "white":
            result = dfs(node)
            if result is not None:
                return result
    return None

if __name__ == "__main__":
    dag = {0: [1, 2], 1: [3], 2: [3], 3: []}
    print("DAG cycle:", find_cycle(dag))

    pipeline = {"ingest": ["clean"], "clean": ["enrich"], "enrich": ["load"], "load": ["clean"]}
    cyc = find_cycle(pipeline)
    print("Pipeline cycle:", cyc)

    def is_real_cycle(graph, cycle):
        if not cycle or len(cycle) < 2:
            return False
        return all(cycle[i+1] in graph[cycle[i]] for i in range(len(cycle)-1))
    print("Reported pipeline cycle uses only real edges:", is_real_cycle(pipeline, cyc))

    diamond = {0: [1, 2], 1: [3], 2: [3], 3: []}
    print("Diamond (shared descendant, no cycle):", find_cycle(diamond))

Output (actually executed with python3):

DAG cycle: None
Pipeline cycle: ['clean', 'enrich', 'load', 'clean']
Reported pipeline cycle uses only real edges: True
Diamond (shared descendant, no cycle): None

The pipeline example (ingest feeds clean, clean feeds enrich, enrich feeds load, and load mistakenly feeds back into clean) correctly reports the exact cycle ['clean', 'enrich', 'load', 'clean'], verified by an independent edge-by-edge check that every consecutive pair in the reported cycle is a real edge in the original graph, not a fabricated list. The diamond case, structurally similar to the shared-ingestion-stage shape common in real pipelines, correctly reports no cycle at all.

Trade-offs and pitfalls

• Common mistake: returning just the back-edge's two endpoints ($u$ and $v$) as "the cycle," rather than the full path between them. This under-reports the problem: an operator debugging a circular dependency needs to see every job in the loop, not just the two that happened to trigger detection, especially in a pipeline graph where the cycle might span many stages.
• Common mistake: using a plain visited set instead of the three-state scheme and expecting the diamond shape (shared descendant, no actual cycle) to be handled correctly; as shown above, this specific shape is exactly what a boolean check gets wrong, making it a strong test case to include in any cycle-detector's own test suite.
• Multiple independent cycles. This algorithm returns the FIRST cycle it happens to find during its traversal order, not necessarily the "worst" one or all of them; a pipeline validation tool that wants to report every cycle in one pass needs to continue searching after finding one (removing or logging it, then resuming), rather than stopping at the first.
• Self-loops are the degenerate one-node case of exactly the same mechanism: a node pointing to itself is immediately gray when its own edge is examined, correctly detected as a cycle of length one without any special-casing needed.

Direct answer

In an undirected graph, DFS with a tracked parent argument detects a cycle by treating an edge to an already-visited node as a cycle, EXCEPT when that already-visited node is the immediate parent, since every undirected edge is stored twice (once in each endpoint's adjacency list), so walking straight back along the edge you just arrived on would otherwise look identical to a genuine cycle. Passing the parent explicitly and skipping exactly that one edge is what makes the check correct.

Structured elaboration

Why the parent check exists at all. An undirected edge $(u, v)$ is represented as $v \in \text{graph}[u]$ AND $u \in \text{graph}[v]$, both directions stored. A DFS that goes from $u$ to $v$ will, when examining $v$'s neighbors, immediately see $u$ again, the edge it just came from. Without a parent check, this looks exactly like discovering an already-visited node, indistinguishable from a real cycle, even on a simple two-node graph with a single edge and no cycle at all. Recording the parent and explicitly skipping the edge back to it removes this false signal while leaving every genuine cycle (an edge into a visited node that is NOT the immediate parent) correctly detected.

Worked example

from typing import Dict, List

def has_cycle(graph: Dict[int, List[int]]) -> bool:
    visited = set()

    def dfs(u: int, parent: int) -> bool:
        visited.add(u)
        for v in graph.get(u, []):
            if v == parent:
                continue  # the edge back to where we came from, not a cycle
            if v in visited:
                return True  # a back-edge to an already-visited, non-parent node: a cycle
            if dfs(v, u):
                return True
        return False

    for node in graph:
        if node not in visited:
            if dfs(node, -1):
                return True
    return False

if __name__ == "__main__":
    tree = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}  # a genuine tree, no cycle
    print("tree (no cycle):", has_cycle(tree))

    triangle = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
    print("triangle (cycle):", has_cycle(triangle))

    disconnected_with_cycle = {0: [1], 1: [0], 2: [3, 4], 3: [2, 4], 4: [2, 3]}
    print("disconnected, cycle only in 2nd component:", has_cycle(disconnected_with_cycle))

    isolated = {0: [], 1: [], 2: []}
    print("all isolated nodes:", has_cycle(isolated))

    self_loop = {0: [0]}
    print("self-loop:", has_cycle(self_loop))

    def edges_from_adj(adj):
        seen = set()
        edges = []
        for u in adj:
            for v in adj[u]:
                if (v, u) not in seen:
                    edges.append((u, v))
                    seen.add((u, v))
        return edges

    def brute_force_has_cycle(adj):
        # Independent ground truth via plain union-find (correct here since
        # this check is over UNDIRECTED edges, where union-find is valid).
        nodes = list(adj.keys())
        idx = {n: i for i, n in enumerate(nodes)}
        parent = list(range(len(nodes)))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        for u, v in edges_from_adj(adj):
            ru, rv = find(idx[u]), find(idx[v])
            if ru == rv:
                return True
            parent[ru] = rv
        return False

    for name, g in [("tree", tree), ("triangle", triangle), ("disconnected", disconnected_with_cycle), ("isolated", isolated)]:
        print(f"cross-check {name}:", has_cycle(g) == brute_force_has_cycle(g))

Output (actually executed with python3):

tree (no cycle): False
triangle (cycle): True
disconnected, cycle only in 2nd component: True
all isolated nodes: False
self-loop: True
cross-check tree: True
cross-check triangle: True
cross-check disconnected: True
cross-check isolated: True

Every DFS-with-parent result is cross-checked against a completely independently implemented union-find (correct for THIS undirected-only use case, unlike the directed case where union-find is unsound). The self_loop case (0: [0]) is correctly reported True: when DFS at node 0 examines its own self-loop edge, the neighbor is 0 itself, which is already in visited (added at the start of the call) and is NOT equal to parent (which is $-1$ for the root call), so it correctly falls through to the cycle-detected branch.

Complexity

Time $O(|V|+|E|)$: each vertex is visited at most once (guarded by visited), and each edge is examined at most twice total (once from each endpoint), a constant factor that does not change the asymptotic bound. Space $O(|V|)$ for visited and the recursion stack.

Edge cases

• Disconnected graph: the outer loop restarts DFS from every unvisited node, so a cycle in any component is found regardless of which component happens to be explored first.
• Isolated nodes (no edges at all): trivially no cycle, handled without any special-casing since the inner loop over graph.get(u, []) simply does nothing.
• Self-loop (v == u): correctly detected as a cycle, as traced above; note that v == u is NOT the same check as v == parent, so a self-loop is never accidentally treated as "the edge back to my parent" even on the very first call where parent starts at a sentinel value.
• Parallel edges between the same pair (the same undirected edge listed twice): would be misreported as a cycle by this implementation, since the second occurrence of the neighbor is not equal to parent on the SECOND time it is examined even though it is the same physical edge; a graph representation that can contain true parallel edges needs an explicit edge-id (not just a node-id) comparison to skip correctly, which this simple adjacency-list version does not attempt to solve.

Trade-offs and pitfalls

• Common mistake: omitting the parent parameter entirely and using a plain "is this neighbor visited" check, which reports every single edge in an undirected graph as a cycle, since the edge back to the immediate parent always looks like a revisit.
• Common mistake: comparing against a set or list of ALL ancestors instead of just the immediate parent. For an undirected graph this is unnecessary extra work, since only the single edge just traversed needs to be excluded, not the whole ancestor chain, that distinction (immediate parent only, versus the full ancestor set) is precisely what separates undirected cycle detection from the analogous directed case, where the full "on the current path" (gray/inStack) set genuinely is needed.
• Why this technique is undirected-specific. The parent-skip trick exists purely because undirected edges are stored bidirectionally; a directed graph never has this "walking back along the same edge looks like a revisit" problem in the first place, since a directed edge $u \to v$ has no automatic reverse entry, which is why directed cycle detection needs the gray/inStack (full active-path) mechanism instead of a simple single-parent exclusion.