0

グラフは次のような形式で表されます。

MAX 12
NODE 1 1
NODE 2 2 
NODE 3 3
NODE 4 4
NODE 5 5
NODE 6 6
NODE 7 7
NODE 9 9
NODE 8 8
NODE 10 10
NODE 11 11
NODE 12 12
EDGE 1 2
EDGE 2 3
EDGE 3 4
EDGE 4 5
EDGE 5 6
EDGE 6 7
EDGE 7 8
EDGE 8 9
EDGE 9 10
EDGE 10 11
EDGE 11 12
EDGE 1 12
EDGE 1 3
EDGE 1 4
EDGE 1 6
EDGE 1 8
EDGE 1 11
EDGE 1 10
EDGE 6 10
EDGE 3 6
EDGE 4 6
EDGE 5 7
EDGE 9 11

これらのエッジを読み取るには、隣接するリストを使用する必要があります。しかし、無向グラフ、つまり として使用したい場合は、すべてのエッジの直接性をすべて無視します。ノードの各ペアの接続性を知るにはどうすればよいですか?

たとえば、(NODE 2, NODE 8) 間の最短距離は、無向グラフでは 2 (2->1>8) ですが、このグラフにダイクストラのアルゴリズムを使用すると 4 (2->3->6->7) になります。 ->8)。エッジを読み取るために同じ手法を使用しながら、無向グラフをどのように表現できますか?

4

1 に答える 1

0

エッジを読み取る手法を本当に変更したくない場合は、他のすべてのノードを繰り返し処理して、ノードが隣接リストにあるかどうかを確認する必要があります。

これにより、実行時間が大幅に増加しますが、ストレージはあまり節約されないため、エッジを読み取る手法を変更することをお勧めします.

于 2016-04-23T10:08:47.640 に答える