拓扑排序（Topological Sort）是针对有向无环图（DAG）的一种排序方式，使得在图中uv路径为从u到v的排序结果中，u始终出现在v前面。
比如说，学功课C需要先学其前置课程A或者B，那么若把功课ABC用图表示，然后进行拓扑排序，可以表示成为ABC或者BAC，总之C不能出现在A或者B的前面。由此可知，很多时候拓扑排序不止一个结果。一般而言，只需要一个结果就够了。
假设图有V个顶点（vetex）和E条边（edge），那么拓扑排序的时间和空间复杂度均为O（|V|+|E|）。
拓扑排序一般有两种方法，即BFS和DFS方法。
- BFS
拓扑排序的BFS方法，步骤如下：
I.遍历图，计算每个节点的入度（in order/degree），所谓入度，就是有几个其他节点有进入这个节点的边。很明显，入度为0的节点，没有前驱节点，因此在拓扑排序里面应该放在最前面。假如有好几个这种0入度的顶点，它们的顺序是无所谓的。这里把它们放入队列，同时也放入结果数组。
II.逐个删除队列里的0入度点，然后对于和其相连的顶点，入度-1。其实就相当于把这些顶点从图上面删掉。
III.再次检查图，把新的0入度的点加入队列和结果。
IV.重复以上过程，直至图为空。
可以看到，BFS方法就相当于每次把最外层的顶点给去除，一层一层剥下来。代码：
class DirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
from collections import deque
class Solution:
def topBFS(self, graph):
countrd = {}
for x in graph:
countrd[x] = 0
for i in graph:
for j in i.neighbors:
countrd[j] = countrd[j] + 1
ans = []
zeroDegree = deque()
for i in graph:
if countrd[i] == 0:
ans.append(i)
zeroDegree.append(i)
while zeroDegree:
i = zeroDegree.pop()
countrd[i] -= 1
for n in i.neighbors:
countrd[n] -= 1
if countrd[n] == 0:
ans.append(n)
zeroDegree.appendleft(n)
return ans
2.DFS
DFS其实和BFS有相似的地方，也是围绕入度来实现，只不过是先一条线到底：
class DirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
class Solution:
def dfs(self, i, countrd, ans):
ans.append(i)
countrd[i] -= 1
for j in i.neighbors:
countrd[j] = countrd[j] - 1
if countrd[j] == 0:
self.dfs(j, countrd, ans)
"""
@param graph: A list of Directedgraph node
@return: A list of integer
"""
def topSort(self, graph):
# writeyour code here
countrd= {}
for x in graph:
countrd[x] = 0
for i in graph:
for j in i.neighbors:
countrd[j] = countrd[j] +1
ans = []
for i in graph:
if countrd[i] == 0:
self.dfs(i, countrd, ans)
return ans
来看看实际应用：
1.选课问题I。假设有n门课要上，序号从0到n-1，假设用数组对来表示前置课程，例如用[0,1]来表示1是0的前置课程。现在给出n和前置课程对的数组，返回是否能够完成课程。
【解】相当于给出n个顶点的图和其边的信息，问是否能够对其进行拓扑排序。很明显关键就在于有没有环。
无论如何，第一步还是建立图的结构。因为没有直接给出neighbor信息，若再刻意地先求neighbor再按照之前的算法计算入度，就有点生硬。
其实，换一个做法，把边的信息分别存到入度表和出度表，效果还是一样的。之后还是按照正常的拓扑排序做法，只不过这里是把入度表为空的节点的出度表里的节点的入度表里的对应节点给删除。假设A是最外层的顶点，有AB这条边，那么B在A的出度表上，A在B的入度表上，因此要删除A，通过A的出度表找到B，然后再看B的入度表，把里面的A删掉。
如果有环，最后出度表会删不完全。因为环里面的元素天生不可能入度为空，那么自然不会从环上的节点开始，而从其他节点开始之后，删除到环，但环上的节点入度除了连接的非环节点以外，自然还是有环上的其他节点，因此怎么着也不会是空，所以就没法删除。
import collections
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
zero_in_degree_queue, in_degree, out_degree = collections.deque(), {}, {}
for i, j in prerequisites:
if i not in in_degree:
in_degree[i] = set()
if j not in out_degree:
out_degree[j] = set()
in_degree[i].add(j)
out_degree[j].add(i)
for i in range(numCourses):
if i not in in_degree:
zero_in_degree_queue.append(i)
while zero_in_degree_queue:
prerequisite = zero_in_degree_queue.popleft()
if prerequisite in out_degree:
for course in out_degree[prerequisite]:
in_degree[course].discard(prerequisite)
if not in_degree[course]:
zero_in_degree_queue.append(course)
del out_degree[prerequisite]
if out_degree:
return False
return True
2.选课问题II。接上题，返回拓扑排序的任意一个结果，假如没有，返回空数组。
【解】相似度99%，多加一个结果数组，把零入度的节点放进去即可。代码略。
3.外文字典。现在有一种新的外语，也用英文字母，但是顺序不一样。现在给出一组这种外文的单词，已经按照字典序排列，返回该外文的字母顺序。例如，给出[wrt,wrf,er,ett,rftt]，返回wertf。假如有多个可能顺序，返回任一个即可。
【解】还是拓扑排序，只不过这次有多个对象，如何转化是一个关键问题。
容易犯的错误是把单词之间的字典序当做单词内的字母序，如果不仔细看例子，就会搞错。单词内不一定是按照字典序排列的，比如rftt，f就在t之前，题目只是说单词按照字典序排列而已。
也就是说，字母的顺序是在单词之间体现出来的，可以用这一点来比较相邻两个单词的字母，从而建立图。为什么不循环比较？没必要，两两比较已经够了。每次比较只能得出一个顺序，拿英文单词举例，az在bc之前，因此只能看出a<b，不能再看出z和c的大小。
例子当中，比较12，得出t<f，然后23，可知w<e，34知道r<t，45知道e<r，因此w<e<r<t<f。
之后的处理就还是老套路了，注意判断有没有环。代码如下：
# T: O(n) S:O(|V|+|E|)=O(1) 因为只有26个字母
import collections
# BFS solution.
class Solution(object):
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
result, zero_in_degree_queue, in_degree, out_degree = [], collections.deque(), {}, {}
nodes = set()
for word in words:
for c in word:
nodes.add(c)
for i in range(1, len(words)):
self.findEdges(words[i - 1], words[i], in_degree, out_degree)
for node in nodes:
if node not in in_degree:
zero_in_degree_queue.append(node)
while zero_in_degree_queue:
precedence = zero_in_degree_queue.popleft()
result.append(precedence)
if precedence in out_degree:
for c in out_degree[precedence]:
in_degree[c].discard(precedence)
if not in_degree[c]:
zero_in_degree_queue.append(c)
del out_degree[precedence]
if out_degree:
return ""
return "".join(result)
# Construct the graph.
def findEdges(self, word1, word2, in_degree, out_degree):
str_len = min(len(word1), len(word2))
for i in range(str_len):
if word1[i] != word2[i]:
if word2[i] not in in_degree:
in_degree[word2[i]] = set()
if word1[i] not in out_degree:
out_degree[word1[i]] = set()
in_degree[word2[i]].add(word1[i])
out_degree[word1[i]].add(word2[i])
break
网友评论