cycle
A path in a graph that starts and ends at the same vertex.
In more detail
A dependency graph with a cycle has no valid order: A needs B, which needs A. Trees and DAGs have no cycles by definition, and Kruskal's algorithm refuses any edge that would close one.
Related terms
- cycle detection — Finding whether a graph contains a cycle; in a directed graph, DFS with three colours finds one by spotting an edge back to a vertex still in progress.
- directed acyclic graph — A directed graph with no cycles, so following edges can never bring you back to where you started.
- tree — A hierarchy of nodes joined by edges, with one root at the top, no cycles, and exactly one path between any two nodes.
Taught in
- Deques And Ring Buffers — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers