Topological Sort

Given an directed graph, a topological order of the graph nodes is defined as follow:

1. For each directed edge A -> B in graph, A must before B in the order list.

2. The first node in the order can be any node in the graph with no nodes direct to it.

3. 无向图不存在topological sort的问题(无先后关系)

4. 常见topological sort都是用indegree的方法遍历，其实用DFS也可以！
5. key point : 具有依赖关系的任务

LintCode 127. Topological Sorting

• 解法1. DFS
  • 每次 DFS 得到一个符合正确拓扑顺序的 list，保证单序列顺序；每次新的 DFS 之后得到的 list 要排在之前结果的前面，保证全序列顺序
  • 每次翻转都会改变单序列和全序列之间的顺序，对于每一个单序列或者全序列，两次翻转可以互相抵消

class Solution:
    def topSort(self, graph):
        visited = set()
        ans = []

        for root in graph:
            self.dfs(root, visited, ans)

        return ans[::-1]

    def dfs(self, root, visited, ans):
        if root in visited:
            return

        for nei in root.neighbors:
            if nei not in visited:
                self.dfs(nei, visited, ans)

        visited.add(root)
        ans.append(root)

• 解法2. BFS
  • step1. 统计每个vertex/node的indegree
  • step2. 从indegree==0开始放入queue，有edge的indegree-1，为0的放入queue

class Solution:
    def topSort(self, graph):
        indegree = collections.defaultdict(int)
        for node in graph:
            for nei in node.neighbors:
                indegree[nei] += 1

        queue = collections.deque([])
        for node in graph:
            if node not in indegree:
                queue.append(node)

        res = []
        while queue:
            node = queue.popleft()
            res.append(node)
            for nei in node.neighbors:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return res

210. Course Schedule II

首先要检查有没有环，没有环的话才有topological sort的结果！

class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        indegree = [0] * numCourses
        graph = collections.defaultdict(list)
        for u, v in prerequisites:
            indegree[u] += 1
            graph[v].append(u)

        queue = collections.deque([i for i in xrange(numCourses) if indegree[i] == 0])
        res = []
        while queue:
            node = queue.popleft()
            res.append(node)
            for v in graph[node]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)
        return res if sum(indegree) == 0 else []

269. Alien Dictionary

字母的顺序有个先后关系可以构成一个图，而拓扑排序的结果是前后关系正好满足前面的先后关系！

class Solution(object):
    def alienOrder(self, words):
        indegree = {}
        for word in words:
            for c in word:
                indegree[c] = 0

        graph = [set() for _ in xrange(26)]
        for i in xrange(len(words)-1):
            cur = words[i]
            next = words[i+1]
            for j in xrange(min(len(cur), len(next))):
                if cur[j] != next[j]:
                    if next[j] not in graph[ord(cur[j])-ord('a')]:
                        graph[ord(cur[j])-ord('a')].add(next[j])
                        indegree[next[j]] += 1
                    break

        res = []
        cnt = len(indegree.keys())
        q = collections.deque([c for c in indegree.keys() if indegree[c] == 0])
        while q:
            cur = q.popleft()
            res.append(cur)
            for n in list(graph[ord(cur)-ord('a')]):
                indegree[n] -= 1
                if indegree[n] == 0:
                    q.append(n)
        return ''.join(res) if len(res) == cnt else ""

332. Reconstruct Itinerary

• 解法. DFS
  • 有点类似用DFS来写topological sort的方法！
  • DFS后根遍历，然后再reverse结果！！！

class Solution(object):
    def findItinerary(self, tickets):
        graph = collections.defaultdict(list)
        for f, t in sorted(tickets, reverse = True):
            graph[f].append(t)

        res = []
        def dfs(node):
            while graph[node]:
                dfs(graph[node].pop())
            res.append(node)
        dfs('JFK')
        return res[::-1]

• 欧拉通路（Eulerian path）
  • 若一个图为欧拉图或半欧拉图都可以通过一笔画遍历。通过图（有向图或无向图）中的所有边且每一条边仅通过一次的通路称为欧拉通路，若此通路为回路则称为欧拉回路
  • 每次深度优先搜索的结果必然是图的一个连通分量。深度优先搜索可以从多点发起。如果将每个节点在深度优先搜索过程中的“结束时间”排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下，将该节点加入list结尾，然后逆转整个链表),则我们可以得到所谓的“拓扑排序”，即topological sort.