图形更新算法

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

使用集合和dicts，将节点添加到其他节点的边集或从其他节点的边缘集移除节点应该是O（1），与更新节点本身的边集相同，因此对于两个循环，这应该只有O（2n），其中n是节点的平均边数。

Answer 2

使用邻接网格会使其更新为O（n），但无论图有多稀疏，都会占用n^2空间

使用列表将使更新的时间达到O（n^2），但对于稀疏图，不会占用大量时间，并且会节省大量空间。

Answer 3

典型的更新是del edge a,e; add edge a,d，但您的更新看起来像是顶点a的新邻接列表。因此，只需找到a邻接列表并替换它。这应该是O（logn）时间（假设邻接列表的排序数组，就像您的描述中一样）。