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.
public List<Integer> topologicalSort(int[][] graph) {
Set<Integer> visited = new HashSet<>();
List<Integer> ordering = new ArrayList<>();
for (int i = 0;
i < graph.length;
i++) {
if (!visited.contains(i)) {
dfs(graph, i, visited, ordering);
}
}
return ordering;
}
public void dfs(int[][] graph, int node, Set<Integer> visited, List<Integer> ordering) {
visited.add(node);
for (int neighbor : graph[node]) {
if (!visited.contains(neighbor)) {
dfs(graph, neighbor, visited, ordering);
}
}
ordering.add(node);
}Follow-up:
How would you handle the case where the graph contains cycles?
