python深度优先搜索递归

Question

我正在尝试使一个python dfs连接岛与递归。。。在

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

例如

o o o

o x x

o o o the output is 1 which is correct.

但是，在其他情况下

^{pr2}$

这是包含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）如果您想从dfs函数返回一个值，这个值应该有一些意义，应该使用它。如果您只调用函数的副作用，那么您就可以return而不加任何值。在本例中，dfs函数的目的是更新visited数组，因此不需要返回1或{}或任何东西。在

2）在图中进行深度优先搜索时，从一个节点开始，递归地访问其连接的节点。如果在dfs函数中有一个for循环，它访问了图形的大部分，忽略了连接，那么就不是在执行DFS。通常，您只需要在连接的节点上递归调用dfs函数。在

3）现在看来，函数在进行任何递归调用之前总是返回1。在

还要注意以下Python代码的良好实践：

1）避免像if expression == True:这样的结构。而是使用if expression:。也不要使用if expression == False，而是使用if not expression。在

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

3）在函数的顶部添加一个docstring，以描述该函数的作用（参见下面我的代码以获取示例）。在

据我所知，每次调用dfs函数时，都需要访问构成一个岛的所有连接的x。可以使用以下代码执行此操作：

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)