合縱連橫: 從 圖論的應用題 理解BFS背後的本質

dharmendra sahu on Unsplash

這篇文章，會帶著大家複習以前學過的BFS框架，

並且以圖論的應用題與概念為核心，

貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。

BFS 框架 + 演算法 虛擬碼

# Queue 通常初始化成根結點，作為起點
BFS_queue = deque([root])​

# 先進先出 FIFO 拜訪整張圖(或者說 整棵樹)
while BFS_queue:

	cur = BFS_queue.popleft():
	
	# 根據題意，蒐集相關資訊，進行計算
	# Do somthing​
	
	if cur.left:
		BFS_queue.append( cur.left )
		
	if cur.right:
		BFS_queue.append( cur.right )​
		
return

BFS 框架常見用途:

1.計算樹的深度(最小深度，最大深度...等等與深度有關的應用)

2.在無權圖 或 等權圖中，計算某個點出發的最短路徑

3.在有權圖中，結合Priorty Queue，計算某個點出發的最短路徑。

4.依照指定順序，拜訪、或者修改整棵樹
(例如每層都由右至左拜訪，或者 把樹做鏡像翻轉)

接下來，我們會用這個上面這種框架，貫穿一些同類型，有關聯的題目

(請讀者、或觀眾留意上面的這種 前綴和 框架，之後的解說會反覆出現)

Maximum Depth of Binary Tree - LeetCode 二元樹的最大深度

這題算是很基本的應用，不論在資料結構或者演算法的期中考、上機考都滿常見的。

想法也很直覺，既然是最大深度，那就從根結點，一層一層往下拜訪，到最深那一層BFS拜訪結束的時候，所計算的層樹自然就是樹的最大深度。

依照BFS框架拓展的解題程式碼

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        
        # Base case
        # 空樹 沒有深度 回傳0
        if not root:
            # Empty tree
            return 0

        ## General cases:
        # Start BFS from root node
        # 從根結點開始拜訪，根節點的深度(層樹) = 1
        bfs_q = deque([ (root, 1) ] )

        while bfs_q:

            cur, level = bfs_q.popleft()
							
							# 美往下一層，深度+1
            if cur.left:
                bfs_q.append( (cur.left, level+1) )
            
            if cur.right:
                bfs_q.append( (cur.right, level+1) )
					
				 # 最深那一層的層樹，自然就是樹的最大深度
        return level

開場的暖身題，也蠻好理解的。

有了最大深度，那另一種問法，也可以考最小深度。

Minimum Depth of Binary Tree - LeetCode 二元樹的最小深度

這題其實也是類似的，什麼時候叫做最小深度?

其實就是遇到第一個葉子節點的時候，當下的深度就是最小深度。

依照BFS框架拓展的解題程式碼

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        
        # 空樹沒有深度，回傳0
        if not root:
            return 0

        bfs_queue = deque([(root, 1)])

        while bfs_queue:

            cur, depth = bfs_queue.popleft()

            # 當我們遇到第一個葉子節點，當下的深度就是最小深度
            if not cur.left and not cur.right:
                return depth

            if cur.left:
                bfs_queue.append( (cur.left, depth+1) )

            if cur.right:
                bfs_queue.append( (cur.right, depth+1) )

        return depth

稍微有點變化，但是畫幾個例子，便能找出規律。

打鐵趁熱，接著來看看最短路徑的應用！

Coin Change - LeetCode 最精簡找零，用最少的銅板數量湊出n元

這題如果是從之前專欄文章或YT頻道過來的觀眾或同學應該不陌生，這題當時是用DP框架+最精簡找零的遞回式去解的。

其實，還可以用圖論的BFS先天在無權圖中具有最短路徑來解喔!

怎麼說呢?

用最少的銅板數量湊出n元

相當於我們從0元出發，每次拿一枚銅板進來，看怎麼拿可以用最少次數湊到n元。

這邊的幾元就相當於一個節點，彼此可以互相抵達的金額有一條邊。

n元的最精簡找零

就等價於

$0 到 $n的最短路徑，每拿一枚銅板，步數+1。

