python - 图更新算法

Question

我有一个使用邻接表表示的(无向)图，例如

a: b, c, e
b: a, d
c: a, d
d: b, c
e: a

图中的每个节点都链接到其他节点的列表

我想在给定某些节点的一些新列表的情况下更新这样的图表，例如

a: b, c, d

其中a不再连接到e，连接到一个新节点d

什么是对图执行此类更新的有效(时间和空间方面)算法？

Answer 1

也许我遗漏了什么，但是使用节点标签(字符串或数字)的字典(或默认字典)来设置不是最快的吗？在这种情况下，更新可能看起来像这样:

def update(graph, node, edges, undirected=True):
    # graph: dict(str->set(str)), node: str, edges: set(str), undirected: bool
    if undirected:
        for e in graph[node]:
            graph[e].remove(node)
        for e in edges:
            graph[e].add(node)
    graph[node] = edges

使用集合和字典，将节点添加到其他节点的边集或从其他节点的边集中删除节点应该是 O(1)，与更新节点本身的边集相同，所以这应该只是 O( 2n) 对于两个循环，n是一个节点的平均边数。