Chapter 18. Directed Paths and Cycles

Directed paths and directed cycles are the basic motion patterns in a directed graph. They describe what can be reached when every arc must be followed in its assigned direction.

In an undirected graph, an edge can be traversed in either direction. In a directed graph, an arc can be traversed only from its tail to its head. Thus a directed path is more restrictive than an undirected path. This restriction is exactly what makes directed graphs useful for modeling dependencies, precedence, control flow, hyperlinks, and one-way movement.

18.1 Directed Walks

Let

D = (V,A)

be a directed graph. A directed walk is a finite sequence of vertices

v_0, v_1, \ldots, v_k

such that

(v_{i-1}, v_i) \in A

for each $i = 1,2,\ldots,k$ .

The integer $k$ is the length of the walk. It counts the number of arcs used, not the number of vertices listed.

A directed walk may repeat vertices. It may also repeat arcs, if the graph permits the same arc to be used again during the walk. The defining condition is only that each consecutive pair follows an existing arc in the correct direction.

For example, if

A = \{(a,b),(b,c),(c,b),(c,d)\},

then

a,b,c,b,c,d

is a directed walk. Each step follows an arc:

a \to b,\qquad b \to c,\qquad c \to b,\qquad b \to c,\qquad c \to d.

The sequence

d,c,b,a

is not a directed walk unless the reverse arcs also exist. The underlying undirected graph may connect these vertices, but the direction of the arcs prevents this traversal.

18.2 Directed Trails

A directed trail is a directed walk in which no arc is repeated.

Vertices may repeat, but arcs may not. Thus a directed trail controls repetition at the level of arcs.

For example, suppose

A = \{(a,b),(b,c),(c,a),(c,d),(d,c)\}.

Then

a,b,c,d,c,a

is a directed trail if all listed arcs are distinct. It repeats the vertex $c$ , but it does not repeat any arc.

A directed trail is useful when arcs represent resources that may be used only once. Eulerian trails, studied later, are directed trails that use every arc of a graph exactly once.

18.3 Directed Paths

A directed path is a directed walk in which all vertices are distinct.

Thus a directed path has the form

v_0, v_1, \ldots, v_k,

where

(v_{i-1},v_i) \in A

for each $i$ , and

v_i \neq v_j

whenever $i \neq j$ .

A directed path is sometimes called a simple directed path. It records a route that never visits the same vertex twice.

The length of the path is the number of arcs:

k.

A path of length $0$ consists of a single vertex. This trivial path is often allowed because every vertex should be reachable from itself by a path of length $0$ .

For example, if

a \to b \to c \to d,

then

a,b,c,d

is a directed path of length $3$ .

The sequence

a,b,c,b

is not a directed path, because $b$ is repeated. It may still be a directed walk.

18.4 Directed Cycles

A directed cycle is a closed directed path. It begins and ends at the same vertex, follows arc directions, and has no other repeated vertices.

It has the form

v_0, v_1, \ldots, v_{k-1}, v_0,

where $k \geq 1$ , each arc

(v_i,v_{i+1})

is in $A$ , with indices taken modulo $k$ , and the vertices

v_0, v_1, \ldots, v_{k-1}

are distinct.

A directed cycle is therefore a directed circuit with no repeated vertices except for the repeated start and end. Standard graph terminology treats a directed cycle as a closed directed trail whose only repeated vertex is the first and last one.

For example,

a \to b \to c \to a

is a directed cycle of length $3$ .

The sequence

a \to b \to c \to b \to a

is closed, but it is not a directed cycle, because $b$ appears more than once. It may be a closed directed walk or a directed circuit, depending on whether arcs are repeated.

18.5 Direction Cannot Be Ignored

The condition of direction is not cosmetic. It changes the structure of the graph.

Suppose the arcs are

a \to b, \qquad b \to c.

Then there is a directed path from $a$ to $c$ :

a,b,c.

There is no directed path from $c$ to $a$ , unless additional arcs are present.

The underlying undirected graph has a path between $c$ and $a$ . But the directed graph does not allow movement against arc direction. This distinction is central in all directed graph theory.

18.6 Reachability

A vertex $v$ is reachable from a vertex $u$ if there exists a directed path from $u$ to $v$ .

We may write

u \leadsto v

