Topological Sort
Given a directed acyclic graph (DAG), perform a topological sort on it. A topological sort is an ordering of the vertices in a DAG such that for every directed edge u -> v, vertex u comes before v in the ordering.
Constraints:
- The graph is represented as an adjacency list
- The graph does not contain any cycles
Examples:
Input: [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [0, 1, 2, 3]
Explanation: One possible topological sort of the given graph is [0, 1, 2, 3]. Another possible topological sort is [0, 2, 1, 3].
Solutions
Depth-First Search (DFS)
Time: O(V + E)Space: O(V)
The DFS approach works by visiting each node in the graph and recursively visiting all of its neighbors. Once all neighbors of a node have been visited, the node is added to the ordering. This ensures that for every directed edge u -> v, vertex u comes before v in the ordering.
function topologicalSort(graph) {
const visited = new Set();
const ordering = [];
for (let i = 0; i < graph.length; i++) {
if (!visited.has(i)) {
dfs(graph, i, visited, ordering);
}
}
return ordering;
}
function dfs(graph, node, visited, ordering) {
visited.add(node);
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfs(graph, neighbor, visited, ordering);
}
}
ordering.push(node);
}
Follow-up:
How would you handle the case where the graph contains cycles?
