Topological sort

Topological sort 有很多实现方式比如维基上就列举了2种。这里我们分别实现一下吧。 https://en.wikipedia.org/wiki/Topological_sorting

1 Kahn's algorithm （push node到stack前，先检查是否已visit了所有parent）

这里我们先实现第一种Kahn's algorithm。我也不知道怎么发音，就叫他“看”算法好了。主要思想是maintain两个dict。一个是indegree一个是outdegree。只有一个node所有的indegree都被visit过了，我们才把这个node加到stack里面去。这样就能保证visit一个node的时候，在他之前的node全部都visit过了（这不就是toposort要做的事情么）。如果最后不能遍历所有的node的话，那么这个图就是有circle的，这里有点绕。因为带circle的图，node之间互为indegree，永远不可能visit这个node全部的indegree。

实现方法是，开始先找所有没有indegree的node，来init一个stack，然后pop一个node出来，然后对他的所有child的indegree移除这个parent。如果移除这个node后的child已经没有indegree了，那么就把这个child push到stack里面。

import collections
class Solution(object):
    def toposort(self, graph):
        """
        :type graph: dict[int:List[int]]
        :rtype: List[int]
        """
        indegree = collections.defaultdict(set)
        outdegree = graph

        # init the stack
        for key in outdegree:
            for c in outdegree[key]:
                indegree[c].add(key)
        stack = [k for k in outdegree if k not in indegree]

        # dfs
        res = []
        while stack:
            tmp = stack.pop()
            res.append(tmp)
            if tmp in outdegree:
                children = outdegree[tmp]
                for c in children:       # remove tmp for all the child
                    indegree[c].remove(tmp)
                    if not indegree[c]:  # if any child's all parents are visited
                        stack.append(c)  # add this child to stack

        node = set([k for k in outdegree] + [k for k in indegree])

        return res if len(node)==len(res) else []

graph = {1:[2,3,4,5],
        2:[3,4],
        3:[5]}
so = Solution()
a = so.toposort(graph)
print a

2 DFS （找一条path一路走到黑，边走边检查是否circle，走到底就把最后node存起来。）

第二种实现方式是DFS。我偷的我女朋友的代码。主要思想是DFS。开始也是一样的，抬手先找所有没有indegree的node，来init一个stack。然后从stack最后的node开始，找一条path一直走到底，中间不断检查新的node时候在stack里面（即有没有circle）。走到底后，我们就pop出最后这个node，把他存到result里面。

class Solution(object):
    def toposort(self, graph):
        """
        :type graph: dict[int:List[int]]
        :rtype: List[int]
        """
        children = []
        for k in graph:
            children += graph[k]
        # find starting points
        stack  = [k for k in graph if k not in set(children)]

        res=[]
        while stack:
            while stack[-1] in graph and graph[stack[-1]]: # keep dig further
                tmp=graph[stack[-1]].pop()    
                if tmp not in stack:   # check if node in path 
                    stack.append(tmp)       
                else:                  # if it in the coming path, we find a circle
                    return []          # return []
            tmp=stack.pop()        # finish one path, pop last node
            if tmp not in res:    
                res.append(tmp)
        return res

graph = {1:[2,3,4,5],
        2:[3,4],
        3:[5]}
so = Solution()
a = so.toposort(graph)
print a

比较：第一种实现方式，我们一开始要建立一个indegree的dict。所以比较耗费空间，后面因为都是hash操作，所以时间复杂度很不错呀。第二种方式，因为不停要检查新的node在不在stack里面，这个操作是O（k）,k是stack的长度。所以我只能理解为，这个时间复杂度比较高。所以两种算法的复杂度tradeoff在时间和空间上。（不一定对哈）

温故而知新，不如我们用topological sort来做道题把。

269 Alien Dictionary https://leetcode.com/problems/alien-dictionary/

import collections
class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        greater = collections.defaultdict(set)
        less = collections.defaultdict(set)

        for i in range(len(words)-1):
            pre = words[i]
            cur = words[i+1]
            index=0
            while index<min(len(pre), len(cur)) and cur[index]==pre[index]:
                index += 1
            if index<min(len(pre), len(cur)):
                greater[pre[index]].add(cur[index])
                less[cur[index]].add(pre[index])

        chars = set(''.join(words))
        s = [ i for i in chars if i not in less]

        res = []
        while s:
            tmp = s.pop()
            res.append(tmp)
            children = greater[tmp]
            for c in children:
                less[c].remove(tmp)
                if not less[c]:
                    s.append(c)

        if len(chars) == len(res):
            return ''.join(res)
        return []


words = [ "wrt", "wrf", "er", "ett", "rftt"]
so = Solution()
a = so.alienOrder(words)
print a