Detect cycle in a directed graph

Q: Detect cycle in a directed graph

This question evaluates mastery of graph algorithms and graph theory concepts—specifically directed cycle detection—and assesses the ability to reason about algorithmic correctness and to analyze time and space complexity for competing approaches.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given a directed graph represented by an adjacency list with n vertices and m edges, determine whether the graph contains a cycle. Describe and implement an algorithm that returns true if a cycle exists and false otherwise. Explain the time and space complexity, and discuss both a DFS-based approach using a recursion stack and an approach based on Kahn’s topological sort.

Detect cycle in a directed graph

Overview

Comments (0)