在Python中優化DFS

我正在學習算法，並正在這樣做problem這是找到區域的數量。我嘗試使用python深度優先搜索方法，但我得到一個調用堆棧超過錯誤。任何人都可以告訴我，我的實施有什麼缺陷，以及如何克服它？該代碼是：在Python中優化DFS

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)

失敗的是100x100的矩陣全部爲1

的錯誤就是讓輸入：

RuntimeError: maximum recursion depth exceeded

謝謝！

來源

2017-09-05 Salmaan P

這不是DFS ...提示：你的DFS函數不會返回任何東西。 – alfasin

我正在改變矩陣。它適用於較小的輸入。你能告訴我我離開的地方嗎？ –

更改矩陣如何幫助您找到連接組件的數量？ – alfasin

爲什麼不直接用一組跟蹤訪問頂點（學生）時執行標準的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

編輯有問題的代碼看起來像是在做DFS時將邊看作頂點。這也可以解釋遞歸深度的問題，因爲具有循環但沒有多點的100個頂點的無向圖具有最大（100 * 101）/ 2 = 5050邊緣。

來源

2017-09-05 08:21:34 niemmi

好吧，我現在明白了。我手動查看每個單元格，並在我們可以佔用整行時對其鄰居執行DFS，因爲它像鄰接列表一樣工作。只是好奇，是我做了適當的DFS或者它是一個錯誤的實現？ –

@SalmaanP圖形表示法被稱爲[鄰接矩陣]（https://en.wikipedia.org/wiki/Adjacency_matrix）。你在做什麼看起來更像是把邊看作頂點。 – niemmi

謝謝，我看到我困惑的地方。我的方法可以在這裏顯示的正常矩陣上工作嗎？https://www.youtube.com/watch?v=R4Nh-EgWjyQ？ –

在Python中優化DFS

回答

相關問題