2017-09-11 10 views
0

こんにちは、グラフの連続した表現について読んだことがありますが、配列の要素の要素を理解できません。データ構造体グラフのシーケンシャル式

本はこう述べています。

graph G4's

シーケンシャル式は以下の通りです。 enter image description here

各配列の要素を取得する方法を知りたい。

本書も言う

ノードは、[i]は、開始頂点のポイント、ノード[N]である(nは頂点、Eはエッジである)、N +によって設定されています2e + 1。

頂点が 'i' は、隣接する頂点がノードに保存され、[i]は...ノード[I + 1] -1

私はこの文章の意味を理解することはできません。

答えて

0

すべての頂点はnodeに格納されています。その頂点inode[i]に格納されています。頂点3が必要な場合は、node[3]を使用します。エドゥアルドの答えのビットを拡張する

0

(正しい多分余りに簡潔である):

この表現では、第一n配列値は、データの残りの部分へのインデックスとして働きます。例えば、nodes[2] == 13 - ノード2の隣接関係のオフセットのため、nodes[11]から最大値(但し含まない)の値は、ノード1の隣接ノードのインデックスです。ノード1の隣接関係のオフセットは、ノード1の隣接関係のオフセットであるnodes[1] == 11となります。 - この場合、[3, 0]

nodes[8] == 23は、オフセット保存の終了を示すnodesのサイズを超える余分な値であることに注意してください。これにより任意のノードの隣接関係にアクセスすることができますinodes[nodes[i]] .. nodes[nodes[i+1]-1] - これはC/C++ループ内で自然に表現されます。

nodes(オフセットと隣接リスト)の2つの部分が2つの別々の配列として格納されている、同様の、しかし間違いなく頻繁に使用される形式はCompressed Sparse Rowです。