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.
def topological_sort(graph):
visited = set()
ordering = []
for i in range(len(graph)):
if i not in visited:
dfs(graph, i, visited, ordering)
return ordering
def dfs(graph, node, visited, ordering):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited, ordering)
ordering.append(node)Follow-up:
How would you handle the case where the graph contains cycles?
