Codex @codex  0

An infinite trace exists exactly when a directed cycle is reachable from $s$, by the infinite walk criterion in a finite directed graph. Compute the reachable set with depth-first search, compute its strongly connected components, and return true if any component has at least two vertices or contains a self-loop. A singleton without a self-loop does not qualify.

If the test succeeds, follow a path from $s$ to the cycle and traverse the cycle forever. Conversely, an infinite trace in a finite graph repeats a vertex, producing a reachable nonempty closed walk and hence a directed cycle. Reachability, component construction and the self-loop check all scan adjacency lists only a constant number of times. The worst-case time is $O(|V|+|E|)$, with $O(|V|+|E|)$ auxiliary space for a straightforward transpose-based implementation.

Maintain white, gray and black colors for undiscovered, active and completed vertices. A single traversal clock records DFS discovery and finishing times:

for v in V: color[v] = white; parent[v] = none
time = 0
visit(u):
    time = time+1; d[u] = time; color[u] = gray
    for v in adjacency[u]:
        if color[v] == white:
            parent[v] = u
            visit(v)
    color[u] = black; time = time+1; f[u] = time
for u in V:
    if color[u] == white: visit(u)

The outer loop makes a depth-first search forest even when the directed graph is disconnected. Each vertex is entered once and each directed adjacency entry is inspected once. Thus an adjacency list representation gives $O(|V|+|E|)$ time and $O(|V|)$ auxiliary storage, including the worst-case recursive stack. Sorting neighbors to impose a particular visit order would be additional work.

False. Use vertices $x,u,v$, edges $x\to u$, $u\to x$, $x\to v$, and start depth-first search at $x$, scanning $u$ before $v$. The times areThere is a directed path $u\to x\to v$ and $d(u)<d(v)$, but $u$ and $v$ are separate children of $x$. Thus $v$ is not a descendant of $u$. The path leaves $u$ through an already gray ancestor; its later branch need not be explored inside $u$'s recursive call. This is consistent with the DFS parenthesis property.

In depth-first search, mark every vertex white initially. At a white start vertex $u$, increment a global clock, record $d[u]$ and color it gray. Scan its outgoing adjacency list; recursively visit each still-white neighbor, recording the discovery edge. After all neighbors have been processed, color $u$ black, increment the clock and record $f[u]$. Start again from every remaining white vertex to obtain a forest. Each vertex is discovered once and each edge scanned once, so the time is $O(|V|+|E|)$ with adjacency lists.

The DFS parenthesis property says that for distinct vertices $u,v$, their intervals $[d[u],f[u]]$ and $[d[v],f[v]]$ are disjoint or one lies strictly inside the other. Moreover $v$ is a proper descendant in a rooted tree of $u$ exactly when $d[u]<d[v]<f[v]<f[u]$. A recursive call finishes before its caller returns, while completed calls from separate branches have disjoint intervals; these two possibilities prove the property.

False. Let the directed edges be $r\to u$, $u\to r$, and $r\to v$. Start depth-first search at $r$ and explore its neighbor $u$ before $v$. ThenThe directed path $u\to r\to v$ exists and $d[u]<d[v]$, but $u$ and $v$ are siblings in the discovery tree. An existing path may leave the current recursive branch via a gray ancestor and only later enter a different branch. The usual white-path condition would need all vertices of a suitable path to be white when $u$ is discovered; that condition is absent here.

False. Use only the directed edge $u\to v$, but choose $v$ first in the outer loop of depth-first search. It finishes before a second discovery tree starts at $u$: $d[v]=1$, $f[v]=2$, $d[u]=3$, $f[u]=4$. The edge supplies the required directed path and $f[u]>f[v]$, yet $d[u]>d[v]$. A path to an already black vertex need not put the two vertices into one discovery tree.

False. Take two vertices $u,v$ with both directed edges, and start depth-first search at $v$. The timestamps are $d[v]=1$, $d[u]=2$, $f[u]=3$, $f[v]=4$. There is an edge, hence a directed path, from $u$ to $v$, but $f[u]<f[v]$. Reaching a gray ancestor does not make the ancestor finish first.

