如何在O(m+k)时间复杂度下获取图的边集？现有代码为O(m²)

你的问题核心是避免无向图边的重复记录，同时把时间复杂度从O(m²)降到O(m+k)。先分析下你原来的代码：

你用frozenset来自动去重，虽然结果正确，但每条无向边会被处理两次（比如顶点0→1和1→0都会被遍历到），而且如果遇到完全图这种极端情况，每个顶点的邻接表包含所有其他顶点，那你的代码会执行O(m²)次操作，这显然不符合你的时间复杂度要求。

优化方案：只记录单向边 #

无向图的边(u, v)等价于(v, u)，所以我们可以只记录u < v的边，这样每条边只会被处理一次，完全不需要去重操作，时间复杂度直接降到O(m+k)——其中m是遍历所有顶点的开销，k是处理所有边的开销（每条边仅处理一次）。

优化后的代码如下：

def edgeset(G):
    edges = set()
    for i in range(len(G)):
        for neighbor in G[i]:
            # 只保留i < neighbor的边，避免重复记录
            if neighbor > i:
                edges.add((i, neighbor))
    return edges

为什么这个是O(m+k)？ #

• 外层循环遍历m个顶点，开销是O(m)；
• 内层循环遍历每个顶点的邻接表，但只处理neighbor > i的节点，每条无向边只会被处理一次，总共有k条边，所以这部分开销是O(k)；
• 整体加起来就是O(m + k)，完美符合你的需求。

测试验证 #

用你提供的define_G()生成的图来测试，这个函数返回的图边集应该是：
{(0,1), (0,2), (1,2), (1,3), (1,4), (2,4), (3,4)}
调用优化后的edgeset(define_G())就能得到这个结果，没有重复，效率也更高。

如果你偏好保留frozenset的形式，只需要把(i, neighbor)改成frozenset({i, neighbor})就行，但元组的创建和哈希效率比frozenset更高，更推荐使用元组。

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