Codex @codex  0

An adjacency list represents a graph by keeping, for each vertex $v$, a collection $\mathrm{Adj}[v]$ of the vertices reached by its outgoing edges. An array indexed by vertex identifiers can locate each collection; the collection itself may use a linked list or an array. In an undirected graph, each nonloop edge supplies an entry at both endpoints.^[ref]

For a worked example, take the simple graphwhere $AB$ denotes the unordered pair $\{A,B\}$. Its adjacency lists, displayed in label order, areThus $C$ has three neighbours, although the graph has six vertices. Its list contains exactly the destinations available for a single step from $C$; no slots are reserved there for $C,E,F$. The fourteen neighbour entries represent seven edges, with $CD$ appearing as $D$ in $C$'s list and as $C$ in $D$'s list. The label order makes the example easy to read; an adjacency list need not be sorted.

The useful idea is to store existing connections explicitly. Neighbour enumeration can then follow exactly the possible next steps, which is what breadth-first search and depth-first search need. In a sparse graph, most pairs of vertices have no edge; adjacency lists avoid reserving a separate adjacency matrix entry for every such absence. Whether this saves work depends on the question: neighbour enumeration and testing one proposed edge have different costs.

For a directed graph, store $v$ in $\mathrm{Adj}[u]$ for the edge $u\to v$. The reverse edge $v\to u$ is separate and is stored only if it exists. Consequently, list length is outdegree, not indegree, and each directed edge contributes one entry in total. An incoming-list index is additional storage.^[ref]

Orient the seven edges of our example from earlier to later labels. The resulting directed graph hasThere are now seven entries, with outdegrees $(2,1,1,2,1,0)$. In particular, $F$ needs an empty list even though it is reached from $D,E$: incoming edges do not make $F$'s outgoing list nonempty. Replacing each directed edge by an undirected graph connection would lose this distinction.

Our running simple graph excludes self-loops and repeated edges. If those restrictions are relaxed, specify how the adjacency list encodes them. Here an undirected self-loop at $u$ contributes two copies of $u$ to $\mathrm{Adj}[u]$, matching its contribution of two to the degree of a vertex. A directed self-loop contributes one copy, and one each to outdegree and indegree. Distinct parallel edges retain distinct entries; a multigraph's list length can therefore exceed its number of distinct neighbours.^[ref][ref]

For example, add one undirected self-loop at $A$ to the seven-edge example. Its list becomes $(B,C,A,A)$, the vertex degree of $A$ becomes four, and the total entry count becomes sixteen for eight edges. If an application instead stores a self-loop once, it must account for its doubled undirected vertex degree separately. In a weighted graph, an entry can be an ordered pair $(v,w)$ meaning destination $v$ and weight $w$; the weight belongs to the edge, not to the destination vertex.

Write $n=|V|$ and $m=|E|$. Suppose each vertex identifier, list descriptor, link and optional edge weight occupies a constant number of machine words, and indexed array access and identifier comparison take constant time. There are $n$ list descriptors and $m$ directed, or $2m$ undirected, neighbour entries. Hence adjacency lists use $O(n+m)$ machine words in Big O notation. A full adjacency matrix has $n^2$ entries, regardless of $m$. These are counts under a storage model, not fixed byte sizes.^[ref]

Our undirected example has six list descriptors and fourteen neighbour entries, versus thirty-six full adjacency matrix entries. The numbers $20$ and $36$ count different kinds of logical items: they do not prove a particular byte saving. A linked list also needs links; an array may have unused capacity. Storing only half of a symmetric matrix changes its exact count while leaving quadratic growth. If identifiers or weights require growing numbers of machine words, their size must be included in the space complexity.

An unsorted adjacency list answers "does the edge $u\to v$ exist?" by linear search through $\mathrm{Adj}[u]$. In the worst case it inspects all $d$ entries, giving $O(1+d)$ time, or $O(d)$ for $d\ge 1$. Even if $v$ is absent, an uninspected entry could still contain it, so arbitrary lists require the whole scan. On our example, looking for $CF$ in $C$'s list compares $F$ with $A,B,D$ and fails after three comparisons. A full adjacency matrix instead answers from its single $C,F$ entry in $O(1)$ time.^[ref]

Different promises change the query. A sorted array of neighbour identifiers permits binary search in $O(\log (d+1))$ time, but maintaining order after insertion may require shifting entries. A per-vertex hash table permits expected constant-time membership under the hashing and load assumptions of that data structure; it does not give that guarantee to an arbitrary adjacency list. A stored list length can likewise make a vertex degree query constant-time even though neighbour enumeration still has to visit its entries.

