咨询：如何将节点邻居列表转换为连通节点组列表？

你可以用深度优先搜索（DFS）的递归实现来解决这个问题，核心思路是遍历每个节点，对未访问过的节点递归收集其所有连通的邻居，最终得到所有连通分量。

实现思路 #

1. 用布尔数组标记节点是否被访问过，避免重复处理
2. 遍历每个节点：
   • 如果节点未被访问，初始化一个空的连通组
   • 调用递归函数，深度优先遍历该节点的所有邻居，把连通的节点全部加入当前组，并标记为已访问
3. 把每个收集完成的连通组加入结果列表

代码示例 #

def find_connected_components(neighbors):
    visited = [False] * len(neighbors)
    components = []
    
    def dfs(node, component):
        visited[node] = True
        component.append(node)
        # 递归遍历所有未访问的邻居
        for neighbor in neighbors[node]:
            if not visited[neighbor]:
                dfs(neighbor, component)
    
    # 遍历所有节点，处理未访问的节点
    for node_idx in range(len(neighbors)):
        if not visited[node_idx]:
            current_component = []
            dfs(node_idx, current_component)
            components.append(tuple(current_component))
    return components

# 测试示例输入
input_neighbors = [(1, ), (0, ), (3, 4), (2, ), (2, )]
print(find_connected_components(input_neighbors))  # 输出: [(0, 1), (2, 3, 4)]

关键说明 #

• dfs递归函数负责深度探索当前节点的所有连通节点，确保不会遗漏任何属于同一组的节点
• visited数组是核心的去重机制，保证每个节点只会被加入一个连通组
• 最终结果将连通组转换为元组，和你给出的示例输出格式一致

内容的提问来源于stack exchange，提问作者smyril