隣接リスト表現を使用しています。
基本的
A:[B,C,D] means A is connected to B,C and D
今、グラフにエッジを追加する方法を (Python で) 追加しようとしています。
しかし、エッジを追加する前に。2 つのエッジが接続されているかどうかを確認したい。たとえば、2 つのノード D と A の間にエッジを追加したい (A と D が接続されているという事実を知らない)。
したがって、ハッシュ/辞書にキー「D」がないため、false が返されます。
今、非常に単純に、D と A をチェックし、次に A と D もチェックできます..しかし、それは非常に面倒です。または、2 つのノードを接続するたびに、いつでも複製できます。
つまり、A と E を接続する場合.. A:[E] create E:[A]
しかし、これはあまりスペース効率が良くありません。
基本的には、このグラフの方向を独立させたいと考えています。
これを解決するのに役立つデータ構造はありますか?
私の質問が理にかなっていることを願っています。
無向グラフの場合、エッジのすべてのペアを格納する単純なエッジ リストを使用できます。これによりスペースが節約され、パフォーマンスが低下しますが、両方を同時に持つことはできないため、常にトレードオフを決定する必要があることを知っておく必要があります。
それ以外の場合は、三角形の隣接行列を使用できますが、スペースの半分を無駄にしないように、特定の方法で格納する必要があります (スペースを無駄にすることなくエッジの存在を取得する効率的な方法を開発することにより)。それだけの価値があり、時期尚早の最適化ではないと確信していますか?
すべての無向辺を 2 回保存する必要がある場合でも、隣接リストはほとんど問題ありません。グラフの大きさはどれくらいですか?
これを見てください 私の答え:グラフ表現のベンチマーク、好きなものを選択できます。
contains()各メソッドが非常に拡張的であり、すべてのコストでこれらを実行することを避けたいと仮定すると、ブルーム フィルターcontains()を使用して、エッジが存在するかどうかを確認できます。これにより、呼び出しの数を減らすことができます。
アイデアは次のとおりです。各ノードは独自のブルーム フィルターを保持し、どのエッジがそれに接続されているかを示します。ブルーム フィルターのチェックはかなり簡単で安価であり、エッジが追加されたときにそれを変更することもできます。
ブルーム フィルタをチェックして「いいえ」と表示された場合は、安全にエッジを追加できますが、エッジは存在しません。
ただし、ブルーム フィルターには誤検知があります。そのため、ブルーム フィルターが「エッジが存在する」と言った場合は、リストが実際に存在するかどうかを確認する必要があります。
注:
(1) ブルーム フィルターを使用する場合、エッジの削除が問題になります。
(2) ブルーム フィルターは、フィルターのサイズが大きくなるにつれて誤検知の数が減少するため、時間と空間の適切なトレードオフを提供します。
(3) ただし、エッジが存在する場合は、フィルターのサイズに関係なく、常にcontains()メソッドを使用する必要があります。
古典的なスペースと時間のトレードオフに遭遇しました。
おっしゃるとおり、D->A が見つからない場合は、A->D を検索できます。これにより、実行時間が最大で 2 倍になります。または、A->D を挿入するときに D->A も作成しますが、これには追加のスペースが必要です。
最悪の場合、時間のトレードオフのために、2 回のルックアップを行いますが、それでも O(N) です (データ構造が優れているほど高速です)。スペースのトレードオフのために、(最悪の場合) ノードのすべてのセット間にリンクを作成します。これはおよそ O(N^2) です。そのため、2回のルックアップを行うだけです。
ノード名を比較できると仮定すると、最初のエンドポイントが2番目のエンドポイントよりも小さくなるように、常にエッジを格納できます。次に、実行するルックアップは1つだけです。これは間違いなく文字列に対して機能します。