Graph - Topological Sort

Algorithms
graph
Catalogue
  1. 1. LintCode 127. Topological Sorting
  2. 2. 210. Course Schedule II
  3. 3. 269. Alien Dictionary
  4. 4. 欧拉通路（Eulerian path

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.
  • 无向图不存在topological sort的问题(无先后关系)
  • 常见topological sort都是用indegree的方法遍历，其实用DFS也可以！
  • key point : 具有依赖关系的任务

LintCode 127. Topological Sorting

  • 解法1. DFS
    • 每次 DFS 得到一个符合正确拓扑顺序的 list，保证单序列顺序；每次新的 DFS 之后得到的 list 要排在之前结果的前面，保证全序列顺序
    • 每次翻转都会改变单序列和全序列之间的顺序，对于每一个单序列或者全序列，两次翻转可以互相抵消
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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的结果！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

  • Build the graph represent the dependency of characters!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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 ""

欧拉通路（Eulerian path

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