to mean that $v$ is reachable from $u$ .

Reachability is reflexive when paths of length $0$ are allowed, because every vertex reaches itself. Reachability is also transitive: if $u$ reaches $v$ , and $v$ reaches $w$ , then $u$ reaches $w$ . The two paths can be joined to form a directed walk from $u$ to $w$ , and from that walk one can extract a directed path if repeated vertices occur.

Reachability is generally not symmetric. The existence of a path from $u$ to $v$ does not imply the existence of a path from $v$ to $u$ .

18.7 Distance in a Directed Graph

If $v$ is reachable from $u$ , the directed distance from $u$ to $v$ , denoted

d(u,v),

is the length of a shortest directed path from $u$ to $v$ .

If $v$ is not reachable from $u$ , one commonly writes

d(u,v)=\infty.

Directed distance may fail to be symmetric. It may happen that

d(u,v) \neq d(v,u),

or that one quantity is finite while the other is infinite.

For example, in the directed path

a \to b \to c,

we have

d(a,c)=2,

but

d(c,a)=\infty.

Directed distance is used in routing, automata, scheduling, program analysis, and graph search algorithms.

18.8 Cycles and Dependence

Directed cycles often represent circular dependence.

Suppose an arc

u \to v

means that $v$ depends on $u$ . Then a directed cycle

v_0 \to v_1 \to \cdots \to v_{k-1} \to v_0

means that each object depends, directly or indirectly, on itself.

This is usually a structural obstruction.

In a build system, a directed cycle may mean that target $A$ requires target $B$ , while $B$ eventually requires $A$ . In a course prerequisite graph, it may mean that no course in the cycle can be taken first. In a database schema or module graph, it may signal recursive coupling.

For this reason, many dependency graphs are required to be acyclic.

18.9 Directed Acyclic Graphs

A directed acyclic graph is a directed graph with no directed cycles. It is often abbreviated as DAG.

A DAG may contain undirected cycles in its underlying graph. What it forbids is a cycle whose arcs can be followed consistently in one direction.

For example, the arcs

a \to b, \qquad a \to c, \qquad b \to d, \qquad c \to d

form a DAG. The underlying undirected graph contains the cycle

a,b,d,c,a,

but there is no directed cycle.

DAGs are central in scheduling, partial orders, compiler analysis, dynamic programming, and causal modeling. A finite directed graph has a topological ordering exactly when it has no directed cycle, a result studied in the chapter on topological ordering.

18.10 Closed Directed Walks and Directed Circuits

A closed directed walk is a directed walk

v_0, v_1, \ldots, v_k

with

v_0 = v_k.

It may repeat vertices and arcs.

A directed circuit is a closed directed trail. It may repeat vertices, but it does not repeat arcs.

A directed cycle is a directed circuit with no repeated vertices except for the first and last.

Thus we have the hierarchy:

Object	Repeated vertices allowed?	Repeated arcs allowed?	Closed?
Directed walk	Yes	Yes	Optional
Directed trail	Yes	No	Optional
Directed path	No	No	No, except trivial conventions
Closed directed walk	Yes	Yes	Yes
Directed circuit	Yes	No	Yes
Directed cycle	Only first equals last	No	Yes

The terminology varies slightly between authors. The mathematical content remains the same when the convention is stated clearly.

18.11 Extracting a Path from a Walk

If there is a directed walk from $u$ to $v$ , then there is a directed path from $u$ to $v$ .

This fact is simple but important.

Suppose a directed walk repeats a vertex:

v_i = v_j

with $i < j$ . Then the part

v_i, v_{i+1}, \ldots, v_j

forms a closed section of the walk. Removing this closed section leaves a shorter directed walk with the same starting and ending vertices.

Repeating this deletion process eventually gives a directed walk with no repeated vertices. That walk is a directed path.

Therefore reachability can be defined using walks or paths. The two definitions are equivalent for finite directed graphs.

18.12 Cycles Inside Closed Walks

Every nontrivial closed directed walk contains a directed cycle.

To see this, take a closed directed walk

v_0, v_1, \ldots, v_k = v_0.

If the only repeated vertex is $v_0$ , then the walk itself is a directed cycle. If another vertex repeats, choose a shortest closed subwalk between two equal occurrences of a vertex. This shortest closed subwalk has no repeated internal vertices. Hence it is a directed cycle.

