What is Topological Sort?

Topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. It is only possible for Directed Acyclic Graphs (DAGs).

What are the main algorithms for Topological Sort?

The two main algorithms are Kahn's algorithm, which is based on in-degrees of vertices, and a depth-first search (DFS) based approach. Kahn's algorithm is often preferred for its intuitive approach of processing nodes with no incoming dependencies.

Graph Algorithms

Topological Sort

Linearly order the vertices of a Directed Acyclic Graph (DAG), essential for scheduling tasks with dependencies.

Kahn's Algorithm for Topological Sort

This implementation uses Kahn's algorithm, which iteratively finds nodes with an in-degree of 0, adds them to the sorted list, and removes their outgoing edges.

                            function topologicalSort(numCourses, prerequisites) {
                            const inDegree = new Array(numCourses).fill(0);
                            const adjList = inDegree.map(() => []);
                            
                            for (const [course, prereq] of prerequisites) {
                            adjList[prereq].push(course);
                            inDegree[course]++;
                            }
                            
                            const queue = [];
                            for (let i = 0; i < numCourses; i++) {
                            if (inDegree[i] === 0) queue.push(i);
                            }
                            
                            const result = [];
                            while (queue.length) {
                            const course = queue.shift();
                            result.push(course);
                            for (const nextCourse of adjList[course]) {
                            inDegree[nextCourse]--;
                            if (inDegree[nextCourse] === 0) queue.push(nextCourse);
                            }
                            }
                            
                            return result.length === numCourses ? result : []; // Return empty if cycle detected
                            }
                        

AI Coach Hint: A key feature of Topological Sort is cycle detection. If the final sorted list doesn't contain all the vertices, it means the graph has at least one cycle, and a valid topological ordering is impossible. This is a common follow-up question in interviews.