时间戳

首页 > 解决方案 > 需要帮助理解这个 python 深度优先搜索代码

python - 需要帮助理解这个 python 深度优先搜索代码

问题描述

我对 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 行开始，我很困惑，尤其是递归部分。 有人可以详细解释一下吗？通常，这类代码往往有一个队列/出队来记录该岛是否已被访问，但我认为这个代码没有那个？

标签： pythongraphdepth-first-search

解决方案

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

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

# 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)所有可能的值i，j然后选择最大计算值。

# inner layer - slightly modified
def dfs(i, j):
    # recursive case
    if (0 <= i <= row - 1 and 0 <= j <= col - 1) and grid[i][j] == 1:
        grid[i][j] = 0  # this is how we remember visited cells since we don't count zeros
        # optional prints to look at the grid during computation
        # print(i, j)
        # print(*grid, sep='\n', end='\n\n')
        count_current = 1
        count_neighbors = dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
        return  count_current + count_neighbors
    # trivial case and out-of-borders case
    else:
        return 0

内层稍微复杂一些。它能做什么？(1) 得到i和j。（2）如果单元格包含0那么它是微不足道的情况（水）或者我们不在网格中 - 只是 return 0。（3）如果单元格包含1，那么它是递归案例（土地） - 函数开始计算1与给定单元格相邻的所有单元格的数量，每个1计数都变成0以避免重复计算。

您的示例网格有 3 行（0、1、2）和 5 列（0、1、2、3、4）。假设我们在i = 0, j = 2。它是1。我们数一下（当前结果是1），把它变成0并一一查看它的邻居——上邻居在网格外，下邻居是0，左邻居是0，右邻居是1。我们不返回当前结果，而是继续到正确的邻居i = 0, j = 3。我们数一下（当前结果是 2），把它变成0并查看邻居。上邻居不在网格中，下邻居是1。我们停在这里，我们不返回当前结果，我们记得大约 2 个邻居，我们继续到底部邻居i = 1, j = 3。我们数一下（当前结果是3），把它变成0并查看邻居。上邻居是1. 我们停在这里，我们不返回当前结果，我们记得大约 3 个邻居，我们继续到上邻居i = 0, j = 3。等等。

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

推荐阅读