Problem

Given a Directed Acyclic Graph (DAG) of V (0 to V-1) vertices and E edges represented as a 2D list of edges[][], where each entry edges[i] = [u, v] denotes a directed edge u -> v. Return the topological sort for the given graph.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before v in the ordering.

Note: As there are multiple Topological orders possible, you may return any of them. If your returned Topological sort is correct then the output will be true else false.

Examples:

Input: V = 4, E = 3, edges[][] = [[3, 0], [1, 0], [2, 0]]

Output: true
Explanation: The output true denotes that the order is valid. Few valid Topological orders for the given graph are:
[3, 2, 1, 0]
[1, 2, 3, 0]
[2, 3, 1, 0]

Input: V = 6, E = 6, edges[][] = [[1, 3], [2, 3], [4, 1], [4, 0], [5, 0], [5,2]]

Output: true
Explanation: The output true denotes that the order is valid. Few valid Topological orders for the graph are:
[4, 5, 0, 1, 2, 3]
[5, 2, 4, 0, 1, 3]

Constraints:
2 ≤ V ≤ 5 x 10³
1 ≤ E = edges.size() ≤ min[10⁵, (V * (V - 1)) / 2]

Solution

DFS

• If there is an edge from u to v, then u should appear before v in the sorted list.

• We use DFS to create this list.

• The key idea is to traverse the graph, collecting nodes, and then reverse the order at the end.

• Therefore, we store a node only after all its prerequisite nodes are fully visited.

• If we store node x and then move to the next node, some nodes might require x as a prerequisite, which won't work.

• To store the order, we use a stack and pop elements from it at the end to get the correct sorted order.

Time - O(V) + O(E_

Space - O(V)

Stack

class Solution {

    public static ArrayList<Integer> topoSort(int V, int[][] edges) {
        List<List<Integer>> adjList = createAdjList(V, edges);
        int[] visited = new int[V];

        Deque<Integer> stack = new ArrayDeque<>();

        for(int i=0; i<V; i++){
            if(visited[i]!=1){
                dfs(i, adjList, visited, stack);
            }
        }

        return convert(stack);
    }

    private static void dfs(int i, List<List<Integer>> adjList, 
        int[] visited, Deque<Integer>stack){

        if(visited[i]==1) return;

        visited[i] = 1;
        List<Integer> list = adjList.get(i);
        for(int vertex : list){
            dfs(vertex, adjList, visited, stack);
        }

        stack.push(i);
    }

    private static ArrayList<Integer> convert(Deque<Integer> stack){
        int size = stack.size();
        ArrayList<Integer> ans = new ArrayList<>();
        for(int i=0; i<size; i++){
            ans.add(stack.pop());
        }
        return ans;
    }

    private static List<List<Integer>> createAdjList(int V, int[][] edges){
        List<List<Integer>> adjList = new ArrayList<>();

        for(int i=0; i<V; i++){
            adjList.add(new ArrayList<>());
        }

        for(int[] edge : edges){
            adjList.get(edge[0]).add(edge[1]);
        }

        return adjList;
    }
}

List

class Solution {

    public static ArrayList<Integer> topoSort(int V, int[][] edges) {
        List<List<Integer>> adjList = createAdjList(V, edges);
        int[] visited = new int[V];

        ArrayList<Integer> order = new ArrayList<>();

        for(int i=0; i<V; i++){
            if(visited[i]!=1){
                dfs(i, adjList, visited, order);
            }
        }
        return reverse(order);
    }

    private static void dfs(int i, List<List<Integer>> adjList, 
        int[] visited, List<Integer> order){

        if(visited[i]==1) return;

        visited[i] = 1;
        List<Integer> list = adjList.get(i);
        for(int vertex : list){
            dfs(vertex, adjList, visited, order);
        }
        order.add(i);

    }

    private static List<List<Integer>> createAdjList(int V, int[][] edges){
        List<List<Integer>> adjList = new ArrayList<>();

        for(int i=0; i<V; i++){
            adjList.add(new ArrayList<>());
        }

        for(int[] edge : edges){
            adjList.get(edge[0]).add(edge[1]);
        }

        return adjList;
    }

    private static ArrayList<Integer> reverse(List<Integer> order){
        int size = order.size();
        ArrayList<Integer> ans = new ArrayList<>();
        for(int i=0; i<size; i++){
            ans.add(order.get(size-i-1));
        }
        return ans;
    }
}

Kahn's Algorithm (BFS - Indegrees)

• Idea: The main idea is to start with nodes that have an indegree of 0, meaning no other nodes need to be visited before these.

• Steps:

  1. Use a queue to store all nodes with an indegree of 0.

  2. Remove each node from the queue and add it to the sorted list.

  3. For each node removed, delete all outgoing edges from it.

  4. After removing edges, check for new nodes with an indegree of 0.

  5. Add these new nodes to the queue.

  6. Repeat the process until the queue is empty.

Time - O(V) + O(E)

Space - O(V)

class Solution {

    public static ArrayList<Integer> topoSort(int V, int[][] edges) {
        List<List<Integer>> adjList = createAdjList(V, edges);
        int[] visited = new int[V];


        int[] indegrees = createIndegrees(V, edges);

        Queue<Integer> queue = initializeQueue(indegrees);

        ArrayList<Integer> order = new ArrayList<>();
        while(!queue.isEmpty()){
            int vertex = queue.poll();
            order.add(vertex);
            for(int node  : adjList.get(vertex)){
                indegrees[node]-=1;
                if(indegrees[node]==0) queue.add(node);
            }
        }

        return order;
    }

    private static Queue<Integer> initializeQueue(int[] indegrees) {

        Queue<Integer> queue = new ArrayDeque<>();
        for(int i=0; i<indegrees.length; i++){
            if(indegrees[i]==0){
                queue.add(i);
            }
        }

        return queue;

    }

    private static int[] createIndegrees(int V, int[][] edges) {
        int[] indegrees = new int[V];
        for(int[] edge : edges){
            indegrees[edge[1]]+=1;
        }
        return indegrees;
    }


    private static List<List<Integer>> createAdjList(int V, int[][] edges) {
        List<List<Integer>> adjList = new ArrayList<>();

        for(int i=0; i<V; i++){
            adjList.add(new ArrayList<>());
        }

        for(int[] edge : edges){
            adjList.get(edge[0]).add(edge[1]);
        }
        return adjList;
    }

}