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.
vector<int> topologicalSort(vector<vector<int>>& graph) {
unordered_set<int> visited;
vector<int> ordering;
for (int i = 0;
i < graph.size();
i++) {
if (visited.find(i) == visited.end()) {
dfs(graph, i, visited, ordering);
}
}
return ordering;
}
void dfs(vector<vector<int>>& graph, int node, unordered_set<int>& visited, vector<int>& ordering) {
visited.insert(node);
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
dfs(graph, neighbor, visited, ordering);
}
}
ordering.push_back(node);
}Follow-up:
How would you handle the case where the graph contains cycles?
