Python中有没有简单方法可以查找所有互相连通的节点？

实现思路 #

• 先构建双向邻接表：给出的连接关系为单向键值对，补充反向关联保证连通性遍历逻辑正确
• 用集合记录已访问节点，避免重复计算
• 对每个未访问的节点启动深度优先遍历，收集所有连通节点作为一个独立分组

完整代码 #

def demo(A, B):
    # 初始化双向邻接表
    adj = {node: [] for node in A}
    for u, v in B.items():
        adj[u].append(v)
        adj[v].append(u)
    
    visited = set()
    result = []
    
    # 深度优先遍历收集连通节点
    def dfs(node, current_group):
        visited.add(node)
        current_group.append(node)
        for neighbor in adj[node]:
            if neighbor not in visited:
                dfs(neighbor, current_group)
    
    # 遍历所有节点生成分组
    for node in A:
        if node not in visited:
            group = []
            dfs(node, group)
            result.append(group)
    return result

测试验证 #

A = ['node1', 'node2', 'node3', 'node4', 'node5']
B = {'node1':'node2', 'node3':'node4', 'node4':'node5'}
print(demo(A, B))
# 输出：[['node1', 'node2'], ['node3', 'node4', 'node5']]

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