# 查找島嶼數| 系列 1（使用 DFS） > 原文： [https://www.geeksforgeeks.org/find-number-of-islands/](https://www.geeksforgeeks.org/find-number-of-islands/) 給定布爾 2D 矩陣，找到孤島的數量。 一組相連的 1 組成一個島。 例如，下面的矩陣包含 5 個島 **示例**： ``` Input : mat[][] = {{1, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {1, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {1, 0, 1, 0, 1} Output : 5 ``` 這是標準問題的變體：“計算無向圖中的已連接組件數”。 在解決問題之前，讓我們了解什么是連接的組件。 無向圖的[連接組件](https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/)是子圖，其中每兩個頂點通過一條路徑相互連接，并且不與子圖外部的其他頂點連接。 例如，下面的圖形具有三個連接的組件。  所有頂點相互連接的圖具有一個完整的連接組件，該組件由整個圖組成。 這樣的僅具有一個連接組件的圖稱為強連接圖。 通過在每個組件上應用 DFS（）可以輕松解決該問題。 在每個 DFS（）調用中，都會訪問組件或子圖。 我們將在下一個未訪問的組件上調用 DFS。 調用 DFS（）的次數給出了已連接組件的數量。 也可以使用 BFS。 ***什么是島嶼？*** 一組相連的 1s 形成一個島。 例如，下面的矩陣包含 4 個島  ## [Recommended: Please solve it on “***PRACTICE***” first, before moving on to the solution.](https://practice.geeksforgeeks.org/problems/find-the-number-of-islands/1) 2D 矩陣中的一個單元可以連接到 8 個鄰居。 因此，與標準 DFS（）不同，在該標準中我們遞歸地調用所有相鄰的頂點，而在這里我們只能遞歸地調用 8 個鄰居。 我們會跟蹤已訪問的 1，以便不再對其進行訪問。 ## C++ ```cpp // C++ Program to count islands in boolean 2D matrix #include <bits/stdc++.h> using namespace std; #define ROW 5 #define COL 5 // A function to check if a given // cell (row, col) can be included in DFS int isSafe(int M[][COL], int row, int col, ???????????bool visited[][COL]) { ????// row number is in range, column ????// number is in range and value is 1 ????// and not yet visited ????return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] && !visited[row][col]); } // A utility function to do DFS for a // 2D boolean matrix. It only considers // the 8 neighbours as adjacent vertices void DFS(int M[][COL], int row, int col, ?????????bool visited[][COL]) { ????// These arrays are used to get ????// row and column numbers of 8 ????// neighbours of a given cell ????static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; ????static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; ????// Mark this cell as visited ????visited[row][col] = true; ????// Recur for all connected neighbours ????for (int k = 0; k < 8; ++k) ????????if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)) ????????????DFS(M, row + rowNbr[k], col + colNbr[k], visited); } // The main function that returns // count of islands in a given boolean // 2D matrix int countIslands(int M[][COL]) { ????// Make a bool array to mark visited cells. ????// Initially all cells are unvisited ????bool visited[ROW][COL]; ????memset(visited, 0, sizeof(visited)); ????// Initialize count as 0 and ????// travese through the all cells of ????// given matrix ????int count = 0; ????for (int i = 0; i < ROW; ++i) ????????for (int j = 0; j < COL; ++j) ????????????// If a cell with value 1 is not ????????????if (M[i][j] && !visited[i][j]) { ????????????????// visited yet, then new island found ????????????????// Visit all cells in this island. ????????????????DFS(M, i, j, visited); ????????????????// and increment island count ????????????????++count; ????????????} ????return count; } // Driver code int main() { ????int M[][COL] = { { 1, 1, 0, 0, 0 }, ?????????????????????{ 0, 1, 0, 0, 1 }, ?????????????????????{ 1, 0, 0, 1, 1 }, ?????????????????????{ 0, 0, 0, 0, 0 }, ?????????????????????{ 1, 0, 1, 0, 1 } }; ????cout << "Number of islands is: " << countIslands(M); ????return 0; } // This is code is contributed by rathbhupendra ```