舉例來說，假如我們有[$1, $5, $10]面額的銅板，請問11元的最精簡找零是多少?

$0 --拿一枚10元銅板--> $10 --拿一枚1元銅板--> $ 11

或者

$0 --拿一枚1元銅板--> $1 --拿一枚10元銅板--> $ 11

最少用兩枚銅板，就可以湊出11元。

依照BFS框架拓展的解題程式碼

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        # cur amount = 0, cur step = 0
        bfs_q = deque([ (0, 0)])

        # visited set
        seen = set([0])

        # Launch BFS from $0, 
        # Target: growing to $amount by adding a coin on each level of iteration
        while bfs_q:

            cur_value, cur_step = bfs_q.popleft()

            # Base case:
            # We've reached $amount by adding coin from $0
            if cur_value == amount:
                return cur_step

            # General cases:
            # Try to grow up to $amount by adding coin
            for coin in coins:
                
                next_value = cur_value + coin
                
                if next_value not in seen and next_value <= amount :
                    seen.add( next_value )
                    bfs_q.append( (next_value, cur_step+1) )

        # No solution                    
        return -1

條條大路通羅馬，一個題目可以有不只一種解法~
除了DP解，還可以用BFS來解。

舉一反三，剛剛學會了無權圖 或 等權圖 的最短路徑。

接下來，來看有權圖的，這題是最小網路延遲時間。

Network Delay Time - LeetCode 最小網路延遲時間

從信號起始點開始發送訊息，傳遞到整個網路的最小時間是多少?

其實就是從起點開始傳遞，每次傳的時候取當下已知的最短路徑往下傳播，當傳遞到最外層的節點的時候，當下的時間，就是整個網路的最小延遲時間。

依照BFS框架 + 優先權佇列(此處使用minHeap)拓展的解題程式碼

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        
        
        times_dict = defaultdict(dict)
        # 更新整個netowrk，還有每個節點pair之間的傳遞時間
        for source, target, time in times:
            times_dict[source][target] = time

        visited = set()

        # 起點傳遞時間為0，起點節點編號為k
        priorityQ = [(0, k)]
        minTime = 0

        while priorityQ:
            time, source = heapq.heappop(priorityQ)

            if source not in visited:
                visited.add(source)
                minTime = time

                if source in times_dict:
                    for target, dt in times_dict[source].items():

                        if target not in visited:
                            heapq.heappush(priorityQ, (time+dt, target))
                    
        if len(visited) < n:
            return -1

        # 最外層節點的傳遞時間，就是整個網路的最小延遲時間
        return minTime

也是類似的，面對有權圖時，使用BFS框架搭配優先權佇列，
每回合都選已知的最短邊長來傳遞資訊。

剛剛看到的都還屬於計算題。

那有沒有需要修改節點的應用?

其實有喔，接下來看鏡像翻轉二元樹。

Invert Binary Tree - LeetCode 鏡像翻轉二元樹

整顆樹需要以中心軸最對稱，左右翻轉。

可以怎麼做?

其實共通模式就是，依序拜訪每個節點，每次拜訪時，交換左右子樹。

依照BFS框架拓展的解題程式碼

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:        
        
        traversal_queue = deque([root]) if root else None
        
					# lanuch BFS, aka level-order-traversal to carry out invertion
        while traversal_queue:
            
            cur_node = traversal_queue.popleft()
            
							# Invert child node of current node
							# 交換 左右子樹，鏡像翻轉二元樹​
            cur_node.left, cur_node.right = cur_node.right, cur_node.left
            
							# push left child into queue to invert left subtree
            if cur_node.left:
                traversal_queue.append( cur_node.left )
            
							# push right child into queue to invert right subtree
            if cur_node.right:
                traversal_queue.append( cur_node.right )                
        
        return root

結語

好，今天一口氣介紹了最精華的部分，

通用的BFS框架，還有相關的深度、最短路徑、節點操作應用題與演算法建造，

希望能幫助讀者、觀眾徹底理解它的原理，

並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！

感謝收看囉! 我們下篇文章再見~