8

ノードの削除が可能な限り高速になるように、有向グラフ (必ずしも非循環的である必要はありません) を保存する必要があります。ノードが削除されたときにどのエッジに移動する必要があるかを正確に知るために、追加のデータを保存してもかまいません。

エッジのリストを (ノード インデックスのペアとして) 格納する場合、いくつかのノード n を強制終了するときに、ソースまたはターゲットが n であるエッジのリスト全体を検索する必要があります。これは私のアプリケーションにはコストがかかりすぎます。ノードに追加のデータを保存することで、この検索を回避できますか?

1 つのアイデアは、各ノードに独自のソースとターゲットを 2 つの別個のリストとして保存させることです。ノード n が強制終了されると、そのリストも強制終了されます。しかし、ノード n にリンクされたすべてのターゲット/ソースは、どのようにして自身のリストを更新するか (つまり、機能していないノードをリストから削除するか) を知るのでしょうか? これには、コストのかかる検索が必要になります...

回避できますか？

どうも。

4

2 に答える 2

4

あまり気にしないで、隣接リストと隣接マトリックスの2つの選択肢があります。前者はおそらくあなたがしていることに最適です。ノードを削除するには、そのノードのすべてのアウトエッジのリストを削除するだけです。インエッジの場合、O（1）ルックアップの各リストのハッシュテーブルを保持することを検討できます。

これは良い概要です http://www.algorithmist.com/index.php/Graph_data_structures

于 2011-02-22T22:00:58.403 に答える
2

解決しました！これは無向グラフのソリューションであり、後で方向を追加するのは簡単です。

各頂点には、特別な隣接リストがあります。これは、要素が「スロット」であるリスト（二重リンク、簡単な挿入/削除用）です。

class Slot {
  Slot prev, next; // pointers to the other slots in the list
  Slot other_end; // the other end of the edge: not a vertex, but a Slot!
  Vertex other_vertex; // the actual vertex at the other end

  void kill() {
    if (next!=null) next.kill(); // recursion
    other_end.pop_out();
  }

  void pop_out() {
    if (next!=null) next.prev = prev;
    if (prev!=null) prev.next = next;
    else other_end.other_vertex.slot_list = next; // in case this slot is the
                                                  // first in its list, I need
                                                  // to adjust the vertex's
                                                  // slot_list pointer.
    // other_end.other_vertex is actually the vertex to which this slot belongs;
    // but this slot doesn't know it, so I have to go around like this.
  }

}

したがって、基本的に、各エッジは2つのスロットで表され、互いに交差しています。そして、各頂点にはそのようなスロットのリストがあります。

頂点が強制終了されると、スロットリストに「強制終了」信号が再帰的に送信されます。各スロットは、other_endを破棄することで応答します（これは、ネイバーのリストから丁寧に飛び出し、前/次のポインターを後ろに修正します）。

このようにして、頂点とそのすべてのエッジが検索なしで削除されます。私が支払わなければならない代償はメモリです。3つのポインタ（通常の二重リンク隣接リストのprev、next、vertex）の代わりに、4つのポインタ（prev、next、vertex、other_end）を保持する必要があります。

これが基本的な考え方です。有向グラフの場合、INスロットとOUTスロットをどういうわけか区別するだけで済みます。おそらく、各頂点の隣接リストをIN_slot_listとOUT_slot_listの2つの別々のリストに分割することによって。

于 2011-02-23T21:28:13.283 に答える