Which operation helps determine if a dependency graph has a cycle?

Which operation helps determine if a dependency graph has a cycle?

• A. Topological sort
• B. Tarjan's strongly connected components algorithm
• C. Depth-first search with recursion
• D. Breadth-first search

Answer: (A)

Topological sort is a natural tool for detecting cycles in a dependency graph because it seeks a linear order of all nodes where every edge goes from an earlier node to a later node. In a graph that represents dependencies, such an ordering exists only if there are no cycles. If a cycle is present, there’s no way to place the involved nodes so that all prerequisites come before their dependents, so the sort cannot process all nodes (for example, you’ll run out of nodes with in-degree zero to start or you’ll end up with unprocessed vertices). This direct relationship—successful completion implies no cycles, while failure implies one—is why topological sort is the go-to operation for cycle detection in dependency graphs. Tarjan’s strongly connected components algorithm can reveal cycles by identifying components with multiple nodes (or a self-loop), but it’s more general and heavier than needed for simply detecting a cycle in a dependency graph. Depth-first search with recursion can detect cycles by finding back edges, but that requires extra bookkeeping (a recursion stack) and is not as straightforward for confirming a global acyclic ordering. Breadth-first search by itself isn’t a standard cycle detector for directed graphs.

Topological sort is a natural tool for detecting cycles in a dependency graph because it seeks a linear order of all nodes where every edge goes from an earlier node to a later node. In a graph that represents dependencies, such an ordering exists only if there are no cycles. If a cycle is present, there’s no way to place the involved nodes so that all prerequisites come before their dependents, so the sort cannot process all nodes (for example, you’ll run out of nodes with in-degree zero to start or you’ll end up with unprocessed vertices). This direct relationship—successful completion implies no cycles, while failure implies one—is why topological sort is the go-to operation for cycle detection in dependency graphs.

Tarjan’s strongly connected components algorithm can reveal cycles by identifying components with multiple nodes (or a self-loop), but it’s more general and heavier than needed for simply detecting a cycle in a dependency graph. Depth-first search with recursion can detect cycles by finding back edges, but that requires extra bookkeeping (a recursion stack) and is not as straightforward for confirming a global acyclic ordering. Breadth-first search by itself isn’t a standard cycle detector for directed graphs.