Processing math: 100%

Glossary

Algo: Cycle

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 n1 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.

Wikipedia

Welcome to Rosalind!

Rosalind is a platform for learning bioinformatics through problem solving.
Please login with Google/Twitter/Facebook or register a new account.