需要帮助理解这个python深度优先搜索cod吗

Question

我对Python编码很陌生，很难理解下面的代码。它是在图论上使用DFS来寻找所有岛屿区域中最大的面积。1表示岛屿，0表示栅格中的水。在

def maxAreaOfIsland(grid):
    row, col = len(grid), len(grid[0])
    def dfs(i, j):
        if 0 <= i <= row - 1 and 0 <= j <= col - 1 and grid[i][j]:
            grid[i][j] = 0

#scans through all rows & cols and 
#turns number in the grid into 0 if all conditions are true?

            return  1 + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
        return 0  

# recursive function that checks up, down, left, right in the grid. 
# when does it return 1?

    return max(dfs(i, j) for i in range(row) for j in range(col))

maxAreaOfIsland([[1,0,1,1,1],
                 [0,0,0,1,1],
                 [1,1,1,0,1]]) 
Out: 6

我已经写了一些评论，这些评论反映了我到目前为止的理解，但不确定它是否正确。从第4行开始，我很困惑，尤其是递归部分。 有人能详细解释一下吗？通常这类代码都会有一个队列/出列来记录是否有人访问过这个岛屿，但我不认为这类代码有这个功能？在

Answer 1

我想问题其实是关于理解算法而不是Python。提供的Python代码非常简单。在

代码包含函数maxAreaOfIsland，该函数又包含递归函数dfs。这两个函数构成两个计算层。让我们分别看看这些层。在

# outer layer
def maxAreaOfIsland(grid):
    row, col = len(grid), len(grid[0])
    # function dfs() definition
    return max(dfs(i, j) for i in range(row) for j in range(col))

所以外层非常简单-计算所有可能的dfs(i, j)和{}，然后选择最大计算值。在

^{pr2}$

内层要复杂一点。它的作用是什么？（1） 它得到i和{}。（2） 如果单元格包含0，那么这是一个很小的例子（水），或者我们超出了网格-只需返回0。（3） 如果单元格包含1，那么它的递归case（land）-函数开始计算给定单元格相邻的所有1的数量，并将每个计数的1转换为{}，以避免重复计数。在

示例网格有3行（0、1、2）和5列（0、1、2、3、4）。假设我们在i = 0, j = 2。它是1。我们对它进行计数（当前结果是1），把它变成0，然后逐个查看它的邻居——上邻居在网格之外，下邻居是0，左邻居是{}，右邻居是{}。我们不返回当前结果，而是转到右相邻的i = 0, j = 3。我们计算它（cuurent结果是2），把它变成0并查看邻居。上邻居超出网格，下邻居是1。我们到此为止，我们不返回当前结果，我们记住了另外两个邻居，我们继续到最下面的邻居i = 1, j = 3。我们计算它（当前的结果是3），把它变成0并查看邻居。上邻居是1。我们到此为止，我们不返回当前结果，我们记住了另外3个邻居，我们继续到上面的邻居i = 0, j = 3。等等。在

我的建议是绘制简单的示例网格（用笔在一张纸上）并手动应用dfs算法。在