Detecting Cycles

Understand the different techniques used to detect cycles in a graph.

Directed acyclic graph

A directed acyclic graph or dag is a directed graph with no directed cycles. Any vertex in a dag that has no incoming vertices is called a source; any vertex with no outgoing edges is called a sink. An isolated vertex with no incident edges at all is both a source and a sink. Every dag has at least one source and one sink but may have more than one of each. For example, in the graph with nn vertices but no edges, every vertex is a source, and every vertex is a sink.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy