Optimierung von DFS in Python

Question

Ich lerne Algorithmen und machte dies problem, die die Anzahl der Regionen findet. Ich habe versucht eine Tiefensuche mit Python, aber ich bekomme einen Call-Stack-Fehler überschritten. Kann mir jemand sagen, was der Fehler in meiner Implementierung ist und wie man es überwinden kann? Der Code ist:

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) 

Die Eingangs es nicht auf eine 100x100-Matrix aller 1en

Der Fehler ist erhalten ist:

RuntimeError: maximum recursion depth exceeded 

Dank!

Answer 1

Warum nicht einfach ein Standard-DFS ausführen, während die besuchten Scheitelpunkte (Studenten) mit einem Set verfolgt werden? Das Problem Erklärung sagt, dass die maximale Größe der Matrix 200x200 ist, so dass Sie würde es 1000. Mit einem Satz für die Verfolgung keine Sorgen zu machen über die Rekursion Grenze unter der Annahme, auch der Code einfacher machen würde:

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 Der betreffende Code sieht so aus, als ob er Kanten als Vertices beim DFS betrachtet. Dies würde auch das Problem mit der Rekursionstiefe erklären, da ein ungerichteter Graph von 100 Scheitelpunkten mit Schleifen, aber keine Mehrecke, maximale (100 * 101)/2 = 5050 Kanten hat.