python - 图更新算法

Question

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

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

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

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

a: b, c, d

wherea不再连接到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 是节点的平均边数。

Answer 2

使用邻接网格将使其 O(n) 更新，但会占用 n^2 空间，无论图有多稀疏。（通过反转行和列来更新每个更改的关系来轻松完成。）

使用列表会使更新时间达到 O(n^2)，但对于稀疏图不会花费大量时间，并且会节省大量空间。

Answer 3

一个典型的更新是del edge a,e; add edge a,d，但你的更新看起来像一个新的 vertex 邻接列表a。所以只需找到a邻接列表并替换它。那应该是 O(log n) 时间（假设邻接列表的排序数组，如您的描述中所示）。