邻接表存储的无向图求连通分量个数并输出各连通分量的首顶点

邻接表是一种常用的图数据结构，它通过链表将每个顶点与其相邻的所有顶点相连。要计算无向图的连通分量，并输出每个连通分量的首顶点，可以按照以下步骤操作：

1. 初始化：遍历整个图，为每个顶点分配一个唯一的标识符（例如序号），并将其添加到对应的集合或数组中。

2. 分割过程：从任意一个顶点开始，进行深度优先搜索（DFS）或广度优先搜索（BFS）。在搜索过程中，遇到的新顶点如果不在当前的集合内，则说明发现了一个新的连通分量。每次进入一个新的连通分量，就新建一个集合来存放该部分顶点，并记录下这个集合的第一个元素作为首顶点。

3. 记录结果：在搜索结束后，所有集合就是连通分量，集合的第一个元素即为对应连通分量的首顶点。统计集合的数量，即得连通分量的总数。

4. 输出结果：遍历所有的连通分量集合，打印出每个集合的第一个顶点。

以下是伪代码示例：

def find_connected_components(adjacency_list):
    components = []
    visited = set()

    def dfs(vertex):
        if vertex not in visited:
            visited.add(vertex)
            component.append(vertex)
            for neighbor in adjacency_list[vertex]:
                dfs(neighbor)

    for vertex, neighbors in adjacency_list.items():
        if vertex not in visited:
            component = [vertex]
            dfs(vertex)
            components.append(component)

    return len(components), [(component[0], component) for component in components]

# 示例
components_count, component_heads = find_connected_components(graph_adjacency_list)
for i, head in enumerate(component_heads):
    print(f"连通分量 {i+1} 的首顶点: {head}")