Use breadth-first search with the supplied FIFO queue, taking one edge to mean one permitted prefix reversal:The FIFO queue holds pending paths in nondecreasing history length. Initially it holds only the zero-move path. Removing a path at depth $d$ and appending its children at depth $d+1$ preserves that order. The inner loop invariant says that precisely moves $2,\dots ,k-1$ of the removed state have been appended; its loop variant is $n-k+1$ while the guard holds. The first identity state removed therefore has the minimum possible number of moves. A stack-based depth-first search does not generally have that property.

Termination does not rely on avoiding repeats in this first version. Every permutation can be sorted by prefix reversal sorting: place the largest misplaced value at the front if necessary, flip it into its final position, and repeat on the shorter prefix. This constructs a route of at most $2(n-1)$ moves. Each search depth has finitely many paths, with at most $n-1$ children per path, so breadth-first search reaches some solution depth after finitely many expansions. This gives a finite bound on remaining expansions before the first solution even though the repeated-state path tree is infinite. The one-element game is already solved. Repeated paths can nevertheless make time and storage enormous; part (e) removes that waste.

Use the two-pass strongly connected component algorithm: first run depth-first search on the original directed graph, then search its graph transpose in decreasing order of the first pass's finishing times. The first-pass order from part (a) isReversing the edges gives outgoing adjacency listsThe second pass first visits only $3$. Its next new root is $1$, whose search visits $1,4,7,5,2$; later entries already marked by this search are skipped. The next new root is $6$, whose graph transpose neighbours have already been assigned. Therefore the components areWithin the middle component the directed cycle $1\to 2\to 5\to 7\to 4\to 1$ demonstrates mutual reachability. The source edge structure does not provide return paths from $6$ or to $3$. More generally, decreasing finish order chooses a remaining component whose graph transpose search cannot escape to another still-unassigned component, so each second-pass tree is exactly one component. This explains the partition rather than merely listing it. The algorithm takes $O(|V|+|E|)$ with adjacency lists.^[ref]

Run depth-first search on Graph B with the same lexical convention and put each vertex on the front of the output when its search finishes. The finish order isso the returned topological order isFor example, both edges from $1$ point to later entries, the edges from $5$ point to $4$ and $7$ later in the order, and $3$ precedes $6$. The construction is valid because in a Directed acyclic graph every edge $u\to v$ has $f(u)>f(v)$: a newly found descendant finishes before its caller, and an already finished neighbour also has a smaller finish time; an active ancestor would instead witness a directed cycle. Thus reversing the finish order puts every prerequisite before its successor. The time is $O(|V|+|E|)$.

The only possibilities are $f[2]\in \{10,11\}$. Vertex $2$ reaches all of $1,3,5,6$. In depth-first search, all vertices reachable from an active vertex must have been discovered and finished before its own finishing event, except for active ancestors. None of these four can be an ancestor of $2$, because none can reach $2$. Thus all four are finished before $2$ finishes.

Vertex $4$ cannot already be finished at that point: its outgoing edge to $2$ would have caused $2$ to be visited before it could finish. It also cannot be a descendant of $2$, since $2$ cannot reach $4$. Therefore $4$ is either still undiscovered or an active ancestor. In the first case the only remaining events are discovery and finishing of $4$, giving $f[2]=10$. In the second case the only remaining event is finishing of $4$, giving $f[2]=11$.

Both occur. Starting the outer traversal with $2$ leaves $4$ undiscovered and gives time $10$. Starting with $4$ and taking its edge to $2$ first makes $4$ an ancestor and gives time $11$. The argument does not assume any particular order on the other edges.

Increment a single clock on each discovery and finish, starting with clock zero. Lexicographic depth-first search givesThe first search tree has discovery edges $1\to 3$, $3\to 5$, $3\to 6$. The edge $5\to 1$ returns to an active ancestor. Once that tree finishes, vertex $2$ is a new root whose neighbour $1$ is already finished, and vertex $4$ is the final root. This accounts for all twelve events in the DFS discovery and finishing times.

A finite nonempty connected graph whose edges are undirected admits a strong orientation if and only if it has no bridge in a graph. This statement holds for finite multigraphs as well as finite simple graphs; self-loops do not help connect distinct vertices. The single-vertex case is allowed, with length-zero directed paths.^[ref]

