What is Topological Sorting in Graphs
💡 Concept Name
Topological Sorting – A linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before v.
📘 Quick Intro
Topological sort is only possible in DAGs and is widely used in scheduling problems, task ordering, dependency resolution, and more. It ensures that each task’s prerequisites are completed first.
🧠 Analogy / Short Story
Think of a college course plan: you must take "Intro to Programming" before "Data Structures", and "Data Structures" before "Algorithms". A topological sort gives you an order that respects these prerequisites.
🔧 Technical Explanation
- 🏗️ DAG Requirement: Only valid for Directed Acyclic Graphs.
-
📥 Kahn’s Algorithm:
- Uses in-degree count and queue
- Removes nodes with in-degree 0
-
🧭 DFS-based Method:
- Recursive post-order traversal
- Push nodes onto a stack after processing neighbors
- 🕒 Time Complexity: O(V + E)
🎯 Purpose & Use Case
- ✅ Course scheduling systems
- ✅ Build systems and task dependency resolution
- ✅ Compiler instruction ordering
💻 Real Code Example
// Kahn's Algorithm for Topological Sort
List<int> TopologicalSort(List<int>[] graph, int v)
{
int[] inDegree = new int[v];
foreach (var edges in graph)
foreach (var node in edges)
inDegree[node]++;
Queue<int> q = new Queue<int>();
for (int i = 0; i < v; i++)
if (inDegree[i] == 0)
q.Enqueue(i);
List<int> result = new List<int>();
while (q.Count > 0)
{
int u = q.Dequeue();
result.Add(u);
foreach (var neighbor in graph[u])
{
if (--inDegree[neighbor] == 0)
q.Enqueue(neighbor);
}
}
return result.Count == v ? result : null; // Null indicates cycle
}
❓ Interview Q&A
Q1: What is topological sorting?
A: A linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, u comes before v.
Q2: Which types of graphs can be topologically sorted?
A: Directed acyclic graphs (DAGs) only.
Q3: What are common applications of topological sorting?
A: Task scheduling, resolving symbol dependencies, build systems, and instruction ordering.
Q4: What is the time complexity of topological sorting?
A: O(V + E), where V is vertices and E is edges.
Q5: Name two common algorithms for topological sorting.
A: Kahn's algorithm and DFS-based algorithm.
Q6: How does Kahn’s algorithm work?
A: By repeatedly removing nodes with zero in-degree and updating in-degrees of adjacent nodes.
Q7: How does DFS-based topological sorting work?
A: By performing DFS and pushing nodes onto a stack after visiting all descendants.
Q8: What happens if the graph contains a cycle?
A: Topological sorting is not possible.
Q9: Can topological sorting be used for undirected graphs?
A: No, it is only defined for directed acyclic graphs.
Q10: How can topological sorting detect cycles?
A: If a cycle exists, algorithms detect it by checking remaining nodes with non-zero in-degree or recursion stack.
📝 MCQs
Q1. What does topological sorting produce?
- Shortest path
- Linear ordering of vertices
- Cycle detection
- Graph coloring
Q2. Which graph type supports topological sorting?
- Undirected graph
- Directed graph with cycles
- Directed acyclic graph
- Complete graph
Q3. What is the time complexity of topological sort?
- O(V^2)
- O(E^2)
- O(V + E)
- O(log V)
Q4. Name a topological sort algorithm.
- Dijkstra
- Kahn's algorithm
- Prim's algorithm
- Kruskal's algorithm
Q5. How does Kahn’s algorithm work?
- Remove nodes randomly
- Remove nodes with zero in-degree
- Remove leaf nodes
- Remove nodes with highest degree
Q6. How does DFS-based topological sort work?
- Pre-order DFS
- Post-order DFS traversal
- Level order traversal
- BFS traversal
Q7. Can topological sorting detect cycles?
- No
- Yes
- Sometimes
- Depends on graph
Q8. Is topological sorting possible for graphs with cycles?
- Yes
- No
- Only for some cycles
- Depends on edges
Q9. Can topological sorting be applied to undirected graphs?
- Yes
- No
- Sometimes
- Depends
Q10. What is the key requirement for topological sorting?
- Graph must be connected
- Graph must be acyclic
- Graph must be weighted
- Graph must be complete
💡 Bonus Insight
Topological sorting is also used in task automation pipelines, where job A must finish before job B starts. It’s crucial in build tools like Make, Gradle, and compilers.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!