拓?fù)渑判颍═opological Sort）是針對(duì)有向無(wú)環(huán)圖（DAG）的一種排序方式堂鲜，使得在圖中uv路徑為從u到v的排序結(jié)果中，u始終出現(xiàn)在v前面。
比如說(shuō)散休，學(xué)功課C需要先學(xué)其前置課程A或者B，那么若把功課ABC用圖表示乐尊，然后進(jìn)行拓?fù)渑判蚱萃瑁梢员硎境蔀锳BC或者BAC，總之C不能出現(xiàn)在A或者B的前面。由此可知限府，很多時(shí)候拓?fù)渑判虿恢挂粋€(gè)結(jié)果夺颤。一般而言，只需要一個(gè)結(jié)果就夠了胁勺。
假設(shè)圖有V個(gè)頂點(diǎn)（vetex）和E條邊（edge）世澜，那么拓?fù)渑判虻臅r(shí)間和空間復(fù)雜度均為O（|V|+|E|）。
拓?fù)渑判蛞话阌袃煞N方法署穗，即BFS和DFS方法寥裂。
- BFS
拓?fù)渑判虻腂FS方法，步驟如下：
I.遍歷圖案疲，計(jì)算每個(gè)節(jié)點(diǎn)的入度（in order/degree）封恰，所謂入度，就是有幾個(gè)其他節(jié)點(diǎn)有進(jìn)入這個(gè)節(jié)點(diǎn)的邊褐啡。很明顯诺舔，入度為0的節(jié)點(diǎn)，沒(méi)有前驅(qū)節(jié)點(diǎn)备畦，因此在拓?fù)渑判蚶锩鎽?yīng)該放在最前面混萝。假如有好幾個(gè)這種0入度的頂點(diǎn)，它們的順序是無(wú)所謂的萍恕。這里把它們放入隊(duì)列逸嘀，同時(shí)也放入結(jié)果數(shù)組。
II.逐個(gè)刪除隊(duì)列里的0入度點(diǎn)允粤，然后對(duì)于和其相連的頂點(diǎn)崭倘，入度-1。其實(shí)就相當(dāng)于把這些頂點(diǎn)從圖上面刪掉类垫。
III.再次檢查圖司光，把新的0入度的點(diǎn)加入隊(duì)列和結(jié)果。
IV.重復(fù)以上過(guò)程悉患，直至圖為空残家。
可以看到，BFS方法就相當(dāng)于每次把最外層的頂點(diǎn)給去除售躁，一層一層剝下來(lái)坞淮。代碼：
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其實(shí)和BFS有相似的地方，也是圍繞入度來(lái)實(shí)現(xiàn)陪捷，只不過(guò)是先一條線到底：
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
來(lái)看看實(shí)際應(yīng)用：
1.選課問(wèn)題I回窘。假設(shè)有n門課要上，序號(hào)從0到n-1市袖，假設(shè)用數(shù)組對(duì)來(lái)表示前置課程啡直，例如用[0,1]來(lái)表示1是0的前置課程。現(xiàn)在給出n和前置課程對(duì)的數(shù)組，返回是否能夠完成課程酒觅。
【解】相當(dāng)于給出n個(gè)頂點(diǎn)的圖和其邊的信息撮执，問(wèn)是否能夠?qū)ζ溥M(jìn)行拓?fù)渑判颉：苊黠@關(guān)鍵就在于有沒(méi)有環(huán)舷丹。
無(wú)論如何二打，第一步還是建立圖的結(jié)構(gòu)。因?yàn)闆](méi)有直接給出neighbor信息掂榔，若再刻意地先求neighbor再按照之前的算法計(jì)算入度，就有點(diǎn)生硬症杏。
其實(shí)装获，換一個(gè)做法，把邊的信息分別存到入度表和出度表厉颤，效果還是一樣的穴豫。之后還是按照正常的拓?fù)渑判蜃龇ǎ徊贿^(guò)這里是把入度表為空的節(jié)點(diǎn)的出度表里的節(jié)點(diǎn)的入度表里的對(duì)應(yīng)節(jié)點(diǎn)給刪除逼友。假設(shè)A是最外層的頂點(diǎn)精肃，有AB這條邊，那么B在A的出度表上帜乞，A在B的入度表上司抱，因此要?jiǎng)h除A，通過(guò)A的出度表找到B黎烈，然后再看B的入度表习柠，把里面的A刪掉。
如果有環(huán)照棋，最后出度表會(huì)刪不完全资溃。因?yàn)榄h(huán)里面的元素天生不可能入度為空，那么自然不會(huì)從環(huán)上的節(jié)點(diǎn)開(kāi)始烈炭，而從其他節(jié)點(diǎn)開(kāi)始之后溶锭，刪除到環(huán)，但環(huán)上的節(jié)點(diǎn)入度除了連接的非環(huán)節(jié)點(diǎn)以外符隙，自然還是有環(huán)上的其他節(jié)點(diǎn)趴捅，因此怎么著也不會(huì)是空，所以就沒(méi)法刪除霹疫。
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.選課問(wèn)題II驻售。接上題，返回拓?fù)渑判虻娜我庖粋€(gè)結(jié)果更米，假如沒(méi)有欺栗，返回空數(shù)組。
【解】相似度99%，多加一個(gè)結(jié)果數(shù)組迟几，把零入度的節(jié)點(diǎn)放進(jìn)去即可消请。代碼略。
3.外文字典±嗳現(xiàn)在有一種新的外語(yǔ)臊泰，也用英文字母，但是順序不一樣⊙潦啵現(xiàn)在給出一組這種外文的單詞缸逃，已經(jīng)按照字典序排列，返回該外文的字母順序厂抽。例如需频，給出[wrt,wrf,er,ett,rftt]，返回wertf筷凤。假如有多個(gè)可能順序昭殉，返回任一個(gè)即可。
【解】還是拓?fù)渑判蛎晔兀徊贿^(guò)這次有多個(gè)對(duì)象挪丢，如何轉(zhuǎn)化是一個(gè)關(guān)鍵問(wèn)題牙肝。
容易犯的錯(cuò)誤是把單詞之間的字典序當(dāng)做單詞內(nèi)的字母序扒最，如果不仔細(xì)看例子，就會(huì)搞錯(cuò)壁榕。單詞內(nèi)不一定是按照字典序排列的慎恒，比如rftt巢块，f就在t之前，題目只是說(shuō)單詞按照字典序排列而已巧号。
也就是說(shuō)族奢，字母的順序是在單詞之間體現(xiàn)出來(lái)的，可以用這一點(diǎn)來(lái)比較相鄰兩個(gè)單詞的字母丹鸿，從而建立圖越走。為什么不循環(huán)比較？沒(méi)必要靠欢，兩兩比較已經(jīng)夠了廊敌。每次比較只能得出一個(gè)順序，拿英文單詞舉例门怪，az在bc之前骡澈，因此只能看出a<b，不能再看出z和c的大小掷空。
例子當(dāng)中肋殴，比較12囤锉，得出t<f，然后23护锤，可知w<e官地，34知道r<t，45知道e<r烙懦，因此w<e<r<t<f驱入。
之后的處理就還是老套路了，注意判斷有沒(méi)有環(huán)氯析。代碼如下：
# T: O(n) S:O(|V|+|E|)=O(1) 因?yàn)橹挥?6個(gè)字母
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
