我在学习算法,正在做这个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矩阵
错误是get是:
^{pr2}$谢谢!在
为什么不在用集合跟踪访问的顶点(学生)时只做一个标准的DFS?问题陈述说,矩阵的最大大小是200x200,所以你不必担心递归限制,假设它是1000。使用集合进行跟踪也会使代码更简单:
编辑有问题的代码看起来像是在执行DFS时将边视为顶点。这也解释了递归深度的问题,因为100个顶点的无向图有循环,但没有多条边,有最大(100*101)/2=5050条边。在
相关问题 更多 >
编程相关推荐