求邻接表表示的有向图与无向图补图的高效算法

针对邻接表表示的图，基础的“建完全图再删边”方法会产生大量冗余操作，尤其是顶点数较多时效率极低。下面是基于排序+双指针的优化方案，无需构建完全图，直接生成补图的邻接表：

无向图补图实现 #

无向图的补图包含所有原图中不存在的无序顶点对（u, v），且u≠v。核心思路是利用排序后的邻接表，通过双指针快速筛选出缺失的边：

1. 预处理：将每个顶点的邻接表按顶点编号排序，保证后续双指针遍历的可行性。
2. 双指针遍历生成补边：
   • 对每个顶点u，仅遍历v > u的顶点（避免重复处理无向边）。
   • 用指针adj_ptr跟踪u的邻接表当前对比位置，对比v和邻接表元素：
     • 若v小于当前邻接表元素：说明（u, v）不在原图中，将其同时加入u和v的补图邻接表。
     • 若v等于当前邻接表元素：跳过该边，同时移动两个指针。
     • 若v大于当前邻接表元素：仅移动邻接表指针，继续对比。
   • 当邻接表遍历完毕后，剩余未匹配的v全部加入补图。

伪代码示例（优化版，避免重复边） #

def undirected_complement(adj, vertex_count):
    # 先排序每个顶点的邻接表
    sorted_adj = [sorted(edges) for edges in adj]
    complement = [[] for _ in range(vertex_count)]
    
    for u in range(vertex_count):
        adj_ptr = 0
        adj_len = len(sorted_adj[u])
        # 只处理v > u的情况，避免重复添加无向边
        for v in range(u + 1, vertex_count):
            # 移动指针找到第一个不小于v的邻接顶点
            while adj_ptr < adj_len and sorted_adj[u][adj_ptr] < v:
                adj_ptr += 1
            # 若v不在u的邻接表中，添加补边
            if adj_ptr >= adj_len or sorted_adj[u][adj_ptr] != v:
                complement[u].append(v)
                complement[v].append(u)
    return complement

有向图补图实现 #

有向图的补图包含所有原图中不存在的有序顶点对（u, v），且u≠v。逻辑类似无向图，但需要处理所有u≠v的有序对：

1. 预处理：同样先将每个顶点的邻接表排序。
2. 双指针遍历生成补边：
   • 对每个顶点u，遍历所有v≠u的顶点。
   • 用指针跟踪u的邻接表，对比v与邻接表元素，筛选出所有不在原图中的有序对（u, v），加入补图的u的邻接表。

伪代码示例 #

def directed_complement(adj, vertex_count):
    sorted_adj = [sorted(edges) for edges in adj]
    complement = [[] for _ in range(vertex_count)]
    
    for u in range(vertex_count):
        adj_ptr = 0
        adj_len = len(sorted_adj[u])
        for v in range(vertex_count):
            if u == v:
                continue
            while adj_ptr < adj_len and sorted_adj[u][adj_ptr] < v:
                adj_ptr += 1
            if adj_ptr >= adj_len or sorted_adj[u][adj_ptr] != v:
                complement[u].append(v)
    return complement

复杂度分析 #

• 时间复杂度：
  • 排序阶段：总耗时O(m log d)，其中m是原图边数，d为顶点平均度。
  • 遍历阶段：无向图优化后为O(n²/2)，有向图为O(n²)（n为顶点数）。
    整体比基础方法节省了构建完全图的冗余开销，尤其在原图稀疏时优势明显。
• 空间复杂度：仅存储补图的边（O(n² - m)），无需额外存储完全图，空间效率远高于基础方法。

额外优化点 #

如果顶点不是连续整数，可先通过哈希表为每个顶点分配连续索引，再按上述逻辑处理，保证遍历的有序性。

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