7

隣接リストを使用して表される（無向）グラフがあります。

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

グラフの各ノードが他のノードのリストにリンクされている場所

特定のノードの新しいリストを指定して、そのようなグラフを更新したい。

a: b, c, d

whereaは に接続されなくなりe、新しいノードに接続されますd

このようなグラフの更新を実行するための効率的な (時間的にも空間的にも) アルゴリズムは何でしょうか?

4

3 に答える 3

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 はノードのエッジの平均数です。

于 2012-08-31T22:36:29.380 に答える
0

隣接グリッドを使用すると、更新が O(n) になりますが、グラフがどれほどまばらであるかに関係なく、n^2 のスペースが必要になります。(行と列を反転して、変更された各関係を更新することで簡単に実行できます。)

リストを使用すると、更新に最大で O(n^2) の時間がかかりますが、まばらなグラフの場合、大きな時間のペナルティはかからず、多くのスペースを節約できます。

于 2012-07-22T03:22:40.913 に答える
0

典型的な更新は ですdel edge a,e; add edge a,dが、あなたの更新は頂点 の新しい隣接リストのように見えますa。したがって、a隣接リストを見つけて置き換えるだけです。それは O(log n) 時間になるはずです（説明のように、隣接リストのソートされた配列を想定しています）。

于 2012-07-22T03:36:48.883 に答える