Topological Sort with Cyclic Dependency Handling

viaGlassdoor

Problem: Given a directed graph representing dependencies, produce a topological ordering of the nodes, and correctly detect and handle cyclic dependencies (where no valid topological order exists).

Approach: Use Kahn's algorithm (BFS with in-degree counting) -- repeatedly remove nodes with in-degree 0, appending them to the order and decrementing neighbors' in-degrees. If not all nodes are processed by the end, a cycle exists. Alternatively, use DFS with a recursion-stack/visiting-state marker to detect back-edges (cycles) while building the order via a stack on finish times.

Add a follow-up question they asked
No follow-ups yet. Be the first to add one.
asked …
LeaderboardSalary
Language
Account