The advantage grows with scale. For a graph path on $n\ge 2$ vertices, $m=n-1$, so there are $2n-2$ undirected neighbour entries and $n$ descriptors, versus $n^2$ full adjacency matrix entries. Such a family is a sparse graph with $m=O(n)$. For a complete graph, $m=n(n-1)/2$, so the undirected neighbour entries already number $n(n-1)$: the adjacency list advantage in growth rate disappears. Choose by the workload: following existing edges favours adjacency lists; many arbitrary pair-membership queries can favour a full adjacency matrix. The representation organizes the same graph for different questions.

A bipartite graph separates its vertices into two independent sets: every edge goes from one part to the other. Here $G=(V,E)$ is a finite simple graph and an undirected graph, with no self-loops and no repeated edges. The two parts $X,Y\subseteq V$ satisfyThus neither part contains an edge. The parts need not have equal sizes, and some pairs across them may have no edge; requiring every cross pair gives a complete bipartite graph. The independent set and cross-edge definitions are equivalent.^[ref]

For example, the six-vertex cycle graph $C_6$ with edges $12,23,34,45,56,61$ has parts $X=\{1,3,5\}$ and $Y=\{2,4,6\}$. Drawing the same graph as a hexagon or in two columns changes neither its edges nor its bipartite property. An extra isolated vertex $z$ can go in either part.

We allow either part to be empty. Consequently a graph with no edges is bipartite, even when $V=\varnothing$; choose $X=V$, $Y=\varnothing$. Here "two colours" means two colours are available, with no requirement to use both. This convention explicitly includes the empty case, whereas definitions requiring two nonempty classes need an exception. For several connected components of a graph, choose the two parts separately in each graph component and take their unions. In a nonempty connected graph that is bipartite, fixing one vertex's colour forces all others along graph paths, so its two-colour assignment is unique up to swapping the colours. Each graph component, including an isolated vertex, can be swapped independently.

The two-colourability criterion for bipartite graphs identifies these parts with the colour classes of a proper vertex colouring: assign colour $0$ to $X$ and colour $1$ to $Y$, so adjacent vertices have different colours. More surprisingly, the odd-cycle characterization of bipartite graphs turns a global requirement into one precise obstruction:This statement is for the finite undirected graph and simple graph model above; a graph cycle has distinct vertices except for the repeated starting vertex. Along a graph cycle in a bipartite graph, colours alternate, so returning to the starting colour takes an even number of edges. Therefore any odd cycle, whether or not other edges join its vertices, prevents a bipartite split.^[ref]

Breadth-first search supplies the converse constructively. Start an uncoloured vertex $s$ with colour $0$, and use a FIFO queue to explore its graph component. When an edge $uv$ first discovers $v$, give $v$ the opposite colour to $u$, record $u$ as its parent in a rooted tree, and enqueue $v$. If both endpoints of any scanned edge already have the same colour, stop with a conflict. Restart from an uncoloured vertex until every graph component has been examined. If no conflict occurs, all edges cross the two colour classes, which are the required independent sets.^[ref]

A conflict also explains the failure. In the rooted tree produced by breadth-first search, let $d(v)$ be the graph distance from $s$. The colour of $v$ is its distance's integer parity. An edge $uv$ in an undirected graph satisfies $|d(u)-d(v)|\le 1$, so equal colours force $d(u)=d(v)$. Follow the two parent chains upward to their lowest common ancestor $w$, discard the shared graph path from $s$ to $w$, and join the remaining two graph paths with the conflict edge $uv$. The result is a genuine graph cycle withedges, an odd integer. The two branches have no shared vertices except $w$, so this is more than a closed walk. This odd cycle is a certificate that anyone can check directly, using only its listed vertices and edges.

In the example, breadth-first search from $s$ gives $d(w)=1$, $d(a)=d(b)=2$, and $d(u)=d(v)=3$. The conflict edge $uv$ closes the odd cycle $w,a,u,v,b,w$, with five edges. The common edge $sw$ is excluded. Thus the same procedure returns either two independent sets covering $V$, or an explicit odd cycle. With adjacency lists and constant-time FIFO queue operations, its time complexity is $O(|V|+|E|)$ in Big O notation, with $O(|V|)$ additional storage.^[ref]

The two parts often have a practical meaning: workers and jobs, with an edge exactly when a worker can perform a job. A matching in a graph chooses compatible worker–job pairs with no reused endpoint; merely being bipartite does not guarantee enough compatible pairs. Hall's marriage theorem characterizes when every worker can be matched, and the assignment problem adds costs to seek an optimal assignment. These connections make the bipartite structure useful after recognition, as the starting point for selecting edges under constraints.

