Topological Sort Flashcards
Front
Back
What is a topological sort?
An ordering of the vertices in a DAG such that for every directed edge u → v, vertex u comes before v in the ordering.
What type of graph allows a topological sort?
A directed acyclic graph (DAG).
Why can’t a graph with cycles be topologically sorted?
Because at least one task depends on itself, making a consistent ordering impossible.
What do the edges in a DAG represent in task scheduling?
Dependencies between tasks; task A → B means A must be completed before B.
What algorithm is commonly used to perform a topological sort?
Depth-First Search (DFS).
How do you determine the topological order using DFS?
Sort nodes in descending order of their finish times during DFS.
What action is taken when a node finishes in DFS during topological sort?
It is inserted at the head of a list to build the final topological order.
What is a back edge in DFS?
An edge that points to an ancestor in the DFS tree, indicating a cycle.
What does the presence of a back edge imply?
That the graph has a cycle and cannot be topologically sorted.
What is the time complexity of topological sorting using DFS?
Θ(V + E), where V is the number of vertices and E is the number of edges.
What is the purpose of tracking discovery and finish times in DFS?
To identify the order of node processing and detect cycles.
How can you use DFS to both traverse and sort a DAG?
By inserting each node into a list upon finish, creating a reverse order of finish times.
What is a real-life example of tasks with dependencies?
Making tea: boil water before pouring, place teabag before adding water, etc.
What happens if you try to topologically sort a graph with a cycle?
It will fail; no valid topological order exists.
How do you detect a cycle while doing DFS for topological sort?
By checking for back edges.
