在 Python 中获取 O(m+k) 图形的边集

Question

我想在O(m+k)[中得到以下图的边集 =25=], k = 边数, m = 顶点数

#graph
def define_G():
    m = 5
    G = [set() for _ in range(m)]
    G[0] |= {1,2}
    G[1] |= {0,2,3,4}
    G[2] |= {0,1,4}
    G[3] |= {1,4}
    G[4] |= {1,2,3}
    return G

我写了这段代码，但它似乎 运行 在 O(m^2):

def edgeset(G):
  m = set()
  i = 0
  for a in G:
    for b in a:
      m.add(frozenset({i, b}))
    i += 1

它 returns set([frozenset([2, 4]), frozenset([6, 7]), frozenset([1, 2]), frozenset([2, 6]), frozenset([1, 4]), frozenset([8, 9]), frozenset([3, 4]), frozenset([0, 2]), frozenset([4, 5]), frozenset([1, 3]), frozenset([2, 7]), frozenset([0, 1])])，但不在 O(m+k)。 O(m+k)怎么可能？

Answer 1

由于每条边在所有邻居集中总共只出现两次，因此邻居集的大小之和为2 x k。意思是你的代码是 O(m+k).

Answer 2

为什么您认为它总是 O(m**2)？

在一种极端情况下，所有节点都可以用边连接，这意味着您将精确地迭代每条边两次，从而得到这个 O(k) 解决方案。请注意，虽然在这种情况下 k 是 O(m**2)，但由于可能的边总数 = m C 2，您的解决方案仍然可以表示为 O(m+k)。

在另一种极端情况下，none 个节点是连接的，这意味着您必须恰好迭代所有空顶点一次，使其成为 O(m) 解决方案。由于 k 为零/常数，这仍然是 O(m+k) 解。

总的来说，您的解决方案始终是 O(m+k)。