基于邻接矩阵的补图实现方法与伪代码补全求教

首先明确补图和邻接矩阵的对应规则：对于n个顶点的图，除顶点与自身的连接（自环）外，原图邻接矩阵中为0的位置在补图矩阵中为1，原图为1的位置补图为0。如果是允许自环的场景，无需排除i==j的位置，直接全量取反即可。

核心实现逻辑 #

• 有向图：遍历所有i≠j的矩阵位置，直接对原图取值取反
• 无向图：邻接矩阵天然对称，仅需遍历上三角区域计算后对称赋值，可减少一半计算量
• 不需要额外使用队列或者标记数组，直接操作矩阵元素即可，你之前开篇写的队列和Arr数组其实是BFS遍历用的，补图计算不需要这套逻辑

补全后的伪代码 #

通用版（支持有向/无向图） #

// 输入：图G的邻接矩阵adj，顶点总数n
// 输出：补图的邻接矩阵comp_adj
Complement(G, n)
    // 初始化n阶补图邻接矩阵
    int comp_adj[1...n][1...n]
    for i = 1 to n
        for j = 1 to n
            // 无自环需求时保留该判断，有自环需求删除即可
            if i == j
                comp_adj[i][j] = 0
            else
                comp_adj[i][j] = 1 - G.adj[i][j]
    return comp_adj

无向图优化版 #

// 输入：无向图G的邻接矩阵adj，顶点总数n
// 输出：补图的邻接矩阵comp_adj
ComplementUndirected(G, n)
    int comp_adj[1...n][1...n]
    for i = 1 to n
        comp_adj[i][i] = 0
        // 仅遍历上三角区域
        for j = i + 1 to n
            comp_adj[i][j] = 1 - G.adj[i][j]
            comp_adj[j][i] = comp_adj[i][j]
    return comp_adj

代码落地注意事项 #

• 若你的邻接矩阵存储的是边权重而非0/1的边存在标识，需要先将原图矩阵转换为0/1的存在性矩阵后再执行取反操作
• 若不需要保留原图数据，可以直接在原图邻接矩阵上修改，无需申请额外的矩阵存储空间，遍历i≠j的位置执行G.adj[i][j] = 1 - G.adj[i][j]即可

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