Python：计算adj中已连接组件的数量。图的列表表示形式

Question

我正在尝试用python编写一个程序，该程序计算使用邻接表（python中的dict（））表示的图中的循环数（连接的组件）。

[基本上，我运行DFS并检查是否已访问相邻的顶点，并且该顶点不是当前顶点的父级。如果是这种情况，则该图中存在一个循环。然后，我计算这种情况发生的次数。

def count_cycles(graph, start, visited, count=0): 
    visited[start] = True
    for next in graph[start]:
        if not visited[next]:
            count_cycles(graph, next, visited, count)
        elif start != next:
            count += 1
    return count

if __name__ == "__main__":
    graph = {
        3: {10},
        4: {8},
        6: {3},
        7: {4, 6},
        8: {7},
        10: {6}
    }
    visited = [False] * (max(graph)+1)
    print(count_cycles(graph, 8, visited))

在示例中，输出应为2，但输出为1。我怀疑我的DFS存在问题，但我无法准确找出。

有什么建议吗？

Answer 1

知道了，您需要通过递归调用来更新计数。

def count_cycles(graph, start, visited): 
    visited[start] = True
    count = 0
    for next in graph[start]:
        if not visited[next]:
            count += count_cycles(graph, next, visited)
        elif start != next:
            count += 1
    return count

if __name__ == "__main__":
    graph = {
        3: {10},
        4: {8},
        6: {3},
        7: {4, 6},
        8: {7},
        10: {6}
    }
    visited = [False] * (max(graph)+1)
    print(count_cycles(graph, 8, visited))