Elementary Graph Algorithms

Elementary Graph Algorithms

Overview

Graph-search answers must bind the representation contract to the invariant being used. Breadth-first search is a layer and shortest-unweighted-path argument; depth-first search is an interval, ancestor, and finish-time argument; topological sorting and strongly connected components are finish-time applications, not just traversal recipes.

Shared CLRS Conventions

• Follow the parent clrs skill for mathematical formatting: every expression, bound, inequality, or recurrence goes in a display LaTeX block, never in prose, tables, headings, or inline code spans.
• Use CLRS graph notation and theorem numbers when they clarify the proof.
• State whether the graph is directed or undirected before classifying edges or claiming reachability.
• State the representation before giving a running time.
• Treat adjacency-list order as an input-order detail: it can change discovery order and predecessor trees, but not breadth-first distances.

When to Use

Use this skill for:

• Choosing adjacency lists, adjacency matrices, or augmented adjacency structures.
• Breadth-first search for unweighted single-source shortest paths, layers, reachability, and breadth-first trees.
• Depth-first search for timestamp intervals, ancestor reasoning, edge classification, cycle detection, articulation points, bridges, and biconnected components.
• Topological sorting of directed acyclic graphs.
• Strongly connected components using the two-pass transpose algorithm.
• Euler-tour existence in directed graphs and reachability questions that reduce to component condensation.

Do not use it as the main skill for weighted shortest paths, minimum spanning trees, maximum flow, matching, or dynamic graph maintenance unless the immediate task is the representation or the initial traversal invariant.

Quick Reference

| Problem shape | Use | Required precondition | Main proof hook | | --- | --- | --- | --- | | Sparse graph traversal | Adjacency lists | Neighbor iteration dominates | Scan each list once | | Dense edge-existence queries | Adjacency matrix | Vertices have stable indices | Constant edge lookup, quadratic storage | | Unweighted shortest paths from one source | Breadth-first search | Unit edge cost or edge count metric | Layer monotonicity | | Ancestors, descendants, and cycle witnesses | Depth-first search | Fixed vertex and adjacency iteration order for exact forest | Parenthesis and white-path theorems | | Linear order of prerequisites | Topological sort | Directed acyclic graph | Decreasing finish times | | Mutual reachability classes | Strongly connected components | Directed graph | Component finish-time ordering on the transpose | | Undirected cut vertices and bridges | Depth-first low values | Connected component considered with tree and back edges | Subtree escape to a proper ancestor |

Representation Decision

Use adjacency lists when traversal or sparse storage is central. The storage bound is below.

$$ \Theta(V+E) $$

For directed graphs, list lengths sum to the number of edges. For undirected graphs, list lengths sum to twice the number of edges. Scanning all edges is linear in the representation.

Use adjacency matrices when edge-existence queries dominate and quadratic storage is acceptable. The storage and row-scan cost are below.

$$ \Theta(V^2) $$

For undirected graphs, the matrix is symmetric; storing only one triangle is an implementation choice, not a change in the model. For weighted graphs, entries may store weights and reserve a sentinel such as NIL, zero, or infinity for absent edges only when that sentinel cannot be confused with a real weight.

Use hash-backed or sorted adjacency containers when edge-existence queries must be faster than scanning a list. Name the tradeoff explicitly: extra memory, weaker iteration locality, possible loss of deterministic adjacency order, hash adversary assumptions, and the need to preserve edge attributes. Balanced trees or sorted vectors may be better when deterministic order or range-like scans matter.

For production workloads that need both fast edge-existence queries and fast deterministic neighbor scans, consider a hybrid representation: an ordered neighbor list or vector for iteration plus a per-vertex lookup index for membership. State the synchronization cost and memory overhead explicitly. If external vertex ids arrive on the hot path, include the external-id resolution map in the lookup cost and failure modes.

Store vertex and edge attributes in the representation that matches the caller's identity model: parallel arrays for dense stable vertex ids, object fields for owned vertex records, maps for external ids, or edge records when parallel edges or edge identity matters.

Breadth-First Search

Use breadth-first search when the distance measure is the number of edges on an unweighted path from a source. It works on directed and undirected graphs.

Core state:

• WHITE vertices are undiscovered.
• GRAY vertices are discovered and waiting in the queue.
• BLACK vertices have had their adjacency list scanned.
• The source has distance zero and NIL predecessor.
• Unreachable vertices keep infinite distance and NIL predecessor.

With adjacency lists, breadth-first search runs in the bound below.

$$ \Theta(V+E) $$

