python 深度优先搜索递归

Question

我正在尝试用递归制作一个 python dfs 连接岛...

程序运行良好，但在某些情况下会出现输出不正确的逻辑错误

例如

o o o

o x x

o o o the output is 1 which is correct.

但是，在其他情况下

o x o

o x o

o o o the output is 2 which is incorrect.

这是包含 dfs 函数的完整代码

row = int(input("Enter Row : "))
col = int(input("Enter Col : "))

# declare array baru namanya peta
peta = []

# array 2 dimensi
# Masukkin smua input ke array petas
for i in range(0,row):
    line = input()
    peta.append(line)


store = []
# declare array baru nama visited
visited = []
for i in range(0,row):
    visited.append([])

    # buat column di row i false smua
    for j in range(0,col):
        visited[i].append(False)

def dfs(i,j):
    visited[i][j] = True
    a = row-1
    b = col-1
    #peta[i][j] = store[a][b]
    for i in range(i,row):
        for j in range(j,col):
            if(visited[i][j] == True):
                return 1
            else:
                if(peta[i][j] == 'x' and visited[i][j] == False ):                  
                    #top left array
                    if(i == 0 or j == 0):
                        dfs(i+1,j+1)
                        dfs(i+1,j)
                        dfs(i,j+1)                  

                    #bottom left array
                    elif(i == a and j == 0):
                        dfs(i-1,j)
                        dfs(i-1,j+1)
                        dfs(i,j+1)

                    #top right array
                    elif(i == 0 and j == b):
                        dfs(i,j-1)
                        dfs(i+1,j-1)
                        dfs(i+1,j)

                    #bottom right array
                    elif(i == a and j == b):
                        dfs(i,j-1)
                        dfs(i-1,j-1)
                        dfs(i-1,j)

                    #west array
                    elif(i >= 1 and j == 0):
                        dfs(i-1,j)
                        dfs(i-1,j+1)
                        dfs(i+1,j)
                        dfs(i,j+1)
                        dfs(i+1,j+1)

                    #north array
                    elif(i==0 and j>=1):
                        dfs(i,j-1)
                        dfs(i+1,j-1)
                        dfs(i+1,j)
                        dfs(i,j+1)
                        dfs(i+1,j+1)

                    #east array
                    elif(i>=1 and j==b):
                        dfs(i-1,j)
                        dfs(i-1,j-1)
                        dfs(i,j-1)
                        dfs(i+1,j-1)
                        dfs(i+1,j)

                    #south array
                    elif(i==a and j>=1):
                        dfs(i,j-1)
                        dfs(i-1,j-1)
                        dfs(i-1,j)
                        dfs(i-1,j+1)
                        dfs(i,j+1)

                    #middle array
                    else:
                        dfs(i-1,j-1)
                        dfs(i-1,j)
                        dfs(i-1,j+1)
                        dfs(i,j-1)
                        dfs(i,j+1)
                        dfs(i+1,j-1)
                        dfs(i+1,j)
                        dfs(i+1,j+1)

                else:
                    #peta[i][j] = 0
                    return 0

numberofisland = 0
for i in range(0,row):
    for j in range(0,col):
        if((peta[i][j] == 'x' and visited[i][j] == False)):
            dfs(i,j)
            numberofisland+=1





print(numberofisland)

在我看来，我的逻辑错误是我访问了访问节点两次，但是我的数组似乎没有错误。你能就我的错误在哪里提出一些建议吗？

非常感谢您的宝贵时间，干杯

编辑：我已按照社区要求更新为完整代码版本（如何调用函数、全局变量等）

Answer 1

您的代码中有些地方没有意义：

1) 如果你想return一个来自dfs函数的值，这个值应该有一些意义并且应该被使用。如果你只是因为它的副作用而调用一个函数，那么你可以 return 没有任何价值。在这种情况下，在我看来 dfs 函数的目的是更新 visited 数组，因此您不需要 return 1 或 0 或任何东西。

2) 当你在图中进行深度优先搜索时，你从一个节点开始，然后递归地访问它连接的节点。如果您在 dfs 函数中有一个 for 循环，它访问了图的大部分，忽略了连接，那么您就没有在进行 DFS。一般只需要在连接的节点上递归调用dfs函数即可。

3) 你的函数现在的样子，似乎总是 return 1 在进行任何递归调用之前。

另请注意 Python 代码的以下良好做法：

1) 避免像 if expression == True: 这样的结构。而是使用 if expression:。也可以使用 if not expression.

而不是 if expression == False

2) 避免在 if 和 elif 子句中的条件表达式周围使用括号，这不是必需的，不像 C 或 Java。例如，使用 elif a == b.

而不是 elif (a == b):

3) 在函数的顶部添加一个 docstring 来描述函数的作用（示例请参见下面我的代码）。

据我了解，您希望 dfs 函数的每次调用都访问所有连接的 xs，形成一个岛。您可以使用以下代码执行此操作：

def dfs(i,j):
    '''
    This function starts from the square with coordinates (i,j).

    The square (i,j) should be an 'x', and also unvisited.

    This function will keep visiting all adjacent 'x' squares, using a
    depth first traversal, and marking these squares as visited in the
    @visited array.

    The squares considered adjacent are the 8 surrounding squares:
    (up, up-right, right, down-right, down, down-left, left, up-left).
    '''

    # The range checks have been moved to the beginning of the function, after each call.
    # This makes the code much shorter.
    if i < 0 or j < 0 or i >= row or j >= col:
        return

    # If we reached a non-x square, or an already visited square, stop the recursion.
    if peta[i][j] != 'x' or visited[i][j]:
        # Notice that since we don't do something with the return value,
        # there is no point in returning a value here.
        return

    # Mark this square as visited.
    visited[i][j] = True

    # Visit all adjacent squares (up to 8 squares).
    # Don't worry about some index falling out of range,
    # this will be checked right after the function call.
    dfs(i-1,j-1)
    dfs(i-1,j)
    dfs(i-1,j+1)
    dfs(i,j-1)
    dfs(i,j+1)
    dfs(i+1,j-1)
    dfs(i+1,j)
    dfs(i+1,j+1)

python 深度优先搜索递归

python depth-first search recursion

python

recursion

microsoft-distributed-file-system