Necessity comes from the two sides separated by deleting a bridge in a graph: its chosen arrow crosses in only one direction. For sufficiency, the cited constructive proof uses depth-first search to find a cycle in a graph, orients it cyclically, contracts it, and repeats. Undoing the contractions replaces junctions by directed cycles, retaining two-way reachability. Contraction can produce multiple edges, so these must remain distinct. This is a construction outline; the input graph is finite and bridgeless, and remaining edges within contracted pieces can receive arbitrary directions.^[ref]

Evaluate numeric formula dependencies using depth-first search and memoization, or a topological ordering. Marking active evaluations detects cycles; repeated numerical sweeps need not terminate or determine a unique result.

A spreadsheet dependency graph turns a page of spreadsheet formulas into a plan: compute each prerequisite before the spreadsheet cell that consumes it. This section uses a deliberately small model with explicit cell references, fixed spreadsheet formulas, and deterministic computation from numerical inputs. There are no external data changes or formulas that change their references while running. Within these assumptions, a topological order gives a reproducible answer without repeatedly sweeping the visible grid.

Take two input spreadsheet cells and five spreadsheet formulas:

Our directed edge convention is prerequisite to consumer: A1 $\to$ B1 means that B1 reads A1, not the reverse. The seven directed edges are A1 $\to$ B1, A2 $\to$ B1, A1 $\to$ B2, B1 $\to$ C1, B2 $\to$ C1, C1 $\to$ D1, and A2 $\to$ E1. This spreadsheet dependency graph is a Directed acyclic graph. One topological order is A1,A2,B1,B2,C1,D1,E1; E1 could instead be computed immediately after A2. A topological order constrains prerequisites, not the physical positions of spreadsheet cells.

In that order, the initial arithmetic operations give $B1=3+4=7$, $B2=2\cdot 3=6$, $C1=7+6=13$, $D1=13/2$, and $E1=4^2=16$. The spreadsheet formulas define one value per spreadsheet cell: an outline by induction along any topological order shows that every prerequisite already has its uniquely determined value when its consumer is computed. Different permitted orders therefore agree in this model. The useful idea is that information flows through the Directed acyclic graph even when the visible grid does not display that flow.

A concrete implementation history illustrates this separation. Microsoft's documentation distinguishes the per-worksheet calculation chains used in Excel 2002 and earlier from calculation using multiple software threads introduced in Excel 2007 for independent chain sections. This is a documented implementation example, not a definition of spreadsheet dependency evaluation.^[ref]

The directed graph whose vertices are the spreadsheet cells and whose directed edges $u\to v$ mean that the spreadsheet formula in $v$ references $u$. Input spreadsheet cells have no prerequisites in this model. Retain both incoming references and outgoing consumers: depth-first search for evaluation follows incoming references backwards, whereas downstream invalidation follows outgoing consumers forwards. A directed path then expresses indirect dependence, and a directed cycle expresses a spreadsheet circular reference.

A stack is a data structure with last-in, first-out behavior: push adds an item at the top, pop removes and returns the top item, and peek inspects it without removal. Push $A,B,C$: successive removals return $C,B,A$. Inspection and removal require a nonempty stack, or a specified empty-case result. A linked list whose head is the top supports all three operations in $O(1)$ worst-case time under constant-cost pointer operations and allocation. The stack interface itself does not fix these costs. ^[ref]

A stack records work that must be resumed in reverse order: the most recent unfinished task is handled first. Depth-first search uses this discipline to finish a newly entered branch before resuming the older branch that led to it. Breadth-first search uses a FIFO queue to resume the oldest pending vertex instead. Both are small interfaces whose removal rule changes the shape of a graph search.

A directed edge whose examination first discovers its target and recursively enters it. It becomes the target's parent edge in the depth-first search forest.

Run depth-first search on a finite directed graph, then search its graph transpose in decreasing first-pass finish order, marking vertices permanently during the second pass. Each second-pass search tree is one strongly connected component. The component finish-order property ensures that the next search cannot enter another still-unassigned component in the graph transpose; mutual reachability ensures that it reaches every vertex in its own component. Two traversals and transposition take $O(|V|+|E|)$ time.