動機

topo sort的重點是怎麼從對的點開始加，像是dfs就要特別注意，不像bfs會有in_degree確認，dfs就是走，什麼都不管

DFS

從*終點(沒有到其他node的edge)*開始往後走，最後的結果要reverse，因為是從終點開始放

另外會有個table去放，node是處理完畢還是處理中的狀態

    def topologicalSortUtil(self, v, visited, stack):
        if visited[v] == 1:
          raise 'loop'
        elif visited[v] == 2:
          return
        visited[v] = 1
        for i in self.graph[v]:
            if visited[i] == False:
                self.topologicalSortUtil(i, visited, stack)
        stack.append(v)
        visited[v] = 2
 
    def topologicalSort(self):
        visited = [0]*self.V
        stack = []
 
        for i in range(self.V):
            if visited[i] == 0:
                self.topologicalSortUtil(i, visited, stack)

        print(stack[::-1])  # return list in reverse order

BFS (Kahn’s algorithm)

從*起點(沒有其他node指到他)*開始往前走，因為要看被多少node指到，所以一個table要另外算 之後就是一直找沒有被指到的邊緣node，加到結果

這裡處理loop就是看bfs結束時是不是所有node都有加到結果，因為loop一定會指到，所以不會被bfs當成邊緣node

    def topologicalSort(self):
        in_degree = [0]*(self.V)
         
        for i in self.graph:
            for j in self.graph[i]:
                in_degree[j] += 1
 
        queue = [queue.append(i) for i in range(self.V) if in_degree[i] == 0]
 
        cnt = 0
        top_order = []
        while queue:
            u = queue.pop(0)
            top_order.append(u)

            for i in self.graph[u]:
                in_degree[i] -= 1
                if in_degree[i] == 0:
                    queue.append(i)
 
            cnt += 1
 
        if cnt != self.V:
            print "There exists a cycle in the graph"
        else :
            print top_order