0

グラフの問題を解いています。無向グラフです。4 つの頂点 (1、2、3、4) が​​あり、頂点が次のようにリンクされているとします。

1,2
1,3
1,4
2,1
3,1
4,1

G(i,j) と G(j,i) は両方とも上記のように存在します (G-グラフ、i-ソース頂点、j-宛先頂点)。ここで、すべての G(j,i) を削除する必要があります。これは効率的な方法かもしれません。

すべての i 頂点を 1 つの配列に挿入し、j 頂点を別の配列に挿入しようとしました。何かのようなもの

a[0] = 1 and b[0] = 2
a[1] = 1 and b[1] = 3
so on..

しかし、G(j,i) エントリを削除するのは難しいです。3 つの質問があります。

  1. 重複を削除する効率的なアルゴリズムはありますか（ここでは重複と言い、bcoz G（i、j）= G（j、i））。

  2. 配列を使用する代わりに、この操作をより簡単に実行できるデータ構造はありますか。

  3. グラフの問題で一般的に使用されるデータ構造。

4

1 に答える 1

1

グラフは通常、隣接行列形式または隣接リストのいずれかで表されます。

n = ノードの数、m = エッジの数、ノードの ID は 0 から (n-1) までの整数であるとします。

隣接行列では、基本的にサイズ nx n の 2D 配列があります。ノードと[i][j] の間にエッジがない場合、 index の値は 0 であり、それ以外の場合は非ゼロです。グラフが重み付けされていない場合、マトリックスは通常バイナリ (エッジなしの場合は 0、エッジの場合は 1) であり、代わりにブール値のマトリックスを使用してスペースを節約できます。グラフが無向の場合、 のエッジはのエッジを示すため、行列が対称になることに注意してください。ij[i][j][j][i]

ただし、スペース効率が懸念され、グラフがエッジに関してまばらである場合、データ構造はエッジの数に関係なく O(n^2) を使用するため、多くの無駄なスペースが発生します。

代替手段は隣接リストで、O(n + m) スペースを取ります。ここでは、配列の各要素がコンテナー (リンクされたリストまたはハッシュ セットなど) である 1D 配列を使用できます。i配列のth コンテナーは、ノードに接続されているノードの ID を保持しithます。

あなたが持っているその「エッジリスト」形式で重複を削除する問題に対処するには、無向グラフが必要なようです。つまり、 から へのエッジは からiへjのエッジを意味jしiます。隣接行列では、これは を設定するだけで実行できます[i][j] = [j][i] = true。隣接リストでは、setコンテナーを使用すると、setエッジが重複しないことが保証されるため、最適です。したがって、エッジリストに からiへのエッジが表示さjれた場合、単純にth セルにインデックスを付けてiin を追加しj、th セルにインデックスを付けてjin を追加しiます。j後でtoが表示されたときにi同じことを行いますが、重複した値をハッシュ セットに追加しても何も起こりません。

于 2013-02-22T07:12:29.310 に答える