0

有向グラフ G = (V, E) の 2 乗はグラフ G2 = (V, E2) であり、u → w が E2 に含まれるのは、u ≠ w であり、両方の u→v を満たす頂点 v がある場合に限ります。そして v→w は E2 にあります。入力ファイルは、頂点の順序付けられたペアとして任意の順序でエッジを単純にリストし、各エッジは別の行に表示されます。頂点には、1 から頂点の総数まで順番に番号が付けられます。

*自己ループと重複/平行エッジは許可されていません

入力データの例を見ると:

1 6
1 4
1 3
2 4
2 8
2 6
2 5
3 5
3 2
3 6
4 7
4 5
4 6
4 8
5 1
5 8
5 7
6 3
6 4
7 5
7 4
7 6
8 1

出力は次のようになります。

1: 3 4 7 8 5 2 6
2: 5 6 3 4 1 8 7
3: 1 7 8 6 5 4
4: 5 6 8 7 3 1
5: 3 1 4 6
6: 2 7 5 8
7: 1 5 6 8 3 4
8: 6 4 3

Cでコードを書いています。

私の考えでは、ファイルを実行し、頂点の数を確認してから、ポインターの配列を割り当てます。行に 1 がある場所を探してリストをもう一度調べ、対応する番号がどこにつながるかを調べます。重複または同じ番号 (1) でない場合は、ポインターの配列からリンクされたリストに追加します。ファイル内の頂点番号ごとにこれを行います。

しかし、これは非常に非効率的であり、最善の方法ではないと思います。誰か他の提案があれば、私は非常に感謝しています。

4

1 に答える 1

2

私が正しく理解できれば、ノードごとに距離が 1 と 2 のすべてのノードが示されている各ノードの結果セットを作成する必要があります。

したがって、エッジが存在する場合はビットが 1 であり、存在しない場合は 0 であるビット配列の隣接行列にエッジを保持できます。

これで、この行列をそれ自体で乗算できます。この場合、乗算は、行と列で AND を作成できることを意味します。

小さな例 (申し訳ありませんが、マトリックスを適切に挿入する方法がわかりません):

0 1 0   0 1 0   0 0 1
0 0 1 x 0 0 1 = 1 1 0
1 1 0   1 1 0   0 1 1

このマトリックスには、2 つのステップで到達可能なすべてのノードの 1 つが含まれています。単純に、1 ステップではなく 2 ステップの隣接行列です。このマトリックスを初期マトリックスと OR すると、長さ 1 と 2 のすべてのパスを保持するマトリックスが得られます。

このアプローチには複数の利点があります。最初のビット操作は非常に高速です。CPUは計算を麻痺させ、結果が1を与える場所で1つのペアが見つかった場合、結果のマトリックスセルを停止できます.

さらに、行列の乗算を並列に計算する方法が十分に文書化されています。

他のすべてのパスの長さを簡単に計算できます。長さ k については、次のように計算する必要があります。

A^k = A^(k-1) * A

役に立ったことを願っています

于 2012-09-13T06:07:20.257 に答える