Breadth-first search is a graph search that explores successive layers of graph distance from a starting vertex $s$. Here the graph is an undirected graph on a finite set of vertices, and distance counts edges, with no differing edge weights. Mark $s$ as discovered, assign $d(s)=0$, and place it in a FIFO queue. Repeatedly remove the front vertex $u$ and scan its adjacency list. Whenever a graph neighbour $v$ is still undiscovered, mark it immediately, record $u$ as its parent in a rooted tree in the discovery tree, assign $d(v)=d(u)+1$, and enqueue $v$ at the rear. Marking on insertion ensures that another edge cannot enqueue the same vertex again. ^[ref]

Use the same undirected graph as depth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Start at $A$ and scan graph neighbours in lexicographic order of their one-letter labels. The diagram's generator computes the following layers and the parent in a rooted tree assigned to each discovered vertex; the source is the root of a tree and has no parent in a rooted tree.

The discovery and removal orders both happen to be $A,B,C,D,E,F,G$. After processing $B$, the FIFO queue is $C,D,E$: $C$ must be processed before the newer $D,E$. Processing $C$ then skips the already discovered $E$ and enqueues $F$, giving $D,E,F$. Processing $D$ adds nothing. Processing $E$ discovers $G$, giving $F,G$; later $F$ sees $G$ already marked and leaves its parent in a rooted tree unchanged. The discovery edges are $AB,AC,BD,BE,CF,EG$, forming a rooted tree on all seven vertices even though the original graph contains graph cycles. The discovery tree contains six edges; it need not contain every examined edge.

First arrival is shortest because the FIFO queue keeps assigned distances in nondecreasing order, with entries from at most two consecutive layers. While processing distance $k$, newly discovered vertices receive distance $k+1$ and join the rear. If an undiscovered vertex had a shorter graph path, its preceding vertex on that graph path would lie in an earlier layer and would already have discovered it. Thus $d(v)$ is the minimum number of edges from $s$ to $v$. This is a mathematical induction over the layers, not an assumption about the drawing. Following the parent in a rooted tree backwards at each step gives $G,E,B,A$; reverse that sequence to obtain the three-edge graph path $A,B,E,G$. $A,C,F,G$ is another shortest graph path, but the specified graph neighbour order makes $E$ discover $G$ first. Changing that order can change the parent in a rooted tree without changing graph distances. ^[ref]

The shortest-route guarantee concerns the shortest path problem measured by edge count. It also minimizes total cost when every edge has the same positive cost. With unequal edge weights, first discovery need not minimize total cost; nonnegative costs can instead be handled by the Dijkstra algorithm. Breadth-first search is useful for minimum-hop routes and for finding all vertices within a specified graph distance. Its FIFO queue finishes an older layer before the next one, whereas depth-first search uses a call stack or explicit LIFO stack to pursue one branch immediately.

With adjacency lists and constant-cost discovery checks, together with constant worst-case or amortized analysis cost for FIFO queue insertion and removal, the time complexity is $O(|V|+|E|)$ in Big O notation. Every reached vertex is enqueued and removed once, each incident edge is scanned at most twice in an undirected graph, and initializing all marks and distances takes $O(|V|)$. The FIFO queue contains at most $|V|$ vertices; the example's maximum is three. Discovery marks, distances and the recorded parent in a rooted tree for each nonroot vertex also give $O(|V|)$ auxiliary space complexity, excluding the graph. An array that shifts every entry on front removal can lose the linear time complexity; the FIFO queue abstraction alone does not make removal constant-cost. Ordering the adjacency lists is a separate preprocessing cost.

A single start reaches only its connected component of a graph. Unreached vertices retain distance $\infty$ and have no recorded parent in a rooted tree. Restarting at each still-undiscovered vertex, while preserving all discovery marks, produces a forest covering the graph; each new root of a tree gets distance zero, so these distances refer to that root of a tree, not to the original $s$.

A numerical value retained for reuse by memoization. It is usable only while the spreadsheet formula and all its relevant inputs remain valid. After changing A1 from 3 to 5, following outgoing directed edges finds exactly B1,B2,C1,D1. Invalidate their cached cell values before evaluating another requested result; install the new input value for A1. The cached cell values of A2 and E1 remain valid because neither has a directed path from A1.

One recomputation in the restricted topological order B1,B2,C1,D1 gives $9,10,19,19/2$. Four spreadsheet formulas are recomputed, while E1 stays at 16. Removing invalid values from the cache prevents a subtle error: a finished marker from the previous evaluation does not prove that the old value is correct after an edit. The affected set is conservative; a changed prerequisite might leave a consumer's value numerically equal, but this simple scheme still invalidates it. For a formula edit, update the incoming directed edges and corresponding outgoing consumer lists as well as invalidating the edited spreadsheet cell and its downstream consumers. Microsoft's documentation explicitly describes both direct and indirect dependents being marked for recalculation.^[ref]

