現在我們介紹圖論 (Graph Theory) 相關題目

這道題是網格類問題的基礎，也是學習BFS、和DFS的經典題目。

題目連結: 200. Number of Islands

題目描述:給你一個由 '1' (陸地) 和 '0' (水) 組成的 m x n 二維網格 grid。一個「島嶼」是由水平或垂直方向上相鄰的 '1' 連接而成的區域。你可以假設網格的四個邊緣都被水包圍。
請計算網格中島嶼的數量。

Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
上面這個例子中有 1 個獨立的島嶼。

Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
上面這個例子中有 3 個獨立的島嶼。

Python

解題思路:

1. 網格中的每一個 '1' 都是一個節點 (Node)。
2. 兩個水平或垂直相鄰的 '1' 之間有一條邊 (Edge)。

我們的目標就是找出有幾個這樣互相連接的「1 的集群」。

下面程式碼用DFS方法來做介紹。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        r, c = len(grid), len(grid[0])
        def bfs(row,col):
            if 0<=row<r and 0<=col<c and grid[row][col] == '1':
                grid[row][col] = '0'
            else:
                return
            bfs(row+1,col)
            bfs(row-1,col)
            bfs(row,col+1)
            bfs(row,col-1)
        count = 0
        for i in range(r):
            for j in range(c):
                if grid[i][j] == '1':
                    bfs(i,j)
                    count += 1
        return count

演算法分析:

• 創建一個count計算總島嶼數。
• 用巢狀迴圈，從左上角 (0, 0) 開始，逐一檢查是不是等於 '1' 。
• 如果遇到一個值為 '1' 時，將島嶼計數器 count 加 1、以當前的座標 (i, j) 為起點，呼叫 dfs(i, j) 函式。
• 首先檢查傳入的座標 (row, col) 是否在區間內，或者該位置是否為'0'。直接返回上一個位置(如果當前grid[2][0]= '0'時，回到grid[1][0])，向四周擴散對當前位置的上、下、左、右四個相鄰的元素，分別再次呼叫 dfs 函式，重複此過程。

複雜度分析:

• 時間複雜度為 O(m * n)。

  1. 演算法的主體是巢狀迴圈，它會遍歷每一個元素。陣列的大小為 m 行 n 列，所以這部分是 m * n 次操作。
  2. dfs 函式雖然是遞迴的，不過只有當grid[row][col] = '0'，不會再觸發新的 dfs 呼叫。

• 空間複雜度： O(m * n) (空間消耗主要來自於遞迴呼叫的堆疊)。

第一次做這類有點陌生
有問題可以底下留言!
下回見!!