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))

Python: 计算adj中连通分量的个数。图表的列表表示

Python: Counting number of connected components in adj. list representation of graph

python

graph-theory

depth-first-search

connected-components