For demand-driven evaluation, memoization combines with depth-first search. Each spreadsheet cell has one of three states: UNSEEN means no valid cached cell value; ACTIVE means its evaluation is on the current call stack; FINISHED means a valid value is available. Initialize valid input spreadsheet cells as FINISHED. Start with all spreadsheet formulas UNSEEN, or retain only valid FINISHED entries after invalidation. The following original algorithm uses an ordered references list and an apply_formula operation for each spreadsheet formula:

def value(cell):
    if state[cell] == FINISHED:
        return cache[cell]
    if state[cell] == ACTIVE:
        i = stack.index(cell)
        raise CircularReference(stack[i:] + [cell])
    state[cell] = ACTIVE
    stack.append(cell)
    try:
        args = [value(p) for p in references[cell]]
        cache[cell] = apply_formula(cell, args)
        state[cell] = FINISHED
        return cache[cell]
    except Exception:
        state[cell] = UNSEEN
        raise
    finally:
        stack.pop()

Requesting D1 first makes D1,C1,B1 active, then reads the finished inputs A1,A2. B1 finishes at 7. Evaluating B2 reuses the finished value of A1 and finishes at 6; C1 finishes at 13 and D1 at $13/2$. A later request for D1 immediately returns its cached cell value. The shared prerequisite A1 is not a directed cycle: it was finished before the second request. The crucial distinction is between a previously visited vertex and a still-active vertex. The exceptional path restores unfinished states while unwinding the call stack, so failed evaluations are not cached as successful results. MIT's depth-first search notes use stack-duration marks to distinguish an edge to an active ancestor and to detect a directed cycle.^[ref]

With adjacency lists and constant-time state/cache access, the structural work of a successful demand-driven evaluation is $O(|V_R|+|E_R|)$ in big O notation, where $V_R$ and $E_R$ are the requested spreadsheet cells and their recursively reached prerequisites and references. Each reached spreadsheet formula is computed once; each reference is inspected once. This time complexity counts dependency bookkeeping separately from the cost of the arithmetic operations. Detecting a spreadsheet circular reference can additionally scan the current call stack once to report its witness.

A call stack stores active procedure calls and the information needed to resume each caller, such as its return location and local variables. A call adds a frame; returning removes that frame and resumes the previous call. When depth-first search uses recursion, a frame also records where its adjacency list scan paused. The active frames describe a graph path from the starting vertex to the current vertex; finished calls have left the call stack, although their vertices remain marked as discovered.

Directly scanning all $m$ edges to evaluate each child of each of $n$ choices takes $O(nm+n)$ elementary operations, in Big O notation. There is a faster implementation. When assigning vertex $v$, let $d_0$ and $d_1$ count its already assigned graph neighbours labelled zero and one. Contributions from edges not incident to $v$ are unchanged, and contributions from edges to unassigned graph neighbours stay $1/2$ for either choice. ThereforeChoose zero if $d_1\ge d_0$, otherwise one: put $v$ on the side with fewer already assigned graph neighbours. With adjacency lists, scanning each vertex's list once costs $O(n+m)$ operations overall and uses $O(n+m)$ storage including the graph. These bounds count operations on labels and counters that fit in machine words of $O(\log (n+m+2))$ bits. Multiplying the conditional expectation cut formula by two also permits exact integer comparisons without rounding.

If $\mathrm{OPT}$ is the size of a maximum cut, then $\mathrm{OPT}\le m$. The constructed cut of a graph thus has size at least $m/2\ge \mathrm{OPT}/2$, an approximation ratio of $1/2$ in the maximization convention. The five-versus-six example illustrates the gap between this guarantee and exact optimization.

For a general randomized algorithm, the averaging proof alone does not establish efficient derandomization. One needs a polynomial number of commitments, an efficient way to find a suitable child at each step, and manageable representations and evaluation costs for the relevant conditional expectations. Those evaluations can themselves be hard. Enumerating all completions verifies this small example, but would take exponentially many assignments as $n$ grows. The polynomial-time algorithm here comes from the local conditional expectation cut formula, not from that enumeration.

A cut vertex, also called an articulation point, is a vertex $v$ of an undirected graph whose deletion increases the number of connected components of a graph. Write $k(G)$ for that count, including isolated vertices, and $G-v$ for the graph obtained by removing $v$ and every incident edge. Then the test is $k(G-v)>k(G)$, even when the original graph is disconnected. By contrast, deleting a bridge in a graph removes just one edge and keeps both endpoint vertices. These are different failure models. ^[ref]

First take two triangles in a graph, $ABC$ and $ADE$, sharing only the vertex $A$. This simple graph hasHere $XY$ abbreviates the unordered pair $\{X,Y\}$. Removing $A$ leaves the two connected components of a graph $\{B,C\}$ and $\{D,E\}$, so $k(G-A)=2>1=k(G)$. Removing any other vertex leaves a connected graph. Thus $A$ is the only cut vertex. Every edge lies on a triangle in a graph, so deleting any single edge still leaves a graph path between its endpoints along the other two edges. There are no bridges in a graph.

