Topology Sort

Topology Sort

1. BFS

   1. Use Map to store the flowing times of each node

   2. Use Queue to store the initial node of graph

   3. A node is added when its all sources are traversed

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */

public class Solution {
    /*
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        Map<DirectedGraphNode, Integer> map = new HashMap<>();

        // Count the flow in number of each node 
        for (DirectedGraphNode node: graph){
            for (DirectedGraphNode neighbor: node.neighbors){
                map.put(neighbor, map.getOrDefault(neighbor, 0) + 1);
            }
        }

        ArrayList<DirectedGraphNode> ans = new ArrayList<>();
        Queue<DirectedGraphNode> queue = new LinkedList<>();
        // Find the heads of graph
        for (DirectedGraphNode node: graph){
            if (!map.containsKey(node)){
                queue.add(node);
                ans.add(node);
            }
        }

        // start to put node to ans
        while(!queue.isEmpty()){
            DirectedGraphNode curNode = queue.poll();
            for (DirectedGraphNode node: curNode.neighbors){
                map.put(node , map.get(node) - 1);
                if (map.get(node) == 0){
                   queue.add(node);
                   ans.add(node);
                }
            }
        }
        return ans;
    }
}

1. DFS

   1. Use map to record the flowing in times of each node

   2. Find out the initial node of graph and put them into stack

   3. A boolean array to record "traversed"

   4. Use dfs and a stack to push leaf node first, parent node last

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        Map<DirectedGraphNode, Integer> map = new HashMap<>();

        // Count the flow in number of each node 
        for (DirectedGraphNode node: graph){
            for (DirectedGraphNode neighbor: node.neighbors){
                map.put(neighbor, map.getOrDefault(neighbor, 0) + 1);
            }
        }

        ArrayList<DirectedGraphNode> ans = new ArrayList<>();
        Stack<DirectedGraphNode> stack = new Stack<>();
        boolean[] traversed = new boolean[graph.size()];

        for (DirectedGraphNode node: graph){
            if (!map.containsKey(node)){
                dfs(stack, traversed, node);
            }
        }

        while(!stack.isEmpty()){
            ans.add(stack.pop());
        }

        return ans;
    }

    private void dfs(Stack<DirectedGraphNode> stack, boolean[] traversed, DirectedGraphNode node){
        traversed[node.label] = true;
        for (DirectedGraphNode neighbor: node.neighbors){
            if (traversed[neighbor.label] == false){
                dfs(stack, traversed, neighbor);
            }
        }
        stack.push(node);
    }

210 Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

from collections import defaultdict
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = defaultdict(set)
        degree = defaultdict(int)
        
        for c1, c2 in prerequisites:
            graph[c2].add(c1)
            degree[c1]+=1    
        
        q = []
        ans = []
        for i in range(numCourses):
            if i not in degree:
                q.append(i)
                
        while q:
            c = q.pop(0)
            ans.append(c)
            for nei in graph[c]:
                degree[nei]-=1
                if degree[nei] == 0:
                    q.append(nei)
                    
        return ans if len(ans) == numCourses else []

269 Alien Dictionary

E.g.

Input:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

Output: "wertf"

• 1. Similar to topology sort, 但比較對象變成word to word 第一個發生變化的char

  2. 若char已經比較過則不允許增加degree，注意 if condition 後break的時機

from collections import defaultdict
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = defaultdict(set)
        degree = defaultdict(int)
        
        for word in words:
            for ch in word:
                graph[ch] = set()
           
        for i in range(1, len(words)):
            pre = words[i-1]
            cur = words[i]
            size = min(len(pre), len(cur))
            getOrder = False
            for j in range(size):
                c1 = pre[j]
                c2 = cur[j]
                if c1 != c2:
                    getOrder = True
                    if c2 not in graph[c1]:
                        graph[c1].add(c2)
                        degree[c2] += 1
                    break
                    
            # invalid  ['abc', 'ab']
            if not getOrder and len(pre) > len(cur):
                return ''          
        
        q = []
        for k in graph.keys():
            if k not in degree:
                q.append(k)

                
        build = ''
        
        while q:
            w = q.pop(0)
            build += w
            for nxt in graph[w]:
                degree[nxt] -= 1
                if degree[nxt] == 0:
                    q.append(nxt)
        print(build)
        return build if len(build) == len(graph) else ''