Cycle Detection
An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge). Equivalently, all the back edges, which DFS skips over, are part of cycles. In the case of undirected graphs, only O(n) time is required, since at most n − 1 edges can be tree edges (where n is the number of vertices).
A directed graph has a cycle if and only if a DFS finds a back edge. Forward and cross edges do not necessarily indicate cycles. Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.
Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.
Read more about this topic: Cycle (graph Theory)
Famous quotes containing the word cycle:
“The lifelong process of caregiving, is the ultimate link between caregivers of all ages. You and I are not just in a phase we will outgrow. This is life—birth, death, and everything in between.... The care continuum is the cycle of life turning full circle in each of our lives. And what we learn when we spoon-feed our babies will echo in our ears as we feed our parents. The point is not to be done. The point is to be ready to do again.”
—Paula C. Lowe (20th century)