Topological Sort Using DFS in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Topological Sort using DFS?

It visits each node and explores all its descendants before adding the node to the order. This ensures that all dependencies come before the node itself.

beginner

In Topological Sort using DFS, when do we add a node to the result list?

We add the node after visiting all its neighbors (children), meaning after the recursive DFS calls for its neighbors finish.

intermediate

Why can Topological Sort only be applied to Directed Acyclic Graphs (DAGs)?

Because cycles create circular dependencies, making it impossible to order nodes linearly without conflicts.

beginner

What data structure is commonly used to store the final topological order in DFS approach?

A stack or a list where nodes are pushed after visiting all their descendants, then reversed to get the correct order.

intermediate

How does DFS help detect cycles during Topological Sort?

By keeping track of nodes currently in the recursion stack; if we revisit a node in this stack, a cycle exists.

What type of graph is required for Topological Sort to work?

A Any Graph

B Undirected Graph

C Directed Acyclic Graph (DAG)

D Cyclic Graph

Topological Sort requires a Directed Acyclic Graph to ensure a valid linear ordering.

In DFS-based Topological Sort, when is a node added to the output list?

A After visiting all its neighbors

B Before visiting its neighbors

C When first discovered

D Randomly

Nodes are added after all their neighbors are visited to respect dependencies.

What does a cycle in the graph indicate during Topological Sort?

A Graph is disconnected

B Ordering is possible

C Graph is undirected

D Ordering is impossible

Cycles mean circular dependencies, so no valid topological order exists.

Which data structure is typically used to store nodes during DFS Topological Sort?

A Stack

B Hash Map

C Queue

D Linked List

A stack stores nodes after visiting descendants, helping reverse the order for final output.

How can DFS detect a cycle in the graph during Topological Sort?

A By checking if a node is visited twice in total

B By checking if a node is in the current recursion stack

C By counting edges

D By sorting nodes alphabetically

If a node is found again in the current recursion path, it means a cycle exists.

Explain step-by-step how DFS is used to perform Topological Sort on a graph.

Think about visiting nodes and when to add them to the result.

Describe why Topological Sort cannot be done on graphs with cycles and how DFS helps identify such cycles.

Focus on the role of recursion stack in DFS.