合縱連橫: 從 路徑搜索 理解DFS背後的本質

Ali Kazal on Unsplash

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

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

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

DFS 深度優先搜索框架

def dfs( parameter ):
	
	# 邊界條件
	if base case or stop condition:

		#​ 更新結果
		return
	
	# 通則​
	for each child node​:

		# 更新參數，遞回下一層的節點
		dfs( updated parameter)

	return

如果特化成圖論中N4 四連通探索的DFS，往往具有下列形式

def dfs( parameter ):

	if base case or stop condition:

		#​ 更新結果
		return

	# 更新參數，遞回4連通相鄰的節點
	mark current node as visited
	
	# 分別是 左、右、上、下 四個鄰居​
	dfs( updated parameter, and go left )
	dfs( updated parameter, aad go right )
	dfs( updated parameter, and go up )
	dfs( updated parameter, and go down )
	
	return

示意圖

常見的用途:

深度優先探索，探索整張圖(也可以是樹、鏈結串列。)

檢測是否有滿足特定條件的路徑(存在性的判斷)

Word Search - LeetCode 搜尋特定的單字是否存在

這題給定一個矩陣，問我們這個矩陣中，是否存在一條N4 四連通的路徑，路徑上的字串恰好是某個特定的單字。

剛好就是我們剛剛提到的存在性判斷，檢測是否有滿足特定條件的路徑。

掃描整個矩陣，依序從每個格子點出發，依序拜訪四連通鄰居，一直往下走，看看有沒有一條路徑剛好可以拼出某個特定的單字。

實作上有一個細節要特別留意，為了避免重複搜索造成無窮循環，每個被我們拜訪過的格子點會先暫時標記成"#"代表已經走過，所有路徑都拜訪過之後，才會還原回來。

以DFS +N4探索框架的形式實現演算法，程式碼如下:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        if not board: 
            
            # Quick response for empty board
            return False
        
        h, w = len(board), len(board[0])
      
        # ------------------------------------------------------
    
        def dfs_search(idx: int, x: int, y: int) -> bool:
            
            if x < 0 or x == w or y < 0 or y == h or word[idx] != board[y][x]:
                # Reject if out of boundary, or current grid cannot match the character word[idx]
                return False

            if idx == len(word) - 1: 
                # Accept when we match all characters of word during DFS
                return True

            cur = board[y][x]
            
            # mark as '#' to avoid repeated traversal
            board[y][x] = '#'
            
            # visit next four neighbor grids
            found = dfs_search(idx + 1, x + 1, y) or dfs_search(idx + 1, x - 1, y) or dfs_search(idx + 1, x, y + 1) or dfs_search(idx + 1, x, y - 1)
            
            # recover original grid character after DFS is completed
            board[y][x] = cur
            
            return found

        # ------------------------------------------------------
        
        return any(dfs_search(0, x, y) for y in range(h) for x in range(w))      

接著看進階延伸題，改成找辭典裡面的單字，把有找到的列出來。

Word Search II - LeetCode 搜尋給定辭典中的單字

這題多了辭典，我們可以用之前學過前綴樹的技巧，先把辭典建成一顆Trie。

接著，同步在矩陣和Trie裡面搜索每個字元，假如在某一格可以在Trie中找到一個單字，就把這個單字加入到最終結果的清單中。

以DFS +N4探索框架的形式實現演算法，程式碼如下:

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        
        # Build a trie from given words
        trie = {}
        for word in words:
            curr = trie
            for c in word:
                if c not in curr:
                    curr[c] = {}
                curr = curr[c]
            curr['@'] = word

        H, W = len(board), len(board[0])
        
        res = []
        # ===========================================
        def dfs(r, c, trie):
            
            # Skip out-of-board search
            if not ( 0 <= r < H ) or not ( 0 <= c < W):
                return

            # Get current character on board
            ch = board[r][c]

            # Skip if current character does not exist in Trie
            if ch not in trie:
                return

            curr = trie[ch]
            word = curr.pop('@', None)
            if word:
                # We've found a word matched in Trie
                res.append(word)
            
            # Avoid repeated traversal
            board[r][c] = '#'
            
            dfs(r-1, c, curr)
            dfs(r+1, c, curr)
            dfs(r, c-1, curr)
            dfs(r, c+1, curr)
            board[r][c] = ch
            
            # Deleted empty trie branch
            if not curr:
                trie.pop(ch)
            
            return 
        # =========================================

        # Scan each position on board
        for r in range(H):
            for c in range(W):
                dfs(r, c, trie)
        
        return res

還有一個類似題，要求我們計算可以從起點走到終點，
而且可以拜訪所有空白格子點的路徑方法數

Unique Paths III - LeetCode 拜訪所有空白格子點的路徑方法數

其實也是類似的，我們可以先計算有幾個空白格子點。
接著從起點開始用DFS+N4拜訪整張棋盤，如果走到終點的時候，恰好拜訪過所有空白格子點，就把方法數累加一。最後的路徑方法數總數就是答案。

以DFS +N4探索框架的形式實現演算法，程式碼如下:

# Define grid state to make it more readable
 
 from collections import namedtuple
 GridState = namedtuple('GridState', 'start ending empty obstacle')
 grid_state = GridState( start = 1, ending = 2, empty = 0, obstacle = -1)
 
 
 class Solution:
     def uniquePathsIII(self, grid):
                 
         h, w = len( grid ), len( grid[0] )  
                                 
         available_grid_count = 0
         obstacle_count = 0
                                                         
         src_row, src_col = 0, 0 
                                                                         
      		# record for valid path
					# a path is valid if and only if it visits all available grid except for obstacles.
        self.valid_path_count = 0
        
        for y in range(h) :
            for x in range(w):
                
                if grid[y][x] == grid_state.obstacle:
											# update counter of obstacle
                    obstacle_count += 1
                    
                elif grid[y][x] == grid_state.start:
											# locate start point
                    src_row, src_col = y, x
        
					# compute counting of all available grids
        available_grid_count = h * w - obstacle_count
        
        # ------------------------------------------------------
        
        def dfs( cur_row, cur_col, depth):
            
            if not ( 0 <= cur_row < h) or not ( 0 <= cur_col < w ):
                # Skip out-of-board search
                return 
            if grid[cur_row][cur_col] == grid_state.obstacle:

                # Terminate DFS when bumping into an obstacle
                return
            
            elif grid[cur_row][cur_col] == grid_state.ending:

                if depth == available_grid_count:
                    
                    # If we reach end with visiting all available grids, update valid path count
                    self.valid_path_count += 1
                
                # Terminate DFS when reach ending
                return
            
            else:
                
                state_backup = grid[cur_row][cur_col]
				
				         # mark current grid as obstacle to avoid repeated visit
                grid[cur_row][cur_col] = grid_state.obstacle
                
                # DFS + N4 to discover each neighbor cell
                dfs( cur_row-1, cur_col, depth + 1)
                dfs( cur_row+1, cur_col, depth + 1)
                dfs( cur_row, cur_col-1, depth + 1)
                dfs( cur_row, cur_col+1, depth + 1)
                
                # restore original grid state
                grid[cur_row][cur_col] = state_backup
                
                return
            
        # ------------------------------------------------------
        
        dfs(src_row, src_col, depth = 1)
        return self.valid_path_count

結語

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

通用的DFS+N4探索框架，還有相關的路徑應用題與演算法建造，

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

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

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