With an adjacency matrix, each dequeued vertex requires scanning a full row, so the traversal uses the bound below.

$$ \Theta(V^2) $$

Invariant Checklist

When explaining or using breadth-first search, include these facts:

1. The queue contains exactly the gray vertices at the loop test.
2. The queue contains vertices from at most two consecutive distance layers.
3. Enqueued distances are monotone by Corollary 20.4.
4. Each tree edge sets a newly discovered vertex one layer deeper than its predecessor.
5. Lemma 20.1 supplies the edge relaxation inequality for true unweighted distances.
6. Lemma 20.2 says computed distances are upper bounds until Theorem 20.5 proves equality for all reachable vertices.
7. Lemma 20.6 says the predecessor subgraph is a breadth-first tree.

Affirmative queue wording: next-layer vertices may be enqueued while current-layer vertices remain in the queue. FIFO order places them behind the remaining current-layer vertices, which is why processing stays layer-monotone. Do not say all vertices in the next layer wait until the entire current layer has finished before being enqueued.

Order-Dependence Rule

Distances are independent of adjacency-list order. Discovery order and the predecessor tree can change with adjacency-list order. If the task asks for a unique tree, require a specified neighbor order or a deterministic tie-breaker.

Breadth-First Edge Classification

For undirected breadth-first search:

• Tree edges go to the next layer.
• Cross edges connect vertices in the same layer or adjacent layers.
• Back and forward edge categories from depth-first search do not appear.

For directed breadth-first search:

• Tree edges go to the next layer.
• Forward edges do not appear under the depth-first classification idea.
• Cross edges can point within the same layer, to the next layer, or to an earlier layer within the permitted breadth-first distance constraint.
• Back edges can point to an ancestor or earlier layer; they do not invalidate shortest-path distances.

Depth-First Search

Use depth-first search when the answer depends on nesting, ancestors, finishing order, cycle witnesses, or decomposing an undirected graph by low values.

With adjacency lists, depth-first search runs in the bound below.

$$ \Theta(V+E) $$

Core state:

• WHITE vertices are undiscovered.
• GRAY vertices are active on the recursion stack.
• BLACK vertices are finished.
• Each vertex receives one discovery time and one finish time.
• The predecessor subgraph is a depth-first forest.

Theorem Hooks

• The parenthesis theorem, Theorem 20.7, says two vertex intervals are disjoint or one strictly contains the other. Containment is the ancestor relation.
• Corollary 20.8 turns strict interval nesting into proper-descendant reasoning.
• The white-path theorem, Theorem 20.9, says a vertex becomes a descendant exactly when a white path from the newly discovered ancestor exists at discovery time.
• In undirected graphs, Theorem 20.10 says every depth-first edge is tree or back; forward and cross edges do not occur.

Directed Edge Classification

Classify an edge by the target color at exploration time first:

| Target color when explored | Classification rule | | --- | --- | | WHITE | Tree edge. No exception. | | GRAY | Back edge to an active ancestor; self-loops are back edges. | | BLACK | Forward or cross edge; use timestamps to distinguish. |

Use interval rules when timestamps are known.

Tree or forward edge:

$$ u.d f(C) $$

• Corollary 20.15 turns that ordering around in the transpose to prevent the next second-pass search from leaking into an unvisited component.
• Theorem 20.16 follows by induction over the second-pass trees: the root's component is still white, every vertex in that component is reachable in the transpose, and every outgoing transpose edge to another component leads only to a component already assigned.

Avoid source-versus-sink handwaving. If you use those words, tie them back to the first-pass component finish-time order and the no-leakage argument in the transpose.

Advanced Depth-First Applications

Articulation Points

In a connected undirected graph, the depth-first root is an articulation point exactly when it has at least two children in the depth-first tree.

A nonroot vertex is an articulation point exactly when it has a child subtree with no back edge to a proper ancestor of that vertex. Use low values to express the test.

For a child subtree rooted at a child, the articulation condition is below.

$$ \text{child.low} \ge \text{vertex.d} $$

Bridges

A bridge is an edge that lies on no simple cycle. For a tree edge from a parent to a child, the bridge condition is below.

$$ \text{child.low} > \text{parent.d} $$

Biconnected Components

Maintain an edge stack during depth-first search. When an articulation boundary is detected, pop edges up to the boundary tree edge; those popped edges form one biconnected component. Nonbridge edges partition into biconnected components, while bridges stand alone as single-edge components when components are defined over edges.

Euler Tours in Directed Graphs

