Topological sorting in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is topological sorting?

Topological sorting is a way to arrange the nodes of a directed graph in a linear order so that for every directed edge from node A to node B, A comes before B in the order.

beginner

Which type of graph can have a topological sort?

Only directed acyclic graphs (DAGs) can have a topological sort because cycles would make it impossible to order nodes without conflicts.

intermediate

Why can't graphs with cycles be topologically sorted?

Because in a cycle, nodes depend on each other in a loop, so there is no way to order them linearly without breaking the dependency.

intermediate

Name two common algorithms used for topological sorting.

The two common algorithms are Kahn's algorithm and Depth-First Search (DFS) based algorithm.

beginner

Give a real-life example where topological sorting is useful.

Topological sorting is useful in scheduling tasks where some tasks must be done before others, like building a house where the foundation must be done before walls.

Which graph property is required for topological sorting?

A The graph must be complete

B The graph must be undirected

C The graph must contain cycles

D The graph must be directed and acyclic

Topological sorting only works on directed acyclic graphs (DAGs).

What does a topological sort of a graph represent?

A A shortest path between two nodes

B A random order of nodes

C A linear order of nodes respecting dependencies

D A cycle detection method

It arranges nodes so that all dependencies come before dependent nodes.

Which algorithm is NOT used for topological sorting?

A Dijkstra's algorithm

B Kahn's algorithm

C Depth-First Search (DFS)

D None of the above

Dijkstra's algorithm is for shortest paths, not topological sorting.

What happens if you try to topologically sort a graph with a cycle?

A It is impossible to find a valid order

B The cycle is ignored

C The graph becomes undirected

D The sorting completes normally

Cycles prevent a linear ordering that respects dependencies.

In a task scheduling scenario, what does topological sorting help with?

A Ignoring task dependencies

B Ordering tasks so prerequisites come first

C Randomizing task order

D Finding the longest task

It ensures tasks are done only after their prerequisites.

Explain what topological sorting is and why it requires a directed acyclic graph.

Think about ordering tasks with dependencies and why loops cause problems.

Describe two algorithms used for topological sorting and how they generally work.

One uses removing nodes step-by-step, the other uses depth-first search.