# Topological Sorting

## Topological Sorting

## 1. Basics

### (1) Topological Sorting By Breath First Search (Kahn's Algorithm)

#### Idea:

1. **Create adjacent list for the graph**
2. **Calculate the inDegree for each node**
3. **Start with node with 0 inDegree and do BFS for its neighbor**
4. **Everytime we visit a node, we decrement the inDegree of it by 1, if the inDegree turns to 0, we add the node to queue**

```java
import java.util.*;

   public static void topologicalSortByBFS(int nodes, int[][] edges) {
        List<List<Integer>> adjList = new ArrayList<>();
        List<Integer> topologicalSortOrder = new ArrayList<>();

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

        int[] inDegree = new int[nodes];

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

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int curNode = queue.remove();

            ++count;
            topologicalSortOrder.add(curNode);

            for (int nextNode : adjList.get(curNode)) {
                if (--inDegree[nextNode] == 0) {
                    queue.add(nextNode);
                }
            }
        }

        if (count != nodes) {
            System.out.println("Cycle is detected, can not implement topological sort");
        }
        else {
            printTopologicalSortOrder(topologicalSortOrder);
        }
    }

    public static void printTopologicalSortOrder(List<Integer> list) {
        System.out.println("Topological Sort: ");
        for (int order : list) {
            System.out.print(order + " ");
        }
    }

    public static void main(String[] args) {
       int nodes = 6;
       int[][] edges = {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}};
       topologicalSortByBFS(nodes, edges);
    }
```

### (2) Topological Sorting By Depth First Search

ideas:

1. **Create adjacent list for the graph**
2. **Maintain two boolean array visited and visiting, where visited mean a node has been visited from a path in dfs, while visiting means a node is being visited in the dfs**
3. **If the visiting value for a node is true, this means a loop is found**
4. **If the visited value for a node is true, this means we have visited this node, we can skip it**

```java
import java.util.*;

   public static void topologicalSortByDFS(int nodes, int[][] edges) {
        List<List<Integer>> adjList = new ArrayList<>();
        List<Integer> topologicalSortOrder = new ArrayList<>();

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

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

        boolean[] visited = new boolean[nodes];
        boolean[] visiting = new boolean[nodes];

        for (int i = 0; i < nodes; i++) {
            if (!dfs(i, visited, visiting, adjList, topologicalSortOrder)) {
                System.out.println("Cycle is detected, can not implement topological sort");
                return;
            }
        }

        printTopologicalSortOrder(topologicalSortOrder);
    }

    public static boolean dfs(int curNode, boolean[] visited, boolean[] visiting, List<List<Integer>> adjList, List<Integer> topologicalSortOrder) {
        // if curNode has been visited (added to the result), we skip it
        if (visited[curNode]) {
            return true;
        }

        // Found loop in the current DFS
        if (visiting[curNode]) {
            return false;
        }

        visiting[curNode] = true;
        for (int nextNode : adjList.get(curNode)) {
            if (!dfs(nextNode, visited, visiting, adjList, topologicalSortOrder)) {
                return false;
            }
        }
        visited[curNode] = true;
        topologicalSortOrder.add(0, curNode);
        return true;
    }

    public static void printTopologicalSortOrder(List<Integer> list) {
        System.out.println("Topological Sort: ");
        for (int order : list) {
            System.out.print(order + " ");
        }
    }

    public static void main(String[] args) {
        int nodes = 6;
        int[][] edges = {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}};
        topologicalSortByDFS(nodes, edges);
    }
```

## 2. Thoughts

1. Q:What if the input is not integer, but rather character or string,  what data structure should we use to build up adjacent list and inDegree?

   A: Use hashmap, for example, if the input is character, then Adjacent list: **Map\<Character, Set\<Character>>**, inDegree: **Map\<Character, Integer>**
2. Q: Time Complexity for Topological Sort:

   A: **O(n + e)**, where n is the number of nodes and e is the number of edges

## 3. Interview Questions

1. [Course Schedule](https://leetcode.com/problems/course-schedule/)
2. [Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)
3. [Alien Dictionary](https://leetcode.com/problems/alien-dictionary/)
4. [Sequence Reconstruction](https://leetcode.com/problems/sequence-reconstruction/)