MLi*_*ter 7 python algorithm graph-theory graph-algorithm
我有一个(非定向)图表使用邻接列表表示,例如
a: b, c, e
b: a, d
c: a, d
d: b, c
e: a
图表的每个节点都链接到其他节点的列表
我想在给定某些节点的一些新列表的情况下更新这样的图表,例如
a: b, c, d
where a不再连接到e,并连接到新节点d
对图表执行此类更新的有效(时间和空间)算法是什么？
小智 0
使用邻接网格将使更新时间复杂度为 O(n)，但无论图形有多稀疏，都会占用 n^2 空间。（通过反转行和列来更新每个更改的关系即可轻松完成。）
使用列表会使更新时间达到 O(n^2)，但对于稀疏图不会花费大量时间，并且会节省大量空间。