の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）dfs関数の値を返す場合は、この値には何らかの意味があり、それを使用する必要があります。副作用のために関数を呼び出すだけの場合は、値なしのreturnにすることができます。この場合、dfs関数の目的はvisited配列を更新することであるため、1または0などを返す必要はありません。

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関数の呼び出しごとに、島を構成するすべての接続された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)