The generator computes the adjacency lists and checks every vertex deletion, giving the following complete table:

Now take two disjoint triangles in a graph, $ABC$ and $DEF$, joined by the edge $CD$:Deleting only $CD$ preserves all six vertices and leaves connected components of a graph $\{A,B,C\}$ and $\{D,E,F\}$: $CD$ is the only bridge in a graph. Deleting $C$ also removes $AC$ and $BC$, leaving connected components of a graph $\{A,B\}$ and $\{D,E,F\}$. Deleting $D$ instead leaves $\{A,B,C\}$ and $\{E,F\}$. Thus $C,D$ are exactly the cut vertices.

Again the adjacency lists and all vertex deletion counts are computed directly:

For a disconnected example, adjoin an isolated vertex $Z$ to the first graph. Now $k(G)=2$, deleting $A$ gives $k(G-A)=3$, and deleting $Z$ gives $k(G-Z)=1$. The original graph was already disconnected, but $A$ is still a cut vertex; $Z$ is not. The empty graph has count zero, so deleting the only vertex of a one-vertex graph does not create a cut vertex. Nor is either endpoint of a single isolated edge a cut vertex, although that edge is a bridge in a graph.

In a communications network, a cut vertex models a router whose failure separates surviving routers. The shared-$A$ example shows why having an alternative graph path around each individual edge does not protect against failure of the common router. An additional edge from $B$ to $D$ removes this particular vulnerability: after deleting $A$, $B,D$ still join the two sides. A bridge in a graph instead models a vulnerable link. This distinction tells us whether to add another cable between existing devices or a route avoiding an indispensable device; it describes connectivity, rather than traffic capacity or failure probabilities.

The beautiful structural consequence is that a graph splits into biconnected components joined at cut vertices. Within each nontrivial robust piece, a single vertex failure cannot separate the other vertices; between pieces, the shared cut vertices reveal the bottlenecks. Also, a Hamiltonian graph has no cut vertex: deleting any vertex from its Hamilton cycle leaves a Hamiltonian path through all remaining vertices.

Historically, Tarjan's June 1972 paper developed depth-first search as a tool for finding biconnected components in time linear in the numbers of vertices and edges. ^[ref] In his 1983 recollection, Tarjan credited Hopcroft with the original linear-time biconnected component algorithm during their collaboration beginning in summer 1970, and described the published version as a refinement. The historical lesson is how a carefully organized traversal turns many separate deletion experiments into one computation. ^[ref]

Initialize source distance to zero and other distances to infinity, then process vertices in topological order, relaxing their outgoing edges once. Every predecessor on a path to a vertex appears earlier, so induction through that ordering proves that its distance is final when processed. Negative weights are allowed because there are no directed cycles. With adjacency lists, topological sorting and all edge relaxations take $O(|V|+|E|)$ time; predecessor pointers reconstruct paths.

Depth-first search is a graph search that follows a branch as far as it can before returning to try the next unexplored branch. Starting at a vertex $s$ of an undirected graph on a finite set of vertices, mark $s$ as discovered. Scan its graph neighbours in a fixed order: for each undiscovered vertex, record the current vertex as its parent in a rooted tree in the discovery tree, mark the new vertex, and explore it immediately using recursion. Return when its adjacency list is exhausted. Discovery marks persist after return, preventing a graph cycle from causing repeated exploration. This branch-and-return rule is the maze exploration described in MIT's notes. ^[ref]

Use the same unweighted undirected graph as breadth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Visit graph neighbours in lexicographic order of their one-letter labels, starting at $A$. The discovery order, computed by the diagram's generator, isThe discovery edges in order are $AB,BD,BE,EC,CF,FG$. They form a rooted tree spanning the reached vertices, with root of a tree $A$. The other edges, $AC$ and $EG$, remain in the original graph but never discover a new vertex. In particular, the graph cycle $A,B,E,C,A$ causes no repeated discovery.

At $D$ there is no undiscovered graph neighbour, so its call returns to $B$. The next call enters $E$, then $C$, then $F$, then $G$. Immediately after discovering $G$, the call stack is $A,B,E,C,F,G$, with $G$ on top; $D$ is still discovered but its call has finished. The maximum call stack depth is six, although seven vertices are discovered. Following the recorded parent in a rooted tree backwards at each step reconstructs a graph path; here the route from $A$ to $G$ is $A,B,E,C,F,G$, using five edges. Breadth-first search instead finds $A,B,E,G$, using three edges. Depth-first search establishes reachability but does not guarantee the fewest edges.

