在了解一個資料結構，一定是先從如何遍歷資料結構開始，懂得如何遍歷資料結構的過程中，也會更了解資料結構的架構。
先前在樹的文章中有稍稍提到，深度搜尋和廣度搜尋，這個概念比較正式被提及通常是圖論會用到這兩個字。
讓我們用這篇來比較深度搜尋和廣度搜尋在圖論中展現出來的樣貌。

Number of Islands

題目會給一個二維陣列，0 表示海，1 表示陸地，如果 1 十字方向相連到其他的 1，表示是同一塊島嶼。
回傳二維陣列裡的島嶼數量。
這是題目中的第二個範例。

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

這個範例裡就有三個島嶼，一個由 4 個 1 組成，兩個由 1 個 1 組成，這題不在意島嶼面積，所以只要回傳 3 即可。

在走訪這種類型由二維陣列構成的圖的時候，一般就需要用到紀錄矩陣來標示已經走過的地方。
當然，如果在修改原矩陣也不會造成錯誤的時候，也可以直接修改原本的矩陣。
紀錄矩陣的大小會和表示圖的二維矩陣一模一樣，型別通常是 bool，因為 bool 的預設值是 false，所以初始化後，一張和表示圖的矩陣大小相等、全部為 false 的矩陣就有了， false 表示尚未走過，走過後就標示為 true。
每次造訪該座標時，都先確認該位置是否已經走過，避免重複處理到同樣的位置。

以這題來說，我們關心的是 1 有哪些，大可直接把走過的 1 填成 0，因為已經走過，也不會再度走訪。填成 0 在條件上，我們本來就會忽略它(因為是海洋，我們只在乎島嶼)。

一開始，我們會從左上到右下開始逐格遍歷，當找到第一個陸地後，我們開始用本篇的主題：深度優先搜尋或廣度優先搜尋來尋找相連的陸地(後文都會直接簡稱 DFS 和 BFS)。

深度優先搜尋(DFS)

深度優先的概念是，我們先往一個方向一直探尋，直到走到終止條件(如碰到邊界)，再回退一步，看有沒有其他能走的地方，沒了就再回退，再看有沒有其他能走的。
以樹的結構來看，就像會一直往下直到碰到葉子節點為止，然後逐次退層往上，每次往上退層前，都會先把該層其他可能都確認過才回退。因為先一直往某個方向鑽，直到碰到邊界，所以稱作深度優先。

廣度優先搜尋(BFS)

廣度優先的概念是，我們在一個位置時，下一步有 n 個可能性，則我們平等的往 n 個可能性都往前進一步，並把這 n 步的可能性都加入待處理清單。以二維陣列表示圖來看，就像同時往上下左右走一步做探尋。
以樹的概念，層級遍歷就是廣度優先，在每個可能的路徑都同時移動同樣的距離。

依據測試資料與題目類型，兩種方法各有不同的優勢。
但大多的題目兩種寫法都能寫，也都解的出來，練習的時候可以以自己手順或題目寫起來比較輕鬆的那種來寫，有餘力再想想另一種的話要怎麼寫。
我們今天以這題展示一下兩個程式碼分別的樣貌。

DFS

public class Solution {
    public int[][] dirs = new int[][]{
        new int[]{ 0,  1},
        new int[]{ 0, -1},
        new int[]{ 1,  0},
        new int[]{-1,  0}
    };
    public int NumIslands(char[][] grid) {
        var count = 0;
        for(var i = 0; i < grid.Length; i++){
            for(var j = 0; j < grid[0].Length; j++){
                if(grid[i][j] == '1'){
                    DFS(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public void DFS(char[][] grid, int row, int col){
        if(row < 0 || col < 0 || row >= grid.Length || col >= grid[0].Length || grid[row][col] == '0'){
            return;
        }
        grid[row][col] = '0';
        foreach(var dir in dirs){
            DFS(grid, row - dir[0], col - dir[1]);
        }
    }
}

BFS

public class Solution {
    public int[][] dirs = new int[][]{
        new int[]{ 0,  1},
        new int[]{ 0, -1},
        new int[]{ 1,  0},
        new int[]{-1,  0}
    };
    public int NumIslands(char[][] grid) {
        var count = 0;
        var q = new Queue<(int,int)>();
        for(var i = 0; i < grid.Length; i++){
            for(var j = 0; j < grid[0].Length; j++){
                if(grid[i][j] == '1'){
                    count++;
                    //BFS start
                    q.Enqueue((i,j));
                    while(q.TryDequeue(out (int,int) node)){
                        if(node.Item1 < 0 || node.Item2 < 0 ||
                         node.Item1 >= grid.Length || node.Item2 >= grid[0].Length ||
                         grid[node.Item1][node.Item2] == '0'){
                             continue;
                         }
                        grid[node.Item1][node.Item2] = '0';
                        foreach(var dir in dirs){
                            q.Enqueue((node.Item1 - dir[0], node.Item2 - dir[1]));
                        }
                    }          
                    //BFS end          
                }
            }
        }
        return count;
    }
}

程式碼回顧

我想把兩個的說明寫在一起，原理的部分上面已經分開寫了，把兩個的說明放在一起方便比較。

首先，我們先講通用的技巧： dirs 二維陣列，在由二維陣列構成的圖裡，我們常常需要四方向(或八方向)的去探索，透過宣告一個方向對行列的變量，搭配上 foreach，就能讓程式碼乾乾淨淨的去遍歷需要的方向。
同時，為避免放入前就進行邊界檢測，會讓放入邏輯變的比較醜，我們統一在進入的第一時間，尚未套用索引查詢陣列時，先檢查索引值是否在恰當的邊界裡，否則也當作終止條件結束探索。
這兩個小技巧讓我們的程式碼在二維陣列往個方向探索的寫法能保持乾淨好讀。

DFS 的相關內容很單純的包在了 DFS 的函式裡，我們透過傳入題目的二維陣列(作為資料源)和當前造訪的位置的座標，以 DFS 的概念去做遞迴，因為深度優先的寫法多為遞迴，所以才會像這樣另外定義一個函式。這題走訪的處理上，如上面提到的，我是用把走過的陸地變為海洋來避免再度走訪，這樣可省下一個造訪矩陣的空間。

BFS 的部分沒有額外開一個 BFS 函式，因為不需要，不是用遞迴的寫法。BFS 具體的程式碼範圍我用註解寫明了。一如樹結構中的層級遍歷，我們這邊選用 queue 來作為訪問順序控制，當然別的型別也行，就看合適跟個人順手的，我這邊就先用 queue。可以看到我們遍歷到每個點，就是直接把四方向加入了下次遍歷清單，就是上面敘述的廣度優先概念。

透過這提，我展示了 DFS 和 BFS 如何用在二維陣列構成的圖去做結構走訪，並以填陸為海的方式說明造訪矩陣，這些都是圖遍歷的基本概念，明天再讓我們來看一些更複雜的圖的相關題目。