求带支点（Pivot）的Bron–Kerbosch算法正确迭代式（非递归、基于栈）伪代码

我完全理解你把递归版带支点的Bron–Kerbosch转成栈实现的痛苦——递归里的分支逻辑和支点优化在栈上很容易出错，你找到的那份伪代码确实存在几个关键问题，比如多余的Q参数、支点选择时机错误，这些都是导致你遇到空P报错的根源。

先帮你梳理原伪代码的核心问题：

• 多余的Q参数：递归版带支点的BK根本不需要这个参数，它是对递归分支的错误拆分，直接导致你混淆了初始值的设置；
• 支点选择时机错误：原伪代码在判断P/X是否为空之后才选支点，且没有判断P∪X是否为空就直接选u，必然会出现空集选支点的错误；
• 栈的入栈顺序错误：栈是后进先出结构，原代码的入栈顺序不符合递归调用的逻辑，会导致枚举顺序混乱。

下面是完全对齐递归版带支点BK逻辑的正确迭代式伪代码，附带详细解释：

// 迭代版带支点的Bron–Kerbosch算法，基于栈实现
// 输入：无向无权图Graph，N(v)表示顶点v的邻域集合（所有与v相连的顶点）
Iterative_BronKerbosch_Pivot(Graph)
    // 栈元素为三元组(R, P, X)：
    // R: 当前已构建的 clique（极大团候选）
    // P: 可加入R的候选顶点集
    // X: 已排除的顶点集（避免重复枚举相同团）
    Stack := empty stack
    all_vertices := 图中所有顶点的集合
    Stack.push( (R={}, P=all_vertices, X={}) )
    
    while Stack is not empty do
        // 弹出栈顶的当前状态
        current_R, current_P, current_X := Stack.pop()
        
        // 若候选集和排除集都为空，说明current_R是一个极大团
        if current_P is empty and current_X is empty then
            report current_R as a maximal clique
            continue
        
        // 选择支点u：从current_P ∪ current_X中选取（优化分支数量）
        // 推荐选度数最高的顶点，也可以选任意顶点
        pivot_u := null
        union_PX := current_P ∪ current_X
        if union_PX is not empty then
            pivot_u := 从union_PX中选择一个顶点
        
        // 生成候选顶点列表：current_P中不在pivot_u邻域的顶点（支点优化核心）
        if pivot_u is not null then
            candidates := current_P \ N(pivot_u)
        else
            candidates := current_P
        
        // 遍历每个候选顶点v，生成两个分支入栈
        for each v in candidates do
            // 分支1：不选择v，将v从候选集移到排除集
            new_R_no_v := current_R
            new_P_no_v := current_P \ {v}
            new_X_no_v := current_X ∪ {v}
            // 先入栈不选v的分支（栈后进先出，保证后入的选v分支先被处理）
            Stack.push( (new_R_no_v, new_P_no_v, new_X_no_v) )
            
            // 分支2：选择v，将v加入current_R，候选集/排除集取与v邻域的交集
            new_R_with_v := current_R ∪ {v}
            new_P_with_v := current_P ∩ N(v)
            new_X_with_v := current_X ∩ N(v)
            Stack.push( (new_R_with_v, new_P_with_v, new_X_with_v) )
            
            // 从当前候选集中移除v，避免重复处理
            current_P := current_P \ {v}

关键细节说明 #

1. 初始状态：完全对应递归版的初始调用，没有多余参数——R为空，P是所有顶点，X为空，解决你之前对Q参数的困惑；
2. 支点选择逻辑：只有当current_P ∪ current_X不为空时才选支点，彻底避免空集选u的错误；
3. 栈顺序控制：先push“不选v”的分支，再push“选v”的分支，保证弹出时先处理选v的情况，和递归调用顺序完全一致；
4. 支点优化作用：通过只遍历current_P \ N(pivot_u)的顶点，能大幅减少重复分支，这也是带支点版本比基础版本效率更高的核心原因。

实现小建议 #

• 集合操作（交集、差集、并集）推荐用哈希集合或位集实现，提升大图处理效率；
• 支点选择可以优化为选current_P ∪ current_X中度数最高的顶点，能最大程度减少分支数量；
• 测试时先用小图验证，比如三角形、完全图，确认能正确枚举所有极大团。

备注：内容来源于stack exchange，提问作者ttnphns