This result explains why cycles are the irreducible closed structures in directed graphs. A closed walk may be complicated, but it contains at least one simple directed cycle.

18.13 Hamiltonian Directed Paths and Cycles

A Hamiltonian directed path is a directed path that visits every vertex exactly once.

A Hamiltonian directed cycle is a directed cycle that visits every vertex exactly once before returning to its starting vertex.

These objects are global. They concern all vertices of the graph, not merely local reachability.

For example, in a directed graph with vertices

\{a,b,c,d\},

the sequence

a,b,d,c

is Hamiltonian if each listed consecutive pair is an arc and all four vertices appear exactly once. Course material on directed graphs commonly defines Hamiltonian paths and cycles in this vertex-covering sense.

Finding Hamiltonian paths and cycles is computationally difficult in general. Later chapters discuss this in the context of NP-complete graph problems.

18.14 Eulerian Directed Walks and Circuits

An Eulerian directed walk is a directed walk that uses every arc exactly once. If it is closed, it is an Eulerian directed circuit.

Eulerian questions concern arcs rather than vertices. This distinguishes them from Hamiltonian questions.

A directed graph can have an Eulerian circuit only if each vertex has equal in-degree and out-degree, together with an appropriate connectivity condition on the nonzero-degree part of the graph. This is the directed analogue of Eulerian circuits in undirected graphs.

Eulerian circuits are important in route inspection, genome assembly, de Bruijn graphs, and sequencing problems.

18.15 Paths, Cycles, and Adjacency Matrices

Let $D$ have adjacency matrix $M$ , where

M_{ij}=1

if there is an arc from $v_i$ to $v_j$ , and $0$ otherwise.

The powers of $M$ count directed walks. The entry

(M^k)_{ij}

counts the number of directed walks of length $k$ from $v_i$ to $v_j$ , when $M$ is a $0$ - $1$ adjacency matrix and ordinary matrix multiplication is used.

This gives an algebraic method for studying directed movement. Paths and cycles become visible through matrix powers. In particular, nonzero diagonal entries of powers of $M$ indicate closed directed walks.

For example, if

(M^3)_{ii} > 0,

then there is a closed directed walk of length $3$ from $v_i$ back to itself. In a simple directed graph without loops, such a walk often corresponds to a directed triangle, though repeated-vertex cases must be handled carefully.

18.16 Cycle Detection

Detecting directed cycles is a basic algorithmic problem.

Depth-first search can detect a directed cycle by tracking the active recursion stack. If the search reaches a vertex that is already active, then the graph contains a directed cycle. Equivalently, such an edge points back to an ancestor in the current depth-first search tree. Standard algorithmic treatments describe cycle detection in directed graphs in terms of depth-first search and back edges.

Cycle detection is used in dependency resolution, package managers, compilers, build systems, deadlock analysis, and topological sorting.

If a directed graph has no directed cycle, then topological sorting is possible. If a directed cycle exists, no topological ordering can place every arc from earlier to later.

18.17 Common Mistakes

A common mistake is to treat a directed edge like an undirected edge. In a directed path, every step must follow the arrow. The existence of $u \to v$ does not allow the step $v \to u$ .

Another mistake is to confuse walks, trails, and paths. Walks allow repetition. Trails forbid repeated arcs. Paths forbid repeated vertices.

A third mistake is to assume that a closed directed walk is automatically a directed cycle. A directed cycle must be simple except for the repeated start and end vertex.

A fourth mistake is to confuse Hamiltonian and Eulerian conditions. Hamiltonian objects visit vertices. Eulerian objects use arcs.

18.18 Summary

A directed walk follows arcs in their assigned direction. A directed trail is a directed walk with no repeated arcs. A directed path is a directed walk with no repeated vertices. A directed cycle is a closed directed path.

Reachability asks whether one vertex can be reached from another by a directed path. Directed distance measures the length of a shortest such path. Directed cycles represent circular movement or circular dependence. Directed acyclic graphs are directed graphs with no directed cycles.

These ideas are elementary, but they support much of the theory that follows: strong connectivity, topological ordering, shortest paths, network flow, Eulerian circuits, Hamiltonian cycles, and directed graph algorithms.