Topological Sort - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series

---

Topological Sort

• put indegree=0 into queue
• works only in DAG(Acyclic, no cycle)
• BFS
• Add the node whose in-degree is 0 into queue
• Answer: length of Topological sort may be the result - longest path
• Add the node whose out-degree is 0 into queue

When to use

• order, sort
• boundary: input degree: 0

Examples

• LeetCode 329 - Longest Increasing Path in a Matrix
  • dfs + cache: O(mn)
  • Topological Sort: BFS
    • matrix to graph, only need indegrees[][]; no need to create graph map

    public int longestIncreasingPath(int[][] matrix) {
    int m = matrix.length; n = matrix[0].length;
    int[][] indegree = new int[m][n];
    Queue<int[]> q = new LinkedList();
    for (int row = 0; row < m; row++) {
        for (int col = 0; col < n; col++) {
            for(int i = 0; i < 4; i++) {
                int nextRow = row + dirs[i][0];
                int nextCol = col + dirs[i][1];
                if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n &&
                    matrix[row][col] > matrix[nextRow][nextCol]) {
                    indegree[row][col]++;
                }
            }
            if (indegree[row][col] == 0) q.offer(new int[]{row, col});
        }
    }
    int len = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        while (size-- > 0) { // consume all nodes in cur layer and add next layer into queue
            int[] coord = q.poll();
            int row = coord[0], col = coord[1];
            for(int i = 0; i < 4; i++) {
                int nextRow = row + dirs[i][0];
                int nextCol = col + dirs[i][1];
                if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n &&
                    matrix[row][col] < matrix[nextRow][nextCol]) {
                    if (--indegree[nextRow][nextCol] == 0)     // remove edge
                        q.offer(new int[]{nextRow, nextCol});  // add as next level node
                }
            }
        }
        len++; // at the end of each layer, increase the length
    }
    return len;
    }

• LeetCode 207- Course Schedule
• LeetCode 210 - Course Schedule II
• LeetCode 269 - Alien Dictionary
• Find Itinerary from a given list of tickets
• Detect Cycle in a Directed Graph
• LeetCode 802 - Find Eventual Safe States
  • Topological sort
  • dfs: color[i] = 0 means node i is not visited; color[i] = 1 means node i is visiting; color[i] = 2 means node i has been already visited
    • when color[i] = 1 and it is visited again; then detect cycle
  • reverse graph
• Preference list - Airbnb