DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master topological sort for DAGs using both Kahn\
What is Topological Sort?
A topological sort of a Directed Acyclic Graph (DAG) is a linear ordering of all vertices such that for every directed edge u→v, vertex u comes before v in the ordering. Think of it as scheduling tasks where some tasks depend on others — you need to find an order that respects all dependencies.
Critical requirement: Topological sort only works on DAGs. If the graph has a cycle, no valid ordering exists (you cannot satisfy circular dependencies).
Real-World Analogy
Consider getting dressed in the morning:
- Underwear must come before pants
- Pants must come before belt
- Shirt must come before belt
- Socks must come before shoes
- Pants must come before shoes
| Underwear | Pants → Belt |
| Shirt ------ | Belt Shoes |
| Pants ──────── | ┘ |
One valid topological order: Underwear, Pants, Shirt, Belt, Socks, Shoes Another valid order: Socks, Underwear, Pants, Shirt, Belt, Shoes
Multiple valid orderings can exist!
Approach 1: Kahn\'s Algorithm (BFS-based)
The idea: repeatedly remove vertices with no incoming edges (in-degree = 0).
Example
1. Compute in-degree for all vertices
2. Add all vertices with in-degree 0 to a queue
3. While queue is not empty:
a. Dequeue vertex u, add to result
b. For each neighbor v of u:
Decrement in-degree of v
If in-degree of v becomes 0, enqueue v
4. If result has fewer than V vertices → cycle exists!
Why It Works
A vertex with in-degree 0 has no prerequisites — it is safe to place first. After "removing" it, new vertices may become prerequisite-free. This greedy process produces a valid topological ordering.
Dry Run
| Graph: 5 | 0, 5→2, 4→0, 4→1, 2→3, 3→1 |
| In-degrees | 0:2, 1:2, 2:1, 3:1, 4:0, 5:0 |
| Queue | [4, 5] (in-degree 0) |
| Process 4: reduce in-degree of 0( | 1) and 1(→1). Queue: [5] |
| Process 5: reduce in-degree of 0( | 0) and 2(→0). Queue: [0, 2] |
| Process 0 | no outgoing. Queue: [2] |
| Process 2: reduce in-degree of 3( | 0). Queue: [3] |
| Process 3: reduce in-degree of 1( | 0). Queue: [1] |
| Process 1 | no outgoing. Queue: [] |
| Result | [4, 5, 0, 2, 3, 1] ✓ |
Approach 2: DFS-based Topological Sort
The idea: perform DFS, and add each vertex to the result AFTER all its descendants are processed (post-order). Then reverse the result.
Example
1. Run DFS from each unvisited vertex
2. When DFS finishes processing a vertex (all neighbors explored),
push it onto a stack
3. Pop all from stack → topological order
Why It Works
In DFS, a vertex is finished only after all vertices reachable from it are finished. So if u→v exists, v finishes before u. Reversing the finish order gives us u before v — exactly what we need.
Python Implementation
Example
from collections import deque
def topological_sort_kahn(graph, num_vertices):
"""Kahn's Algorithm (BFS-based)."""
in_degree = [0] * num_vertices
for u in range(num_vertices):
for v in graph[u]:
in_degree[v] += 1
queue = deque([v for v in range(num_vertices) if in_degree[v] == 0])
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(result) != num_vertices:
return None # Cycle detected!
return result
def topological_sort_dfs(graph, num_vertices):
"""DFS-based topological sort."""
visited = [False] * num_vertices
stack = []
def dfs(u):
visited[u] = True
for v in graph[u]:
if not visited[v]:
dfs(v)
stack.append(u) # Add after all descendants processed
for i in range(num_vertices):
if not visited[i]:
dfs(i)
return stack[::-1] # Reverse of post-order
# Example
graph = {
0: [], 1: [], 2: [3], 3: [1], 4: [0, 1], 5: [0, 2]
}
print(topological_sort_kahn(graph, 6)) # [4, 5, 0, 2, 3, 1]
print(topological_sort_dfs(graph, 6)) # [5, 4, 2, 3, 1, 0]
C++ Implementation
Example
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> kahnTopSort(vector<vector<int>>& graph, int V) {
vector<int> inDegree(V, 0);
for (int u = 0; u < V; u++)
for (int v : graph[u])
inDegree[v]++;
queue<int> q;
for (int i = 0; i < V; i++)
if (inDegree[i] == 0) q.push(i);
vector<int> result;
while (!q.empty()) {
int u = q.front(); q.pop();
result.push_back(u);
for (int v : graph[u])
if (--inDegree[v] == 0) q.push(v);
}
return result.size() == V ? result : vector<int>{}; // Empty = cycle
}
Time and Space Complexity
- Time: O(V + E) for both approaches — each vertex and edge processed once
- Space: O(V) for in-degree array / visited set + O(V) for queue/stack
Cycle Detection as a Bonus
Both approaches naturally detect cycles:
- Kahn's: If result has fewer than V vertices, remaining vertices are in a cycle
- DFS: Use three-color marking (WHITE/GRAY/BLACK). If DFS encounters a GRAY vertex, a cycle exists.
Applications
- Build systems (Make, Gradle): Compile files in dependency order
- Course scheduling: Prerequisites must be completed before a course
- Package managers: Install dependencies before dependent packages
- Spreadsheet evaluation: Compute cells in dependency order
- Task scheduling: Order tasks respecting dependencies
- Compilation: Order function definitions before usage in single-pass compilers
Kahn\'s vs DFS Approach
| Feature | Kahn\'s (BFS) | DFS |
|---|---|---|
| Cycle detection | Count vertices in result | Gray vertex revisited |
| Lexicographic order | Easy (use min-heap instead of queue) | Harder |
| Implementation | Slightly more code | Simpler recursive |
| All topological orders | Possible with backtracking | Possible with backtracking |
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Topological Sorting.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, graphs, topological, sorting
Related Data Structures & Algorithms Topics
Continue learning this concept
GraphsBellman-Ford AlgorithmLearn Bellman-Ford shortest path algorithm that handles negative edge weights, detects negative cycles, with complete implementation and analysis.GraphsBreadth-First Search (BFS) AlgorithmLearn BFS traversal with queue-based implementation, level-order processing, shortest path in unweighted graphs, and real applications.GraphsDepth-First Search (DFS) AlgorithmMaster DFS traversal using recursion and stack, understand pre/post ordering, cycle detection, and connected component discovery.GraphsDijkstra\Master Dijkstra\GraphsFloyd-Warshall AlgorithmMaster the all-pairs shortest path algorithm using dynamic programming with three nested loops, path reconstruction, and practical applications.GraphsGraph Interview ProblemsMaster 12 essential graph interview problems with clear approaches, patterns, and solutions for coding interviews at top tech companies.