PythonでのDFSの最適化

Question

私はアルゴリズムを学んでいて、これを実行してproblemが領域の数を見つけています。私はpythonを使用して深さの最初の検索アプローチを試みたが、呼び出しスタックを超過しているエラーを取得しています。誰も私の実装の欠陥とそれを克服する方法を教えてくれますか？コードは次のとおりです。

def findCircleNum(A): 

    count = 0 

    def dfs(row, column): 
     if row < 0 or column >= len(A[0]) or row >= len(A) or column < 0: 
      return 

     if A[row][column] == 0: 
      return 

     A[row][column] = 0 

     for i in range(row-1, row+2): 
      if i >= 0 and i<len(A) and A[i][column] == 1: 
       dfs(i, column) 
     for i in range(column-1, column+2): 
      if i >= 0 and i<len(A[0]) and A[row][i] == 1: 
       dfs(row, i) 




    for row in range(len(A)): 
     for column in range(len(A[0])): 
      if A[row][column] == 1: 
       dfs(row, column) 
       count += 1 


    return count 


findCircleNum(m) 

それが失敗し、エラーが取得され、すべて1の

の100x100の行列で入力されている：

RuntimeError: maximum recursion depth exceeded 

ありがとう！

Answer 1

訪問した頂点（学生）をセットで追跡しながら、標準のDFSを実行するだけではどうですか。問題文は行列の最大サイズは200×200であることを述べているので、あなたは再帰制限が追跡のためのセットを使用して、それが1000であると仮定すると心配する必要はないでしょうもコードがシンプルになります

def findCircleNum(A): 
    count = 0 
    visited = set() 

    def dfs(student): 
     if student in visited: 
      return 

     visited.add(student) 
     for i, friend in enumerate(A[student]): 
      if friend: 
       dfs(i) 

    for student in range(len(A)): 
     # Note we want to track circles, student without any friend won't count 
     if student not in visited and any(A[student]): 
      dfs(student) 
      count += 1 

    return count 

EDIT問題のコードは、DFSの実行中にエッジを頂点とみなしているようです。これはループなしでマルチエッジのない100頂点の無向グラフが最大（100 * 101）/ 2 = 5050のエッジを有するので、再帰深度に関する問題も説明する。