8

私は現在、C ++の有向グラフデータ構造に取り組んでいます（このプロジェクトにはBoost GLはありません）。主なアプリケーションは、接続されたコンポーネントとシンクを識別することです。グラフはまばらであると予想され（E〜4Vのnumエッジの上限）、すべて均一な重みになります。私は、隣接リスト、発生率リスト、またはおそらくまだ聞いたことがない他の表現のいずれかを決定しようとしています（余因子行列はスパース性のオプションbcではありません）。ボトルネックは、全体的なスペースとグラフの初期化の速度である可能性があります。グラフは、潜在的に巨大な配列から初期化されるため、配列内の各要素は、隣接する要素の1つに向けられたエッジを持つ頂点になります。各頂点のエッジを取得するには、その隣接するすべての要素を最初に比較する必要があります。

私の質問は次のとおりです。（1）通常、初期化が高速で、BFSトラバーサルも高速な表現、（2）連結成分を見つけるためのアルゴリズム（バニラBFS以外）はありますか？BFSを使用したO（V + E）であることは知っていますが（これが最適だと思います）、グラフの幅が高さとともに指数関数的に増加するため、中間キューのサイズが心配です。

グラフの実装についてはあまり経験がないので、何か提案をいただければ幸いです。

4

3 に答える 3

5

次のようなレイアウトを検討してください。

ここに画像の説明を入力

隣接リストは、次の形式で [Nx4] の配列として実装できます (この場合、n は 3 であり、4 がエッジの最大数であると言っているため、4 です)。

2  3  0  0
3  0  0  0
0  0  0  0

上記の表現は、頂点の数が、配列への最初のインデックスが で与えられるソート順になっていることを前提としてい(v-1)ます。

一方、発生リストでは、頂点リスト、辺リスト、およびその間の接続要素 (発生リスト - グラフ) を定義する必要があります。

あなたが述べたように、グラフは非常にまばらであるため、どちらも隣接行列と比較してスペース使用の点で優れています。

私の提案は、メモリ内の[Nx4]連続配列として初期化できる隣接リストを使用することです（1つの頂点に対して最大4つのエッジがあると言っているため）。この表現は、初期化が高速になります。(また、この表現は、キャッシュ効率の点でより優れたパフォーマンスを発揮します。 )

ただし、グラフのサイズが動的かつ頻繁に変化することが予想される場合は、通常、連続していないスペースであるリストとして実装されるため、発生リストの方が適している可能性があります (上記のリンクを参照)。その場合、隣接配列の割り当て解除と割り当ては望ましくない場合があります。

于 2013-03-08T01:14:43.003 に答える
2

目的に合わせてグラフを実装する最も効率的な方法は、おそらく、各頂点の隣接リストと、頂点のペアをエッジにマップするハッシュ構造 (存在する場合) の組み合わせです。これには、隣接リストに O(|V|+ |E|) スペース、ハッシュ構造に O(|E|) が必要であり、予想される O(1) を提供containsEdge(vertex v, vertex w)し、マッピングinsertEdge(vertex v, vertex w)をremoveEdge(vertex v, vertex w)使用して必要なポインターを取得します頂点の隣接リストをすばやく変更します。

于 2013-03-08T01:35:41.733 に答える