An explicit LIFO stack can replace recursion, but its entries and discovery rule must be specified. To reproduce this exact traversal, store one frame per active vertex, retaining the next position in its adjacency list. Advance the top frame by one graph neighbour; if that vertex is undiscovered, mark it and push its frame immediately; pop an exhausted frame. Pushing all undiscovered graph neighbours at once and marking them on push is a different iterative variant. Even pushing them in reverse lexicographic order does not generally reproduce the parent in a rooted tree relationships above: $C$ would already be marked while processing $A$, so $E$ could not discover $C$.

With an adjacency list representation, constant-cost discovery checks and frame operations, and the graph neighbours already ordered, depth-first search has time complexity $O(|V|+|E|)$ in Big O notation. Each reached vertex is entered once and each incident edge is examined at most twice in an undirected graph; initializing all discovery marks costs $O(|V|)$. The call stack has depth at most $|V|$, since no active vertex repeats. Discovery marks and the recorded parent in a rooted tree for each nonroot vertex also need $O(|V|)$ auxiliary space complexity, excluding storage for the graph. Sorting adjacency lists to obtain a chosen order is additional work. ^[ref]

One start explores only its connected component of a graph. To cover a disconnected graph, start again at every still-undiscovered vertex while keeping all discovery marks; the discovery trees form a forest. Depth-first search is useful for reachability, constructing a spanning tree of a connected graph, and organizing the return steps needed by a depth-first traversal of a tree. For detecting a graph cycle in a simple graph that is an undirected graph, an edge to an already discovered vertex other than the current parent in a rooted tree closes a graph cycle; the immediate return edge to that parent in a rooted tree is not itself a graph cycle.

// Target: computer-science.bigb

For a finite simple graph that is an undirected graph, the DFS lowpoint of $v$ is the smallest DFS discovery time reachable by following zero or more discovery edges down its rooted tree, then at most one non-discovery edge to an ancestor. Staying at $v$ is allowed. Ignore the reverse traversal of the discovery edge to the parent in a rooted tree: it is the same edge, not an escape route. Start with $\mathrm{low}(v)=\mathrm{disc}(v)$. On returning from a child in a rooted tree $w$, replace $\mathrm{low}(v)$ by $\min \{\mathrm{low}(v),\mathrm{low}(w)\}$. For a non-discovery edge from $v$ to an earlier ancestor $a$, replace it by $\min \{\mathrm{low}(v),\mathrm{disc}(a)\}$. This summarizes how far upward the explored branch can reconnect. ^[ref]

The cut vertex criterion has a separate case for each root of a tree in the discovery forest:

Why does equality matter? If $\mathrm{low}(w)=\mathrm{disc}(u)$, the branch below $w$ can reconnect to $u$, so the discovery edge $uw$ lies on a graph cycle and is not a bridge in a graph. Deleting the vertex $u$ destroys that reconnection too. If $u$ has a parent in a rooted tree, the branch is then separated from that parent in a rooted tree, explaining the non-strict cut vertex test. For a root of a tree, there is no earlier side to separate from; distinct discovery branches cannot have an edge between them, since depth-first search would have explored them as one branch. This gives the two-children in a rooted tree rule. These are proof outlines of the criteria. ^[ref][ref]

In the joined-$CD$ example with DFS discovery times $1,2,3,4,5,6$, the DFS lowpoints in label order are $1,1,1,4,4,4$. For $C$ and its child in a rooted tree $D$, $4>3$: $CD$ is a bridge in a graph, and $C$ is a cut vertex. For $D$ and its child in a rooted tree $E$, $4=4$: $D$ is a cut vertex, although $DE$ is not a bridge in a graph. The root of a tree $A$ has only one child in a rooted tree, $B$, so it is not a cut vertex. In the shared-$A$ example, the root of a tree $A$ has two children in a rooted tree, $B$ and $D$, and is a cut vertex, while every DFS lowpoint is $1$ and no edge passes the strict bridge in a graph test.

Restart depth-first search at every undiscovered vertex to cover a disconnected graph, applying the root of a tree rule separately in each connected component of a graph. With adjacency lists and constant-cost label operations, computing all DFS lowpoints, cut vertices and bridges in a graph has time complexity $O(|V|+|E|)$ in Big O notation, because each vertex is discovered once and each edge is inspected twice. The simple parent-skipping rule assumes a simple graph. In a multigraph, skip only the actual parent edge, identified individually: a parallel edge to the same parent in a rooted tree is a valid reconnection and can prevent the first edge from being a bridge in a graph. The criteria here concern undirected graphs; a directed graph requires a different connectivity analysis.

