Can a directed acyclic graph contain an undirected cycle?

Yes; the three-arrow triangle example does.

Does a directed cycle always mean an error?

No. Repeated transitions and feedback can be intentional.

Are all vertices left by topological removal on a cycle?

No; downstream blocked vertices can remain too.

AI Glossary / Mathematics and optimization / Advanced

Directed cycle

Definition

A directed cycle is a sequence of directed edges that follows their arrow directions and returns to its starting vertex. For a simple directed cycle, no vertex repeats except the start appearing again at the end of the written route. For example, A → B → C → A is a directed cycle. Its significance depends on what the vertices and arrows represent, such as dependencies, transitions or communication links.

What it means

The arrows must form a consistently traversable loop. A picture that looks circular is not enough. If the arrows are A → B, A → C and B → C, the three vertices form an undirected triangle when arrowheads are ignored, but there is no directed cycle.
When an arrow means that one task must finish before another starts, a cycle creates incompatible strict precedence requirements. In a state-transition or feedback model, a cycle may instead represent intended repeated behavior. Its meaning determines whether the cycle is a defect.

How it works

Follow outgoing edges and check whether the route can return to a vertex already on the current path. A depth-first search can detect a directed cycle when it encounters an edge back to an active ancestor. Encountering any previously visited vertex is not sufficient; the vertex's position in the search matters.
Another approach repeatedly removes vertices with no incoming edges. A finite directed graph has a topological ordering exactly when it contains no directed cycle. If this removal process stops before all vertices are removed, a cycle exists. Listing every cycle is a different task from detecting one and can require much more work because there may be many cycles.

Three practical examples

A build system represents prerequisites as arrows from a required component to a dependent component. A directed cycle prevents a strict one-pass build order until the dependency problem is resolved.
A workflow model includes a review step that can send an item back for revision. The directed cycle describes a permitted repeated process. Additional rules determine when that process terminates; the cycle alone does not establish an infinite execution.
A directed communication graph contains routes that return to their starting device. Such cycles can support routing alternatives, while a particular forwarding policy may still need measures to prevent unintended repeated forwarding.

Think of it this way

Think of following one-way signs around a city block. A genuine directed cycle lets you obey every sign and eventually return to where you began. Three streets drawn as a triangle do not guarantee this route if their one-way directions disagree.

Worked example

Consider five tasks P, A, B, C and D. Let an arrow X → Y mean that X must finish before Y starts. The edges are P → A, A → B, B → C, C → A and C → D.
The route A → B → C → A is a directed cycle of length three. Its requirements imply that A must precede B, B must precede C, and C must precede A. No linear ordering can satisfy all three strict requirements.
Now apply the zero-incoming-edge removal procedure. Initially, P has no incoming edges. A has two, from P and C, while B, C and D each have one. Remove P and its outgoing edge. A still has an incoming edge from C, and B, C and D still each have one. The procedure stops with A, B, C and D remaining.
Crucially, D is not on the cycle. It is blocked downstream because it waits for C, and it has no outgoing edge that could return to another task. A failed topological-ordering attempt therefore identifies the existence of a cycle without making every unprocessed vertex a cycle member.
If the C → A requirement is established to be a modeling mistake and removed, the remaining graph permits the order P, A, B, C, D.

Illustrative case study

In a fictional reporting project, a scheduler reports four unresolved tasks after completing an initial preparation step. The team initially assumes all four participate in a circular dependency.
Examining the graph reveals the worked example's pattern: three tasks form the cycle, while a final publication task only waits for one of them. The team focuses its specification review on the actual cyclic dependencies rather than blaming the publication step.
It discovers that one arrow combined two meanings: consuming an already available prior-version artifact and waiting for the current-version artifact. The team separates those versions and rebuilds the dependency graph. It checks the revised requirements with the process owners and verifies that a topological order exists. The fix comes from correcting the dependency meaning, not from arbitrarily dropping whichever edge is easiest to remove.

Common misconceptions and mistakes

An undirected loop does not necessarily form a directed cycle. A strongly connected component with several vertices contains directed cycles, but a single isolated vertex is not itself a cycle. If self-loops are allowed, an edge from a vertex to itself can count as a cycle of length one; state the graph convention.
Rotating a written cycle's starting point does not normally create a different cycle: A → B → C → A and B → C → A → B describe the same traversal. Reversing it requires the corresponding reverse-direction edges, which may not exist.

Business use

Use cycle checks when designing strict dependencies, scheduling rules or staged processing. Record what each arrow means and distinguish the vertices forming a cycle from those blocked by it. For intentional feedback or repeated workflows, specify the conditions that advance or end an iteration. Match the analysis to the question: detecting a cycle, identifying its members and enumerating all cycles are different requirements.

Check your understanding

Which vertices form the worked example's cycle?

Answer: A, B and C.

Why does D remain unprocessed?

Answer: Its predecessor C cannot be removed, even though D is not a cycle member.

What order works after removing the erroneous C → A edge?

Answer: P, A, B, C, D.

Related terms

Directed graph
Directed acyclic graph
Depth First Search
Feedback loop
topological ordering
strongly connected component
dependency graph
simple cycle

Learn next

Compare cycle detection with topological sorting and strongly connected component analysis. Practice tracing dependency directions before interpreting a scheduler's unresolved tasks.

Sources

Aalto Dictionary of Machine Learning, directed cycle and directed acyclic graph: directed closed routes and the absence of cycles. https://aaltodictionaryofml.github.io/ADictML_Main.pdf NetworkX, simple_cycles: simple-cycle conventions, rotation equivalence, self-loops and cycle enumeration. https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.cycles.simple_cycles.html The prerequisite graph, removal trace and fictional reporting case are original teaching illustrations.

Previous: Directed acyclic graph Next: Directed graph