For a strongly connected directed graph, an Euler tour exists exactly when every vertex has equal indegree and outdegree. Find the tour by repeatedly following unused outgoing edges to form cycles and splicing cycles into the current tour, as in Hierholzer-style traversal. The edge-processing time is linear when unused outgoing edges are removed or advanced by cursor.

Reachability Labels on Component Graphs

For problems asking for a minimum reachable label or representative, first condense strongly connected components into a directed acyclic graph. Compute component answers in reverse topological order, combining each component's own label with answers from outgoing neighbors.

Answer Template

When answering a graph-search problem, use this order:

1. State graph direction, representation, and whether weights matter.
2. Choose the algorithm and name the precondition that makes it valid.
3. State the invariant or theorem hook.
4. Give the running time in a display block after naming the representation.
5. Name what is order-dependent and what is invariant under adjacency-list order.
6. Include production caveats for representation choices, ids, attributes, and adversarial lookup assumptions.

Replayable Pressure Pattern

Use this small directed graph to test edge classification and finish-time reasoning. Vertices are considered in alphabetical order, and each adjacency list is in the order shown.

A: B, C
B: D
C: D
D: B
E: C

Required reasoning:

• The first WHITE target reached from a vertex is a tree edge.
• The edge from D to B is back because B is gray while D is active.
• The edge from C to D is cross if D has already finished before C explores it.
• The second depth-first tree rooted at E can create a cross edge to an already finished component of the forest.

Use this pattern to catch the false claim that a WHITE target can be a cross edge, and to catch answers that classify BLACK targets without timestamps.

RED Pressure Failures This Skill Prevents

• Treating a WHITE target in depth-first search as a possible cross edge.
• Classifying BLACK targets without interval or discovery-order reasoning.
• Saying undirected depth-first search has forward or cross edges.
• Claiming every topological-sort edge target becomes a descendant.
• Explaining strongly connected components only with vague source or sink language instead of the finish-time component argument.
• Forgetting that adjacency-matrix breadth-first search scans rows and therefore has quadratic traversal cost.
• Treating breadth-first predecessor trees as unique when adjacency-list order is unspecified.
• Choosing hash-backed adjacency lists without naming memory, determinism, iteration locality, and adversarial hashing tradeoffs.
• Leaking inline formulas in CLRS answers, especially inside tables.

Common Mistakes

| Mistake | Correction | | --- | --- | | Giving a running time before naming the representation | State adjacency lists, adjacency matrix, or augmented adjacency structure first | | Using breadth-first search for weighted shortest paths | Switch to an algorithm whose preconditions match the weights | | Treating predecessor trees as unique | Say distances are stable, parents are order-dependent | | Calling a WHITE depth-first target cross | WHITE target means tree edge | | Using a gray target in topological sort | A gray target is a back edge, so the graph is not a directed acyclic graph | | Explaining strongly connected components by intuition only | Use component finish-time order and transpose no-leakage | | Putting formulas in table cells | Keep tables verbal and put formulas in display blocks nearby |

Verification Pressure Tests

• Ask for breadth-first search on a graph with two different neighbor orders. The answer must keep distances fixed while allowing different parents.
• Ask for directed depth-first edge classification with WHITE, GRAY, and BLACK targets. The answer must say WHITE means tree and must use intervals for BLACK targets.
• Ask why decreasing finish time topologically sorts a directed acyclic graph. The answer must handle both WHITE and BLACK target cases.
• Ask why the second pass of the strongly connected components algorithm cannot leak into a different unvisited component. The answer must cite the component finish-time ordering and transpose argument.
• Ask whether an adjacency matrix is appropriate for a sparse production graph with frequent edge-existence queries. The answer must weigh memory against lookup needs and mention augmented adjacency alternatives.
• Ask for a production representation with sparse graph storage, frequent membership tests, deterministic full-neighbor scans, weighted edges, and external vertex ids. The answer must discuss hybrid list-plus-lookup designs, synchronization cost, id resolution, and edge records.
• Ask for an answer under the parent CLRS formatting rule. The answer must not place formulas in prose, headings, tables, or inline code spans.

Static Checks

• Frontmatter name matches the directory slug.
• Description begins with Use when and names concrete triggers.
• The parent clrs router has a bullet for this chapter skill.
• Bounds and inequalities appear only in display LaTeX blocks.
• Tables contain verbal guidance, not formula expressions.
• The skill contains no narrative session log or source-conversion diary.
• Scan generated answers for inline math delimiters, asymptotic expressions in prose, inequalities in code sp

…

Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

• Author: Arcadi4
• Source: Arcadi4/nerdy
• License: MIT

Install and usage instructions live in the source repository linked above.