The Dijkstra algorithm solves the single-source shortest path problem in a finite graph with nonnegative edge weights, finding distances to all reachable vertices. Start with tentative distance $d(A)=0$ and $d(v)=\infty$ elsewhere. Repeatedly choose the unfinalized vertex with least tentative distance, declare that label permanent, and perform edge relaxation on its outgoing edges. For an undirected graph, inspect both directions. A finite tentative distance always records the cost of a discovered graph path, but can improve before finalization.

In our example, finalizing $A$ discovers $C$ at $1$, $B$ at $4$, and $D$ at $10$. Choose $C$ next: edge relaxation through $C$ lowers $B$ to $1+2=3$ and $D$ to $1+5=6$. Choose $B$: edge relaxation through $B$ lowers $D$ to $3+1=4$. Finally choose $D$. The permanent distances are therefore $A:0$, $C:1$, $B:3$, $D:4$; the evolving tentative distances were $B:4\to 3$ and $D:10\to 6\to 4$.

Store a shortest-path predecessor whenever edge relaxation improves a label. The final table contains enough information to reconstruct routes, rather than merely their costs:

Following shortest-path predecessors backwards gives $D,B,C,A$; reversing the order gives $A,C,B,D$. If only this destination matters, stop when $D$ is finalized. Stopping when $D$ is first discovered would incorrectly return $10$. If the smallest remaining tentative distance is $\infty$, all remaining vertices are unreachable.

Why is the permanent choice safe? Suppose the selected vertex $u$ had a cheaper graph path. Let $y$ be the first unfinalized vertex on that graph path. Its preceding vertex was finalized, so edge relaxation has already offered $y$ a label no larger than that prefix's cost. Nonnegative remaining edge weights make the whole cost at least this prefix's cost; selection gives $d(u)\le d(y)$. A cheaper graph path would contradict these comparisons. Zero weights are allowed; ties can be resolved arbitrarily. This is the reason the label-setting shortest-path algorithm works, rather than a lucky feature of the drawing.

Negative weights break that reasoning. In a directed graph with $s\to u$ costing $2$, $s\to v$ costing $5$, and $v\to u$ costing $-4$, the Dijkstra algorithm would finalize $u$ at $2$ before discovering the cheaper cost $1$. The Bellman-Ford algorithm handles negative edge weights when no relevant negative directed cycle exists.

With an adjacency list and an indexed binary heap implementing a priority queue, the time complexity is $O((|V|+|E|)\log |V|)$ for $|V|\ge 2$, using Big O notation. Each vertex is extracted at most once, each edge is inspected once per direction, and each successful edge relaxation decreases a heap key in $O(\log |V|)$ time. This assumes constant-cost arithmetic and comparisons; exact computation with very large weights adds their representation cost. The queue uses $O(|V|)$ space beyond the graph. Simply scanning all remaining vertices gives $O(|V{|}^2+|E|)$ instead.^[ref][ref]

The 1959 paper presents the shortest path problem as its second problem, after the minimum spanning tree problem, and grows known shortest routes in increasing distance order.^[ref] In his later recollection, Dijkstra dated the shortest-route discovery to 1956: a demonstration for the ARMAC computer used a simplified Dutch railway map and printed the route between towns. A practical request became an enduring algorithm because the same distance rule applies to any suitable graph.^[ref]

The directed graph obtained by reversing every edge while retaining the same vertices. Scanning adjacency lists constructs the graph transpose in $O(|V|+|E|)$ time. A path reverses direction, while mutual reachability and therefore strongly connected components are unchanged.

Hierholzer's algorithm constructs an Euler circuit by growing closed trails along unused edges and splicing them at shared vertices, as in the Euler circuit criterion. Each edge must have a distinct record. An implementation using adjacency lists, a stack, and a used flag for each edge runs in $O(|V|+|E|)$ time, including the connectivity and vertex degree checks. Store both incidences of a self-loop, while marking its single edge record used only once.

Kahn's algorithm maintains each remaining vertex's indegree, the number of its unfinished incoming directed edges, and a FIFO queue of ready vertices. Initialize the counts by scanning all directed edges and enqueue every vertex of indegree zero. Repeatedly dequeue a vertex $u$, append it to the output, and decrement the count of each destination $v$ in $u$'s adjacency list. Enqueue $v$ exactly when its count becomes zero. When the FIFO queue empties, accept the output if it contains all vertices; otherwise report a directed cycle. ^[ref]

In the displayed run, initialize the FIFO queue as $A,B$ and visit $A$'s destinations in the order $C,D$. Removing $A$ makes $C$ ready but leaves $D$ waiting for $B$. Removing $B$ then makes $D$ ready. Publication becomes ready only after both $C$ and $D$ are removed. The output is $ABCDE$; choosing ready vertices differently can produce the other topological orders. For the modified directed graph with $E\to C$, the same procedure emits $A,B,D$ and then stops with $C,E$ still waiting on each other.

