HackMD
Python-LeetCode 581 第11招 Graph Traversal
本單元介紹圖論中的三個graph走訪的基本演算法：Breadth First Search (BFS)、Depth First Search (DFS) and Topological Sort。前兩者可用於有向圖與無向圖的走訪，後者則是用於有向無環圖(Directed Acyclic Graph, DAG)的偵測或是尋找一個符合前後關係的順序。
基本原理
BFS演算法
圖的搜尋是圖的基本問題：「輸入一圖
在看BFS的演算法前，我們先以一個例子來說明算法要做的事情，以下是一個無向圖。
假設我們要以
這個圖是一個樹狀圖，而且由BFS走出來的，我們稱它是一個BFS tree。BFS tree是一層一層的，每往下一層與起點
在探訪第
因為一個點可能會發現多個點，但我們必須依照發現的順序逐一探訪，所以我們準備一個FIFO(先進先出)的Queue(佇列)
BFS演算法運作的過程中，我們可以把點分成三類，用顏色予以區分：
- 尚未被發現的點(白色)
- 已經被發現，但它的鄰居尚未檢查的點(灰色)
- 已經被發現且鄰居已經被檢查完畢(黑色)
演算法運作的過程中，點會由白變灰，最後都變成黑色就結束了。以下是Python的BFS的範例程式。對每一個點
def bfs(adj, s):
que = [s]; head = 0 # a FIFO queue
visit = {s} # set of all visited vertex
parent = {s:-1} # assume vertex label >=0
dist = {s:0} # distance to s
while head < len(que):
v = que[head]; head += 1 # pop
for u in adj[v]:
if u in visit: continue
que.append(u)
visit.add(u)
parent[u] = v
dist[u] = dist[v] + 1
#end while
# que: list of visited vertex
# visit: set of visited
# parent: BFS tree
# dist: distance of each vertex to s
在解題的場合，筆者的習慣是以list來做queue，用一個變數
BFS通常有下列用途：
- 計算某個點出發可以到達的點。
- 在無加權圖中，計算一個點到其他點的距離，或是找兩點的最短路徑。
- 計算無向圖的connected component。從一個點出發可以拜訪到該點所在的連通區塊的所有點，若對每一個點當起點進行BFS，則可以找到所有連通區塊，但要注意應略過前面的點已經被拜訪過的點。
Depth First Search
除了BFS之外，另外一個常用的圖的搜尋演算法是深度優先搜尋(DFS, Depth-First Search)。BFS像水面掀起的水波，從中心點往外一圈一圈的擴散，DFS通常是以遞迴的概念來說明：「先從一個鄰居出發探索所有可以探索的點，如果還有剩下，則在從下一個鄰居出發，重複此步驟，直到所有鄰居嘗試完畢。」遞迴的演算法通常比較簡潔但不易了解，DFS也不例外。
我們實際看一下DFS在下面這個無向圖上的運作狀況，會比較了解此演算法。假設一樣從2出發。
演算法運作過程如下(假設鄰居的檢查順序依照編號)：
- DFS(2)：2有兩個鄰居{0,3}，而且都未曾被拜訪，先去0，留著3未檢查；
- DFS(0)：0有兩個鄰居{1,2}，先去1；
- DFS(1)：1只有個鄰居{0}，但是0已經被拜訪過，所以return回到0；本來是從0探訪它的鄰居，本來先去1，現在從1回來了，所以檢查下一個鄰居2，但2是已經被拜訪過的，所以也結束，return回到2；本來是從2探訪它的鄰居，本來先去0，現在從0回來了，所以檢查下一個鄰居3，3尚未被拜訪，所以去3；
- DFS(3)：3有3個鄰居{2,4,5}，先檢查2，被拜訪過；再檢查4，沒拜訪過，所以去4(留著5還沒檢查)；
- DFS(4)：4有4個鄰居{3,5,6,7}，先檢查3，被拜訪過；再檢查5，沒拜訪過，所以去5(留著6,7還沒檢查)；
- DFS(5)：5有4個鄰居{3,4,6,7}，先檢查3與4，都被拜訪過；再檢查6，沒拜訪過，所以去6(留著7還沒檢查)；
- DFS(6)：沒被拜訪過的鄰居只有7；
- DFS(7)：沒有沒被拜訪過的鄰居，所以return回到6號點；6沒有剩下沒拜訪過的鄰居，所以return回到5號點；5本來留著7尚未檢查先去6，所以6回來時檢查7，但此時7已經被拜訪過了！！所以也沒有剩下沒拜訪過的鄰居，也return回到4號點；4號點先去5，留著6與7尚未檢查，所以從5號點回來會去檢查6與7，但此時兩點都已經被拜訪過了，所以就return回到3號點；類似地，3號回到2號，然後就結束了整個探訪的過程。
如果我們把每個點被誰呼叫當作它的parent，然後把每點與它的parent連起來，一樣可以得到一棵樹，這棵樹是由DFS走出來的，所以就稱為DFS tree(如下圖)，圖中紅線是走訪順序，它可以讓我們了解DFS運作的過程。
def dfs(s, adj, parent, visit):
visit.add(s)
for v in adj[s]:
if v not in visit:
parent[v] = s
dfs(v, adj, parent, visit)
# end of dfs
# prepare adj
visit = set()
parent = {}
# start node
dfs(start, adj, parent, visit)
DAG and Topological sort
DAG(directed acyclic graph)是指一種沒有環路的有向圖，DAG是應用很多的一個圖的類別，在動態規劃中，也用DAG來描述狀態轉移，其實不只是DP的狀態，在很多前置關係的問題上都有類似的情形，例如一件計畫分成很多工作，某些工作必須在某些工作完成之後才能進行。我們可以將每個工作看成一個點，若
對於一個DAG，我們最常須要找的就是一個拓樸順序(topological sort)，所謂拓樸順序是將所有的點排成一個序列，使得所有的有向邊都是從前往後，而沒有從後往前的邊。拓樸順序顯然不惟一，但通常只要找出其中一個就可以了。
以下圖為例來找一個拓樸順序，因為前置關係是有遞移性的，前置的前置也必須是前置，我們可以看得出來，2一定要放在第一個，相同的5一定是最後一個。因為3要放在右邊所有點前，所以最前面的四個點一定是(2,0,1,3)。置於右邊的四個點，因為4必須在6與7之前，所以3後面只能接4，但6與7不一定誰先誰後，所以我們知道(2,0,1,3,4,6,7,5)是一個拓樸順序，而(2,0,1,3,4,7,6,5)也是一個。
我們的重點要放在如何計算一個拓樸順序，常用的方法有兩個。其中一個是利用DFS，假如在DFS時，對每一個點在完成探訪時(return之前)，將該點的編號輸出，那麼將此輸出順序反轉就可以得到一個拓樸順序。證明不是很難，簡單的說，在執行DFS(
DFS的複雜度是線性時間，所以用DFS來做拓樸順序應該很完美，但是它是遞迴的，很多時候我們不希望使用遞迴，例如DP的過程，因為不想(或是環境不允許)使用遞迴，所以才要找拓樸順序，所以我們需要一個非遞迴的演算法。以下我們介紹一個找出拓樸順序的演算法。
這個方法很簡單，它的原理就是：只要是in-degree=0的點，也就是沒有箭頭指向它的點，都是可以出列的點。
以下是一個使用adjacency list的範例程式，以上面的圖為輸入範例。
一開始先把所有的邊看一遍，用一個list
如果這是一個DAG，while迴圈跑完時，所有的點一定都處理過，否則便是有迴圈。程式的時間複雜度是
# assume vertex = 0..n-1
# edge is the list of directed edge u->v
n=8
edge=[[2,0],[2,3],[0,1],[1,3],[3,4],
[3,5],[4,6],[4,7],[6,5],[7,5]]
adj = [[] for i in range(n)] # out neighbor
deg = [0]*n # in-degree
for u,v in edge:
deg[v] += 1
adj[u].append(v)
# initialize a queue with deg=0
que = [v for v in range(n) if deg[v]==0]
head = 0
while head < len(que):
v = que[head]; head += 1
for u in adj[v]:
deg[u] -= 1
if deg[u]==0: que.append(u)
# end while
if len(que)<n:
print("Existing cycle")
else:
print("A topological sort:", que)
Shortest and longest path on a DAG
在DAG上求兩點之間的最短路徑或最長路徑都是topological sort加上基本DP(動態規劃)觀念的延伸問題。通常是邊上有權重，但權重在點上也是類似的。權重可以是正的或是負的都沒關係。
令
起點的初始
要找最長距離時，將前面DP式的min改成max就可以了。
BFS and DFS 範例題
由於BFS與DFS類似，且有些題目BFS與DFS都能做，所以我們把它們放在一起。以下分不同的資料類型來舉例。
Tree
樹狀圖的BFS/DFS可以比graph的BFS/DFS簡化一些，因為樹狀圖沒有環路，可以不需要紀錄那些點已經走過。我們看以下例題。
(題目連結)102. Binary Tree Level Order Traversal (Medium)
給一個點結構定義好的rooted tree，要找出level by level的list of node value。
做法當然不只一種，最直接的就是用BFS。BFS找出來的一定是與root距離由小而大，也就是說，相同level的會在一起。以這一題來說，我們不使用標準BFS的方式，而用一層產生下一層的方式更自然而簡潔。
以下是範例程式。我們將目前這一層的節點由左而右放在
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root: return []
p = [root] # previous level
ans = []
while p: # d = children of p
ans.append([v.val for v in p])
d = []
for v in p:
if v.left: d.append(v.left)
if v.right: d.append(v.right)
d,p = p,d
#end while
return ans
下面一題其實非常類似。
(題目連結)1161. Maximum Level Sum of a Binary Tree (Medium)
要求出一棵binary tree哪一個level的節點總和最大，只要會求出每一個level的節點，計算最大總和不是問題。
以下是範例程式。時間複雜度
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxLevelSum(self, root: Optional[TreeNode]) -> int:
p = [root] # previous level
level,imax = 0,-1000000001
currLev = 0
while p: # d = children of p
currLev += 1
t = sum(v.val for v in p)
if t>imax:
level,imax = currLev,t
d = []
for v in p:
if v.left: d.append(v.left)
if v.right: d.append(v.right)
d,p = p,d
#end while
return level
(題目連結)297. Serialize and Deserialize Binary Tree (Hard)
這題很有意思，你要設計一套encoding與decoding的方法，encoding是指將一棵binary tree傳換成一個字串，而decoding就是將字串轉換成binary tree。
將rooted tree編碼成一個序列有個簡單的方法，把leaf的children補成external node，也就是沒有結點的NULL 指標，實作時使用一個不存在真正節點的值即可。然後走一個DFS順序。解碼時用相同的概念打一個遞迴就可以了。
以下是範例程式。時間複雜度
解碼時，先用split()把傳入的字串以空白切開。走一個遞迴程序，它的程式結構跟DFS幾乎是一樣的。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
# DFS sequence with null for external nodes
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
encode = ""
def dfs(r):
nonlocal encode
if not r:
encode += "$ "
return
encode += str(r.val)+' '
dfs(r.left)
dfs(r.right)
dfs(root)
return encode[:-1] # remove last seperator |
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
seq = data.split()
idx = 0
def decode():
nonlocal seq, idx
if seq[idx]=='$':
idx += 1
return None
v = TreeNode(int(seq[idx]))
idx += 1
v.left = decode()
v.right = decode()
return v
root = decode()
return root
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))
很多樹的問題可以歸類到DFS，也可以歸類到動態規劃或遞迴。下題是一個例子。
(題目連結)1123. Lowest Common Ancestor of Deepest Leaves (Medium)
這題要在一棵樹中找出深度最深那些節點的Lowest common ancestor (LCA)。
樹的題目很適合用遞迴的思考，因為樹本來就是遞迴定義出來的結構。要找最深節點的LCA，我們用遞迴的思考：假設目前在某個節點
根據題意，我們必須先知道左右子樹的最深節點的深度，如果兩邊一樣深，那LCA就是
這樣程式就好寫了，我們必須知道左右深度與個別的解，深度可以由上往下透過參數傳，回傳的是最深的深度與該子樹的解。遞迴的終端條件設在空節點。以下是範例程式。時間複雜度
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(v, dep): # return (depth of deepest,lca)
if not v: return (dep,None) # leaf
le = dfs(v.left,dep+1)
ri = dfs(v.right,dep+1)
if le[0] == ri[0]: return (le[0],v)
return max(le,ri)
#end dfs
r = dfs(root,0)
return r[1]
Grid
格子點是圖形(Graph)的一種形式，LeetCode與其他程式解題中都經常出現，原因可能是不需要在題目中引入graph的術語，出題也比較方便。Python在處理grid的題目時有一些比較方便的小技巧，可以參閱Python-LeetCode 581 第三招 Grid Traversal ，
我們以下選一些BFS/DFS的題目。
(題目連結) 130. Surrounded Regions (Medium)
本題中，每一個格子點內是O或X，要把被X包圍的O更換為X。所謂包圍是指O的區域四方位聯通的鄰居都是X。下圖是一個例子。
這一題可以反面思考：找出那些沒有被包圍的，剩下的都是被包圍的。那些沒有被包圍呢？就是連通到邊界的O區域。
所以我們可以用BFS/DFS，從邊界的O開始走訪，找出連通到邊界的所有O區域的點。本題我們以DFS來示範，以下是範例程式，時間複雜度
走訪過程中，我們將走到的點暫時改成'V'，所以不必另外紀錄是否已經走過。當走訪完畢之後，將所有的V改成O，而所有的O改成X。
class Solution:
# dfs from board O
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
m,n = len(board),len(board[0])
if min(m,n) <= 2: return # nothing can be capture
def dfs(r,c,board): # modified O to V
board[r][c] = 'V'
for nr,nc in ((r,c+1),(r,c-1),(r+1,c),(r-1,c)):
if 0<=nr<m and 0<=nc<n and board[nr][nc]=='O':
dfs(nr,nc,board)
# from boarder O
for i in range(m):
if board[i][0] == 'O':
dfs(i,0,board)
if board[i][n-1] == 'O':
dfs(i,n-1,board)
for j in range(n):
if board[0][j] == 'O':
dfs(0,j,board)
if board[m-1][j] == 'O':
dfs(m-1,j,board)
# replace O->X, V->O
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'V':
board[i][j] = 'O'
return
(題目連結) 200. Number of Islands (Medium)
很標準的格子點找component的題目。格子點內是0或1，找出1的連通區塊有幾個。
與上一題很類似，我們也使用DFS，過程中將走過的點改成2來避免重複走訪，另外一開始在最後一列與最後一欄加上0當作哨兵，來免除檢查邊界的動作。以下是範例程式。時間複雜度
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
drc = [(0,1),(0,-1),(1,0),(-1,0)]
def dfs(r,c,g): #search a component and change to '2'
g[r][c] = '2'
for nr,nc in ((r,c+1),(r,c-1),(r+1,c),(r-1,c)):
if g[nr][nc] == '1':
dfs(nr,nc,g)
return
#main
m,n = len(grid), len(grid[0])
for row in grid:
row.append('0') # sentinel
grid.append( ["0"]*(n+1))
island = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
island += 1
dfs(i,j,grid)
return island
(題目連結) 417. Pacific Atlantic Water Flow (Medium)
格子點給的是每一點的高度，雨水下到每一個格子後，會流到上下左右高度相同或較低的鄰居。上方與左方是太平洋，右邊與下邊是大西洋，請問有哪一些格子的雨水會流到兩個海洋。以下圖的例子來說，要找的是那些淡黃色的格子。
也就是說，有哪些格子存在一條路徑通往上左邊界，也存在路徑通往右下邊界。所謂路徑是高度non-increasing的相鄰格子序列。
我們一樣可以反過來做，由邊界找所有non-decreasing路徑可以到達的點。太平洋做一次，大西洋做一次，兩者取交集就是答案。
我們用BFS來做，BFS的輸入是一個初始的list
左上邊邊界當起點做一次BFS，右下邊邊界當起點做一次，然後將兩次回傳的集合做交集後轉成list就可以了。
以下是範例程式。時間複雜度
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
# return set of reachable, given initial queue
def bfs(start):
reach = set(start)
head= 0
while head < len(start):
r,c = start[head]
head += 1
for nr,nc in [(r,c-1),(r,c+1),(r-1,c),(r+1,c)]:
if 0<=nr<m and 0<=nc<n and \
heights[nr][nc]>=heights[r][c] and (nr,nc) not in reach:
reach.add((nr,nc))
start.append((nr,nc))
#end while
return reach
m,n = len(heights), len(heights[0])
s1 = bfs([(0,c) for c in range(n)]+[(r,0) for r in range(1,m)])
s2 = bfs([(m-1,c) for c in range(n)]+[(r,n-1) for r in range(m-1)])
both = list(s1&s2)
return both
下面這個題目是LeetCode中少數對Python比較不友善的題目，在筆者寫這一題的時候，在相同的時間複雜度下，需要加入一些技巧才不會TLE。
(題目連結) 675. Cut Off Trees for Golf Event (Hard)
題目是說每個格子裡有一個整數，0代表不能通行，1表示可以通行，其他的格子要數字由小到大走訪(可以通過任意非0的格子)，起點在(0,0)，大於1的數字無相同，求最小總路徑長度。
題目看起來不難，將大於1的數字位置由小到大排序後，求相鄰數字位置之間的最短路徑就可以了，因為每走一格長度都是1，所以用BFS就可以求最短路徑。時間複雜度
在寫這一題的時候，這樣寫的python程式是無法通過的，會TLE。現在或許可能可以，因為LeetCode的server有效能越來越好的情況，筆者一年前的程式，現在丟進去幾乎running time都只剩當初的一半。
無論如何，以下我們講一個稍微優化的技巧。這個技巧很簡單，假設要依序拜訪的節點是
以下是範例程式。程式中我們將0不能走的位置用字典標示為以走過，格子的邊界外，也都用字典紀錄為以走過，這樣就不會走到這些不該走的點。
第9 ~ 14行把格子掃一遍，要走的數值與位置放入
第36行開始，我們每次取最後三點做一次BFS然後刪除兩點，直到剩下不超過2點時結束，如果此時還有兩點，就再做一次BFS求兩點距離。
class Solution:
# BFS search from i to i-1 and i+1
def cutOffTree(self, forest: List[List[int]]) -> int:
m,n = len(forest),len(forest[0])
seq = [(0,0,0)]
D0 = dict()
for j in range(n): D0[-1,j] = -1
for j in range(n): D0[m,j] = -1
for i in range(m):
D0[i,-1] = -1; D0[i,n] = -1
for j in range(n):
x = forest[i][j]
if x>1: seq.append((x,i,j))
elif x==0: D0[i,j]=-1
seq.sort()
def bfs(p0,p1,p2): # distance (p0,p1)+(p0,p2)
#print(p0,p1,p2)
que=[p0]; head=0
D = D0.copy() # all 0 visited
D[p0] = 0
while head<len(que) and (p1 not in D or p2 not in D):
#print(que,head)
r,c = que[head]; head += 1
nd = D[r,c]+1
for nr,nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
if (nr,nc) not in D:
D[nr,nc] = nd
que.append((nr,nc))
#end for
#endwhile
if p1 not in D or p2 not in D:
return -1
return D[p1]+D[p2]
#end BFS
total = 0
while len(seq)>2:
#print(seq)
step = bfs(seq[-2][1:],seq[-1][1:],seq[-3][1:])
#print(seq,step)
if step<0: return -1
total += step
seq.pop(); seq.pop()
if len(seq)>1:
step = bfs(seq[0][1:],seq[0][1:],seq[1][1:])
if step<0: return -1
total += step
return total
下面一題也是較難的題目。
(題目連結) 749. Contain Virus (Hard)
某些格子有病毒。連在一起的感染格子是屬於同一群。同一群每天會感染周遭鄰接尚未感染的格子。每天只能蓋牆壁圍堵一群病毒，指定圍堵隔天感染最多格子的那一群(保證沒有平手)。
請計算最後用了多少長度的圍牆。最後可能是全部都堵住了，也可能全部都感染了。
我們稍微修改BFS的程式，讓它可以除了計算出一群的節點之外，也可以算出周長與鄰接的0(未感染格子)，為了方便不重複計算，我們用set存鄰接的格子。以下範例程式中，第4 ~ 21行是這樣的一個函數。
主程式部分就跑一個無窮迴圈，每次找出所有的群以及它們的周長與鄰接點數，周長的計算方式，就計算每個1與0格子的交界線數量。所有群探訪完後，取出最大鄰接點數的群，將它的周長納入解答，對於非最大的群，就將它的鄰接格子設為感染(1)。我們在BFS的時候，將走過感染的格子改成2，如果沒有圍堵的恢復成1，圍堵的群就保留2的狀態，也就不會在下一回合再走到它。程式有點長，但不算太難。
class Solution:
def containVirus(self, Infect: List[List[int]]) -> int:
m,n = len(Infect),len(Infect[0])
def findg(r,c): # return perimeter,next,inner
inext = set()
perimeter = 0
que=[(r,c)]
Infect[r][c]=2
head=0
while head<len(que):
r,c=que[head]
head += 1
for nr,nc in ((r,c-1),(r,c+1),(r-1,c),(r+1,c)):
if 0<=nr<m and 0<=nc<n:
if Infect[nr][nc]==1:
Infect[nr][nc]=2
que.append((nr,nc))
elif Infect[nr][nc]==0:
inext.add((nr,nc))
perimeter += 1
return perimeter,inext,que
#end findg
wall=0
while True:
allgroup = []
for r in range(m):
for c in range(n):
if Infect[r][c]==1:
allgroup.append(findg(r,c))
#print(allgroup)
if not allgroup: break
imax = max(len(inext) for w,inext,inner in allgroup)
for perimeter,inext,inner in allgroup:
if len(inext)==imax: # never tie
wall += perimeter
else:
for r,c in inext:
Infect[r][c]=1
for r,c in inner:
Infect[r][c]=1
if len(allgroup)==1: break
#endwhile
return wall
Graph
二分圖檢測是個圖論很基本的問題。所謂二分圖是指一個圖的點可以分成兩個獨立點集，獨立點集的意思是此集合中任兩點都沒有邊相連。下面這個題目是二分圖檢測的裸題。給你一個圖，請回傳它是否是二分圖。
(題目連結) 785. Is Graph Bipartite? (Medium)
圖論中，所謂點的著色是給每一個點一個顏色編號，必須滿足：相鄰的點必須著不同色。
二分圖就是可以只用二色著色。我們可以用著色的概念來檢測。
假設要著AB兩色。從任意一點
上面的演算法可以用BFS或DFS來做，以下是用DFS的範例程式，顏色用1與-1表示。我們的DFS從傳入一個指定點
跟偵測連通區塊一樣，主程式要拉一個迴圈對每一個尚未走訪的點，執行DFS檢測它所屬的連通區塊是否為二分圖。時間複雜度
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
n = len(graph)
color = {}
def dfs(v,c):
color[v]=c
for u in graph[v]:
if u in color:
if color[u]==c: return False
else:
if not dfs(u,-c):
return False
return True
#main
for v in range(n):
if v in color: continue
if not dfs(v,1): return False
return True
題目的Graph有時並不是由輸入明顯給的，我們看以下例題。
(題目連結) 815. Bus Routes (Hard)
有若干巴士路線，求從某一站要到某一站最少須搭乘幾次巴士。
如果把停靠站看成graph的點，兩點如果有一條巴士路線同時經過，則兩站之間有一條邊。但這個方法並不是個好主意，因為如果有一條巴士路線上有
事實上，把停靠站看成一群獨立點集，巴士路線看成一群獨立點集，這是個二分圖的關係。我們以停靠站為主來做BFS走訪，計算每一個停靠站與起點的距離，也就是最少要搭乘幾次巴士。對一個停靠站
為了要找到在某停靠站可以搭乘的巴士路線，我們要將輸入做一個轉換，因為輸入是給某個路線可以到達那些站。
以下是範例程式。我們用dict of list來存每一站可以搭的巴士。第4 ~ 7行是做輸入轉換。第9行開始是BFS，以字典dist來存已知停靠站的距離。在while迴圈中一樣的每次取出一點，我們要檢查這一點所有可以搭乘的巴士，以及可搭乘巴士所能到達的點。這檢查過程中，我們都排除已經看過的巴士與以隻距離的停靠站，以便免重覆的計算。
時間複雜度
class Solution:
def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
n = len(routes)
mybus = defaultdict(list) # buses at given stop
for i in range(n):
for stops in routes[i]:
mybus[stops].append(i)
#BFS
que = [source]; head = 0
dist = {source:0}
visited = [False]*n # if bus is visited
while head<len(que) and target not in dist:
v = que[head]; head += 1
d = dist[v]+1
for bus in mybus[v]: # check each bus we can take at v
if visited[bus]: continue
visited[bus] = True
for stops in routes[bus]:
if stops not in dist:
dist[stops] = d
que.append(stops)
#end for
#end for
#end while
if target not in dist: return -1
return dist[target]
(題目連結) 924. Minimize Malware Spread (Hard)
一個有
依照題意，如果一個連通區塊有超過一個感染的節點，則移出任何該連通區塊的節點都不會影響最後的結果。所以，我們的目標是找出
我們找連通區塊時，可以順便將所有點的leader設為該連通區塊的起點。當處理到某一點時，我們可以檢查它的leader是否被標記過，若有，表示有兩個
本題的graph是以adjacent matrix傳入，所以輸入的大小為
在主程式中，我們設
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
n = len(graph)
leader = [-1]*n
def dfs(v,r): # return num of nodes and set leader=r
num = 1
leader[v] = r
for u,e in enumerate(graph[v]):
if e and leader[u]<0:
num += dfs(u,r)
return num
#main
cnt = [-1]*n
for v in initial:
if leader[v]<0:
cnt[v] = dfs(v,v)
else:
cnt[leader[v]] = 0 # >1 in initial
cnt[v] = 0
return cnt.index(max(cnt))
(題目連結) 1129. Shortest Path with Alternating Colors (Medium)
一個圖中有兩種顏色的邊，要找出起點0到每一個點的最短交錯路徑長度，所謂交錯路徑是指路徑上的邊的顏色是兩色交錯出現。
我們修改BFS，每一個點除了編號外，還有此時到達它的前一個邊顏色，也就是(節點編號,顏色)兩個值構成一組狀態。根據狀態的顏色，就可以選取下一個可以走的邊的顏色。
以下是範例程式。一開始(第5 ~ 9行)先將輸入的邊集轉成adjacency list，此處每個點的鄰居也分兩色(0與1)儲存。距離也設兩個顏色，初值給oo代表走不到。因為第一個邊沒有限制顏色，所以queue中的初值，給起點的兩個顏色。在while迴圈中，每次取出一個狀態，點編號
當BFS結束後，我們對於每一點的兩種到達顏色路徑長度取較小值。如果到達不了的點就給
時間複雜度跟一般BFS一樣為線性時間。
class Solution:
def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
# red=0, blue=1
oo = n+n
adj =[ [[] for i in range(n)] for c in range(2)]
for a,b in redEdges:
adj[0][a].append(b)
for a,b in blueEdges:
adj[1][a].append(b)
#bfs
d = [[oo]*n, [oo]*n] # distance
d[0][0]=d[1][0]=0
que = [(0,0),(0,1)] # (node,color)
head= 0
while head <len(que):
node,color = que[head]; head += 1
c2 = 1-color
for v in adj[c2][node]:
if d[c2][v]==oo:
d[c2][v] = d[color][node]+1
que.append((v,c2))
#endfor
#end bfs
for i in range(n):
d[0][i] = min(d[0][i],d[1][i])
if d[0][i]==oo: d[0][i]=-1
return d[0]
狀態走訪
有些問題要走訪的不是輸入給你的圖，而是問題所描述的一些狀態之間從某個狀態轉換到某個狀態，
(題目連結) 127. Word Ladder (Hard)
給開始的字串、結束的字串，以及一群可以做為中間節點的字串，這些字串的長度都是一樣的。要找一個從開始到結束的最短路徑，路徑上相鄰兩個字串只能差一個字元。例如
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
答案是
最短路徑可以用BFS求，問題在於要先建構出這個圖，也就是哪個字串與哪個字串之間有邊相連。如果倆倆來比較，需要花費
BFS的部分就不需要多說，主要問題是建構出哪個字串與哪個字串可以相接的adjacency list。
我們做
以下是範例程式。
第4 ~ 15行是BFS，跟前面的沒有甚麼不同，這裡我們用了deque()。第18 ~ 20行我們特判掉一些特例，接著找出起點與終點的編號，包含處理本題起點可能不在wordList中的狀況。接著跑一個
時間複雜度
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
# BFS to find the shortest path
def BFS(s, t): # compute distance d[] from s
d = [-1]*len(adj)
que = deque([s])
d[s] = 0
while que and d[t]<0:
v = que.popleft()
for u in adj[v]:
if d[u]<0:
que.append(u)
d[u] = d[v] + 1
#end while
return d[t]
# build the graph (adjacency list) by rotation and dict
n,m = len(wordList),len(beginWord)
if endWord not in wordList: return 0
if m==1: return 2 # length = 1
if beginWord in wordList:
source = wordList.index(beginWord)
else:
wordList.append(beginWord)
source = n
n += 1
dest = wordList.index(endWord)
# building adj
adj = [[] for i in range(n)] # source at n
for p in range(m): # find words diff at p-th ch
dic = defaultdict(list)
for i,w in enumerate(wordList):
ww = w[:p]+w[p+1:]
dic[ww].append(i)
for same in dic.values():
for i in range(len(same)):
for j in range(i+1,len(same)):
adj[same[i]].append(same[j])
adj[same[j]].append(same[i])
# end for building adj
return BFS(source, dest)+1
下面這一題是前一題的延伸，前一題只要找出距離，也就是找一條就可以，這一題要找出所有的最短路徑。
(題目連結) 126. Word Ladder II (Hard)
這題前半部建圖與找最段路徑長度的部分與前一題一模一樣，我們專注在如何找出所有的為短路徑。
在一個有向或無向圖上，要找出
- 對任意點在此DAG上的點
這一題我們可以用以下的步驟來做：
- 建出字串之間的關係圖(與前題相同)
- 以BFS找出起點到終點的最短路徑長度
- 從起點開始做一個DFS在所有最短路徑形成的DAG上展開搜尋。對於一個目前的路徑
以下是範例程式。第4行的BFS與前一題稍有不同，因為我們在執行完畢後要保留距離
前半部的時間複雜度與前一題相同，DFS的部分的時間複雜度是所有最短路徑長度的總和。
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
# BFS to find the shortest path
def BFS(s, t, adj, d): # compute distance d[] from s
que = deque([s])
d[s] = 0
while que and d[t]<0:
v = que.popleft()
for u in adj[v]:
if d[u]<0:
que.append(u)
d[u] = d[v] + 1
#end while
return d[t]
# dfs to find path from v to dest, current path = ipath
def dfs(ipath): # dist = distance from v to dest
nonlocal dest, adj, d, path
v = ipath[-1]
if d[v] == 1: # path found, insert to ans
path.append(ipath+[dest])
return
for u in adj[v]:
if d[u] == d[v]-1:
ipath.append(u)
dfs(ipath)
ipath.pop()
# end dfs
n,m = len(wordList),len(beginWord)
if endWord not in wordList: return []
if m==1:
return [[beginWord, endWord]] # length = 1
if beginWord in wordList:
source = wordList.index(beginWord)
else:
wordList.append(beginWord)
source = n
n += 1
dest = wordList.index(endWord)
# building adj
adj = [[] for i in range(n)] # source at n
for p in range(m): # find words diff at p-th ch
dic = defaultdict(list)
for i,w in enumerate(wordList):
ww = w[:p]+w[p+1:]
dic[ww].append(i)
for same in dic.values():
for i in range(len(same)):
for j in range(i+1,len(same)):
adj[same[i]].append(same[j])
adj[same[j]].append(same[i])
# end for building adj
d = [-1]*n # distance to destination
BFS(dest, source, adj, d)
if d[source] == -1: return []
path = [] # answer, all shortest path
ipath = [source]
dfs(ipath)
ans = []
for ll in path:
t = [wordList[i] for i in ll]
ans.append(t)
return ans
(題目連結) 773. Sliding Puzzle (Hard)
這是一個智慧盤的遊戲，有一個
以下圖為例，只要把5向左滑動，一步就可以變成目標。
這是一個暴搜解空間的題目，想像所有可能的盤面，也就是狀態，有
我們不須先建立此圖，而直接將解空間以樹狀圖展開，遞迴嘗試所有可能。本題因為要找最少步數，所以適合用BFS來暴搜。
對於任何一個盤面，它的移動必然是空格旁的某個位置與空格交換，所以，每一步只有三種或兩種可能。我們用tuple來儲存盤面，為了方便與清楚，寫一個副程式對六種可能的空格位置，回傳它下一步可能的盤面。
主程式就跑一個BFS，距離就用dict of tuple來存，要留意tuple可以做hash，但list不可以。
以下是範例程式。
class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
def inext(t):
if t[0]==0:
return [(t[1],0)+t[2:], (t[3],t[1],t[2],t[0],t[4],t[5])]
elif t[1]==0:
return [(t[1],t[0])+t[2:], (t[0],t[2],t[1])+t[3:],
(t[0],t[4],t[2],t[3],t[1],t[5])]
elif t[2]==0:
return [(t[0],t[2],t[1])+t[3:], (t[0],t[1],t[5],t[3],t[4],t[2])]
elif t[3]==0:
return [t[:3]+(t[4],t[3],t[5]), (t[3],t[1],t[2],t[0],t[4],t[5])]
elif t[4]==0:
return [t[:4]+(t[5],t[4]), t[:3]+(t[4],t[3],t[5]),
(t[0],t[4],t[2],t[3],t[1],t[5])]
else: #t[5]=0
return [t[:4]+(t[5],t[4]), (t[0],t[1],t[5],t[3],t[4],t[2])]
#end inext
target=(1,2,3,4,5,0)
s = tuple(board[0]+board[1])
d = {s:0}
que = [s]
head=0
while head<len(que) and target not in d:
v = que[head]
head += 1
for u in inext(v):
if u not in d:
d[u]=d[v]+1
que.append(u)
#end while
if target in d: return d[target]
return -1
Topological sort範例
前兩題是類似題，都是裸題。
(題目連結) 207. Course Schedule (Medium)
有一些課程，某些課程是某些課程的先修課，要修某課程之前必須修完它的所有先修課。請問是否可能修完所有的課。
這題只是在問所給的圖是否是個DAG，或者有環路。
這是Topological sort的裸題。依照前面介紹的方式寫就可以了，如果迴圈跑完沒有歷遍所有的點就是有環路。
以下是範例程式。時間複雜度
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# check dag, topological sort
deg = [0]*numCourses
succ = [[] for i in range(numCourses)] # succesor
for u,v in prerequisites: # edge (v,u)
deg[u] += 1
succ[v].append(u)
# move to queue whenever deg==0
queue = [v for v in range(numCourses) if deg[v]==0]
head = 0
while head<len(queue) and len(queue)<numCourses:
v = queue[head]
head += 1
for u in succ[v]:
deg[u] -= 1
if deg[u] == 0:
queue.append(u)
return len(queue)==numCourses
(題目連結) 210. Course Schedule II (Easy)
這題是前一題的延伸，不只要問是否可以修完，要找出一個修課的順序，也就是要找一個topological sort。
這還是個裸題。因為要回傳排序結果，程式中用list加上一個頭端的index來實作deque比較好，這樣不會真的pop掉。最後list中就是所要的拓譜排序。
以下是範例程式。時間複雜度
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# topological sort
deg = [0]*numCourses
succ = [[] for i in range(numCourses)] # succesor
for u,v in prerequisites: # edge (v,u)
deg[u] += 1
succ[v].append(u)
# move to queue whenever deg==0
queue = [v for v in range(numCourses) if deg[v]==0]
head = 0
while head<len(queue) and len(queue)<numCourses:
v = queue[head]
head += 1
for u in succ[v]:
deg[u] -= 1
if deg[u] == 0:
queue.append(u)
if len(queue)==numCourses:
return queue
return []
下面這題有點複雜。
(題目連結) 1203. Sort Items by Groups Respecting Dependencies (Hard)
有一些項目要排序，每個項目可能屬於每一群，也可能不屬於任何一群(也就是自成一群)。排序的結果要符合以下要求
- 同一群的項目必須排在一起
- 要滿足所有給定的先後關係。對於編號
雖然比較複雜，但也就只是具有指定先後關係的一種排序，還是拓譜順序的問題。因為同一組必須排在一起，所以我們應該先找組的排序，然後每一組在各自排序。若兩組的項目之間有先後關係，就代表組的順序必須滿足此先後關係。因此我們可以用下面步驟做這一題。
- 找出每一組的member，對於沒有組別的item，自創一個組只含該item。
- 將item之間的關係，根據是同組或不同組，轉換為組的先後關係，以及同組內item的先後關係。
- 找出組的拓普排序
- 對於每一個組，找出其成員的拓譜排序。
我們前面介紹的topological sort使用的是每一個點的後繼是什麼，本題給的是必須放在
以下是範例程式。時間複雜度
class Solution:
def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
# label group -1 and build member list
member = [[] for i in range(m)]
for i in range(n):
if group[i]<0: # no group
group[i] = m; m+=1 # create a new group
member.append([i]) # only itslef
else:
member[group[i]].append(i)
#build inter-group and intra-igroup relation
beforeG = [set() for i in range(m)] # group precedence
for i in range(n):
tem = [] # relation in the same group
for v in beforeItems[i]:
if group[i]==group[v]: # same group
tem.append(v)
else: # group relation
beforeG[group[i]].add(group[v])
tem,beforeItems[i] = beforeItems[i],tem
def topo_sort(vertex, child): # topollogical sort, return empty if cycle
deg = Counter()
for v in vertex:
for u in child[v]:
deg[u] += 1
que = [v for v in vertex if deg[v]==0]
head = 0
while head<len(que):
v = que[head]; head += 1
for u in child[v]:
deg[u] -= 1
if deg[u]==0: que.append(u)
return que
# sort group; in reverse order due to the given input
gque = topo_sort(range(m),beforeG)
if len(gque)!=m: return []
ans = []
for g in gque: # topological sort of member in each group
tlist = topo_sort(member[g],beforeItems)
if len(tlist) != len(member[g]): return []
ans += tlist
return ans[::-1]
(題目連結) 1298. Maximum Candies You Can Get from Boxes (Hard)
有一些箱子，每個箱子裡有若干糖果，也可能有打開某些箱子的鑰匙。一開始有一些箱子是已經打開的，其他的箱子必須(1)被找到且(2)有開啟的鑰匙，才能打開它。打開鑰匙就可以獲得裡面的糖果、鑰匙、與找到箱子中的其他箱子。請問最後可以拿到多少糖果。
拿到多少糖果也就是要問那些箱子是可以開啟的。
題目跟topological sort好像不完全一樣，但也可感覺有某些程度的相像。對每一個箱子，我們紀錄是否已經找到與是否已經有鑰匙兩個開啟的條件，我們把已經可以開啟的箱子，放在一個queue中，每次開啟一個queue中的箱子，根據箱子內發現的箱子與找到的鑰匙，檢查是否有新的可以開啟的箱子。直到queue中是空的就結束了。
以下是範例程式。時間複雜度
class Solution:
# box i can be open if its key is obtained and its parent is opened
def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
n = len(status)
found = [False]*n # box is found
for b in initialBoxes:
found[b] = True
# status if opened (own the key)
que = [b for b in initialBoxes if status[b]]
visit = [False]*n # boxed already opened
for b in que: visit[b]=True
head = 0
total = 0
while head <len(que):
b = que[head]; head += 1
total += candies[b]
for p in keys[b]:
status[p] = 1
if found[p] and not visit[p]:
que.append(p)
visit[p]=True
for p in containedBoxes[b]:
found[p] = True
if status[p] and not visit[p]:
que.append(p)
visit[p]=True
return total
(題目連結) 1857. Largest Color Value in a Directed Graph (Hard)
給一個有向圖，每個點有一個顏色，顏色是以一個小寫英文字母表示，也就是說最多26種顏色。要找出一條路徑，經過同一種顏色的點越多越好。請問最多可以經過幾個同一顏色的點。如果有環路時回傳
這個題目其實是限定在DAG上面，只是一開始沒有講很清楚。如果不限定在DAG，有環路時，可以一直繞，就沒有最大值。如果限定simple path(點不可重複)，那會變成NP-hard的問題。
DAG就沒這麼難了。但也不太簡單。
想像沿著一個topological sort由前往後掃描。假設我們只要知道經過某個顏色最多點的路徑，那麼就像找最長路徑一樣，我們只要紀錄到達每一個點時可以踩到的最大值就可以了。既然只有26種顏色，做26次就得了。
我們也可以只做一次，但將26中顏色的最大值都記錄下來，基本上是一樣的，但可以少做很多重複的事，所以這個方法是比較好一點的。
我們可以利用python的特別適合計數的字典Counter來做，Counter的設計是用來處理Multi-set，所以兩個Counter可以做OR，結果是對每一個key值所對應的value取max，正是我們所需要的。
以下是範例程式，基本上是個標準的topological sort，只是每一點配上了一個Counter
時間複雜度是
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
n = len(colors)
deg = [0]*n
adj = [[] for i in range(n)]
for u,v in edges:
adj[u].append(v)
deg[v] += 1
que = [v for v in range(n) if deg[v]==0]
cnt = [Counter() for i in range(n)]
for v in que: cnt[v][colors[v]]=1
head = 0
imax = 1
while head < len(que):
v = que[head]; head += 1
for u in adj[v]:
deg[u] -= 1
cnt[u] |= cnt[v]
if deg[u]==0:
cnt[u][colors[u]] += 1
imax = max(imax, max(cnt[u].values()))
que.append(u)
#end while
if len(que)<n: return -1
return imax
(題目連結) 2050. Parallel Courses III (Hard)
這題跟一開始DAG的基本題修課問題是很像的，也是有一些課要修，有些課是另外一門課的先修課程，必須修完一門課的所有先修課程，才能修該門課。
每一門課有需要修課的時間，無前後關聯的課可以同時修，請問最少要多少時間修完所有的課。請留意先後關係是有遞移性的。
這個相當於是在DAG要求longest path，但權重不在邊上的長度，而在點上的時間。這也是計畫管理與施工網圖的一個很重要的應用。簡單就本題的敘述與要求來說，我們需要計算的是每一門課的最早開始時間，而
有了這個理解，就很簡單了，以下是範例程式。稍微留意本題中的節點編號是1開始，但每個節點的時間是0-indexed，所以要稍加轉換。時間複雜度是線性時間。
class Solution:
# longest path in a dag
def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
deg = [0]*n
succ = [[] for i in range(n)]
for u,v in relations: # index -1
deg[v-1] += 1
succ[u-1].append(v-1)
start = [0]*n # earliest starting time
que = [v for v in range(n) if deg[v]==0]
head = 0
while head < len(que):
v = que[head]; head += 1
ftime = start[v]+time[v]
for u in succ[v]:
if ftime > start[u]:
start[u] = ftime
deg[u] -= 1
if deg[u]==0: que.append(u)
#end while
return max(start[v]+time[v] for v in range(n))
結語
Graph traversal是最基本的圖論演算法，它的應用很廣，在之前Python-LeetCode 581 第三招 Grid Traversal 中介紹的是比較針對grid這種特殊圖，本單元則是更普遍的一般情形。
圖論還有很多重要的演算法但LeetCode中的圖論題並不多也不深入，除了本單元基本的走訪外，接下來還會介紹最短路徑的問題。
