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

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

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
2. Course Schedule II
3. Alien Dictionary
4. Sequence Reconstruction