The invariant is that each stored indegree counts incoming directed edges from unprocessed vertices. A ready vertex therefore has every prerequisite already in the output. If the FIFO queue empties with vertices left, every remaining vertex has a predecessor in the remaining directed graph; the predecessor argument gives a directed cycle. The unprocessed vertices can also include tasks blocked downstream of a directed cycle, so the leftover list alone is not a list of exactly the cyclic vertices.

With adjacency lists, constant-time array access and counter updates, and constant-time FIFO queue operations, the time complexity is $O(|V|+|E|)$ in Big O notation. Initialization scans all vertices and directed edges; each vertex is then enqueued at most once and each outgoing directed edge processed at most once. Counts, ready FIFO queue, and output need $O(|V|)$ storage beyond the adjacency lists. Shifting an array on every dequeue invalidates this bound. ^{[ref] [ref]}

The name refers to A. B. Kahn's 1962 paper "Topological sorting of large networks", published in Communications of the ACM, volume 5, issue 11, pages 558–562. Its abstract motivates topological sorting through network analysis and project planning. ^[ref]

// Target: foundations-of-mathematics.bigb

During repeated deletion of vertices of current degree below $k$, every subgraph of minimum degree at least $k$ is contained in the active induced subgraph. If an active vertex has degree below $k$, its degree in any subgraph of the active graph is no greater, so no candidate can contain it. This proves the invariant inductively. A queue of threshold crossings and adjacency lists implements peeling in $O(|V|+|E|)$ time.

Use adjacency lists and a FIFO queue to implement the deletion rule in time complexity $O(|V|+|E|)$. Compute each initial degree of a vertex once, mark every vertex alive, and put all vertices of degree of a vertex zero or one in the FIFO queue. Each vertex is inserted at most once. Repeatedly remove the front vertex $v$, mark it dead, and traverse its original adjacency list. For each still-alive graph neighbour $u$, decrease the stored degree of a vertex of $u$ by one; if it has just become one, append $u$. A vertex already queued can drop from one to zero before its turn, but it stays queued and requires no second insertion. Stop when the FIFO queue is empty; the alive vertices induce $C_2(G)$.

For the displayed example, initially enqueue $(f,g,z)$ in that order. The successive FIFO queues, after each deletion and all its updates, areThis explains the delayed deletion of $d$: its initial degree of a vertex was three, but the relevant degree of a vertex is always its current one in the surviving induced subgraph. Removing only the original vertices of degree of a vertex one would give the wrong answer.

Initialization inspects every vertex and every adjacency list entry once. During deletion each original adjacency list is traversed at most once, so at most $2|E|$ entries are inspected in an undirected graph. All insertions, removals and stored-degree updates cost constant time each. Thus total time complexity is $O(|V|+|E|)$ and additional storage, beyond the adjacency lists, is $O(|V|)$. The cost includes isolated vertices; repeatedly rescanning the whole surviving graph after each deletion would lose this bound. The single-threshold FIFO queue method is enough for the 2-core; the full k-core of a graph decomposition computes all thresholds.

A fixed-size unit of stored information in a computational cost model. Counting machine words separately from bits makes assumptions about identifier and value sizes explicit: for example, the storage bound for an adjacency list assumes each vertex identifier fits into a constant number of machine words.

Neighbour enumeration reports the neighbours of a specified vertex. For a simple graph, scan its adjacency list and report each entry. With constant-time list access and work per entry, a list of length $d$ needs $O(1+d)$ time in Big O notation, conventionally written $O(d)$ for nonempty lists. Use vertex degree for an undirected graph and outdegree for a directed graph. Obtaining the list reference can take constant time; consuming it requires visiting every entry.^[ref]

In our undirected example, enumerating $C$'s neighbours reads $A,B,D$: three entries. Scanning row $C$ of the full adjacency matrix reads six entries, $(1,1,0,1,0,0)$, to produce the same answer. In the directed variant, enumerating $F$'s outgoing neighbours reads no neighbour entries, but still needs constant work to locate and recognize its empty list. For a multigraph, scanning lists enumerates incident edges with multiplicity; reporting only distinct neighbours additionally requires removing repetitions.

For a short time complexity argument, each reported entry requires at least one output operation, and one scan suffices. Across all vertices, the undirected entry count is ${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$ by the handshaking lemma; the directed count is ${\sum }_{v\in V}{d}^{+}(v)=|E|$. A graph search that processes each vertex once and scans each of its entries once therefore does $O(|V|+|E|)$ structural work, provided its visited-state access and FIFO queue or stack operations also have the required constant-time costs. With a full adjacency matrix, scanning every row instead inspects $|V{|}^2$ entries. This is how the representation enters the analysis of breadth-first search and depth-first search.