优化Python中的DFS算法

Question

优化Python中的DFS算法

3

我正在学习算法，并在解决这个问题，该问题是找到区域的数量。我尝试使用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

谢谢！

- Salmaan P

这不是深度优先搜索（DFS）...提示：你的DFS函数没有返回任何内容。 - Nir Alfasi

我正在原地更改矩阵。对于较小的输入有效。您能告诉我哪里出了问题吗？ - Salmaan P

改变矩阵如何帮助您找到连通组件的数量？ - Nir Alfasi

如果单元格的值为1，我将其更改为0，然后对其邻居执行DFS。更改它可以确保不会再次遇到相同的单元格。希望这样说得清楚。 - Salmaan P

对不起，我应该说独立组件而不是连接组件。它是在矩阵中查找区域的数量。在第一个dfs调用完全完成后，所有直接连接的1将变为0，这使得这个组件成为一个点，此时我会增加计数。这个链接有完整的问题陈述https://leetcode.com/problems/friend-circles - Salmaan P

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- niemmi · Accepted Answer

为什么不使用标准DFS，同时使用集合来跟踪访问的顶点（学生）呢？问题陈述表明矩阵的最大大小为200x200，因此假设递归限制为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

编辑问题中的代码似乎在进行深度优先搜索时将边缘视为顶点。这也可以解释递归深度的问题，因为具有循环但没有多重边的100个顶点的无向图最多有（100 * 101）/ 2 = 5050条边。