ポインタによる配列によるツリーの実装のメリット？

Question

最近、私は、このような

struct Node{ 
    Node *parent; 
    vector<Node*> child; 
    Node(void):parent(nullptr){} 
} 

として構造体でツリーを実装学んだ私は 、これは木を実装するためにはかなりまっすぐ進むべき道であると思ったし、また、構造体の中のプロセスのためのより多くのものを含めることが容易です。

しかし、多くの人のコードでは、 はポインタの代わりに配列を使用する方が好きです。 バイナリツリーではこれを理解することができました。配列でもそれを行うのはかなり簡単ですが、 でも、他の複雑なグラフではなぜですか？

Answer 1

Skienaから：(x, y)場合

• 隣接行列は、テストのために速くつのノードです：2008：ADM：1410219とCormen：2001：IA：グラフ利回りについて580470の比較隣接行列と隣接リスト接続エッジがある
• 隣接リストは、特定のノードの次数（隣接ノードの数）を見つけるためにより速くなります。
• mノードとnのエッジを持つグラフは、隣接リストを使用して実装された場合はm + nスペースを消費しますが、隣接行列の場合はn^2です。
• 隣接行列は、をわずかに使用します。大きなグラフではメモリが少なくなります。
• 隣接行列を使用する場合、エッジ挿入/削除はO(1)で実行されます。
• 隣接リストを使用して実装グラフをトラバースグラフは、多くの頂点が、いくつかのエッジの隣接行列は、過度のメモリを消費している場合Θ(m + n)とマトリックスΘ(n^2)

で行います。

一般に、隣接関係リストの方が優れています。