如何获取连通图所有划分块内部连通的节点划分结果？

你要找的这类划分叫做图的连通划分，要求每个划分块对应的诱导子图都是连通的，无需生成所有Bell数对应的全量划分再筛选，可以用更高效的回溯枚举方法直接生成合法结果：

核心思路 #

• 先给所有节点固定一个全局排序，比如按节点编号升序排列，核心逻辑是每次优先处理当前未分配的最小序号节点，避免生成重复的划分（同一划分的不同块顺序不会被重复计数）。
• 对当前处理的最小未分配节点 x，枚举所有满足以下条件的子集 S：
  1. x 属于 S
  2. S 中的所有节点都是未分配状态
  3. S 对应的诱导子图是连通的
• 每选一个合法的 S 作为划分块，就把 S 里的节点标记为已分配，递归处理剩余的未分配节点，直到所有节点都被分配，就得到一个合法划分。

连通子集枚举方法 #

枚举包含节点 x 的所有未分配连通子集，可以用小的回溯逻辑实现：

1. 初始时子集 S = {x}，标记为待扩展
2. 每次遍历当前 S 所有节点的邻接节点，把还没有加入 S 的未分配节点作为候选加入，生成新的连通子集
3. 每生成一个新的连通子集就可以作为候选划分块，继续扩展直到没有可加入的节点为止

示例验证 #

以你给出的4节点示例为例，初始未分配节点是p1、p2、p3、p4，最小节点是p1：

• 第一次枚举包含p1的连通子集，可选的包括 {p1}、{p1,p2}、{p1,p3}、{p1,p2,p3} 等
  • 当选 S={p1,p2,p3} 时，剩余未分配节点只有p4，递归后得到划分 {p1,p2,p3}{p4}
  • 当选 S={p1,p2} 时，剩余未分配节点是p3、p4，最小节点是p3，枚举包含p3的连通子集可以选 {p3,p4}，得到划分 {p1,p2}{p3,p4}
  • 当选 S={p1,p3} 时，剩余未分配节点是p2、p4，最小节点是p2，只能选 {p2}，最后剩余p4选 {p4}，得到划分 {p1,p3}{p2}{p4}
    和你给出的示例结果完全匹配。

参考实现（Python） #

def get_connected_partitions(graph):
    # graph是邻接表，key是节点，value是相邻节点列表
    nodes = sorted(graph.keys())
    n = len(nodes)
    node_to_idx = {node:i for i, node in enumerate(nodes)}
    result = []
    
    def backtrack(unused_mask, current_partition):
        if unused_mask == 0:
            result.append(current_partition.copy())
            return
        # 找最小的未使用节点
        min_idx = (unused_mask & -unused_mask).bit_length() - 1
        min_node = nodes[min_idx]
        # 枚举所有包含min_node的未使用连通子集
        def dfs_subset(s_mask, s_nodes):
            # 先把当前子集作为划分块，递归处理剩下的
            backtrack(unused_mask ^ s_mask, current_partition + [s_nodes.copy()])
            # 找可以加入的节点：和s_mask里的节点相邻，且在unused_mask里，不在s_mask里
            candidates = 0
            temp = s_mask
            while temp:
                idx = (temp & -temp).bit_length() -1
                node = nodes[idx]
                for neighbor in graph[node]:
                    n_idx = node_to_idx[neighbor]
                    if (unused_mask & (1 << n_idx)) and not (s_mask & (1 << n_idx)):
                        candidates |= (1 << n_idx)
                temp ^= (1 << idx)
            # 遍历候选节点加入
            while candidates:
                c = (candidates & -candidates).bit_length() -1
                candidates ^= (1 << c)
                dfs_subset(s_mask | (1 << c), s_nodes + [nodes[c]])
        
        dfs_subset(1 << min_idx, [min_node])
    
    backtrack((1<<n) -1, [])
    return result

# 示例调用，匹配你的测试场景
graph = {
    'p1': ['p2', 'p3'],
    'p2': ['p1', 'p3'],
    'p3': ['p1', 'p2', 'p4'],
    'p4': ['p3']
}
partitions = get_connected_partitions(graph)
for p in partitions:
    print([set(block) for block in p])

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