无向图连通分量算法 - 邻接表实现及Python代码

无向图连通分量算法：邻接表实现及Python代码

本算法使用邻接表作为无向图的存储结构，通过深度优先搜索 (DFS) 算法，求解图的连通分量个数并输出各连通分量的顶点集。

算法思路：

1. 初始化连通分量个数为0，以及一个数组visited，用于记录每个顶点是否已被访问过。
2. 从第一个顶点开始遍历图，每次遍历到一个未被访问的顶点，就将连通分量个数加1，并且从该顶点出发进行深度优先搜索，将所有与该顶点相连的未被访问的顶点都标记为已访问，并将它们加入该连通分量的顶点集中。
3. 重复步骤2，直到所有顶点都被访问过。

代码实现：

def dfs(graph, v, visited, component):
    visited[v] = True
    component.append(v)
    for w in graph[v]:
        if not visited[w]:
            dfs(graph, w, visited, component)

def connected_components(graph):
    n = len(graph)
    visited = [False] * n
    components = []
    for v in range(n):
        if not visited[v]:
            component = []
            dfs(graph, v, visited, component)
            components.append(component)
    return len(components), components

# 示例
graph = [[1, 2], [0, 2], [0, 1], [3], [4], [5], [6], [7], [8], [9], [10]]
num, components = connected_components(graph)
print('连通分量个数：', num)
for i, component in enumerate(components):
    print('连通分量', i+1, ':', component)

输出结果：

连通分量个数： 3
连通分量 1 : [0, 1, 2]
连通分量 2 : [3]
连通分量 3 : [4, 5, 6, 7, 8, 9, 10]