不規則な枝の数のグラフ構造について

[yskey]

どうもyskeyです。お世話になっています。
現在DxLibで戦略ゲームを製作中です。

ノードからの枝の数が異なるグラフ構造を実装しようと思うのですが、通常はどのような方法で実装されるのですか？
http://ja.wikipedia.org/wiki/%E3%83%80% ... 9%E6%B3%95
Wikipediaの「ダイクストラ法」のページにある画像が丁度実装したいものです。

調べても中々具体例が探し出せないので困っています。

通常、二分木やリスト構造なら構造体内にある自身を示すポインタの数は大体1,2個で十分ですが、
今考えているような構造だと、枝の数が1本だったり、3本、5本だったりして少し工夫しなければなりません。

そこで、一応多めにポインタを宣言しておくような方法が考えれたのですが、この方法はどうなんでしょうか？

また、もう一つ疑問があります。
この複雑なデータ構造をどのように保存すべきなのでしょうか？
（実際のデータは切り離して、それぞれのノードから参照する…とか？）

[MNS]

動的配列を使うのはどうでしょうか？

[Ma]

私ならノードの構造体内に、枝分かれする（型という意味で）同じ構造体へのポインタの配列を用意しますね。
結局、簡単に言えば動的配列です。
あとデータの持たせ方についてですが、私ならデータへのポインタをノードに持たせます。
とはいっても、メリット、ディメリットがぱっと思いつかないんで、このへんは他の方の意見も聞いてみてください。

一応、ぱっと思いついたメリット
・あるクラスが登録しておきたいデータだったとします。そのあるクラスを継承させて登録したい場合、親クラス名のポインタで両方のクラスに対応できる。

[たいちう]

> そこで、一応多めにポインタを宣言しておくような方法が考えれたのですが、
> この方法はどうなんでしょうか？

あらかじめ最大を決めておく必要があること、
メモリ使用量に無駄が発生すること、という欠点がありますが、
これに目をつぶれるならば大丈夫でしょう。

とりあえずは簡単なこの方法で作成し、後で必要になったら動的配列に
変更することも可能です。


> この複雑なデータ構造をどのように保存すべきなのでしょうか？

すべきかどうかはともかく、例えばこのようにできます。
（Wikipediaのダイクストラ法の動作のアニメーションのグラフ）

1, 2, 3, 6
2, 1, 3, 4
3, 1, 2, 4, 6
4, 2, 3, 5
5, 4, 6
6, 1, 3, 5

[yskey]

>>MNSさん、Maさん、たいちろうさん、ご返信ありがとうございます。
動的配列というとmalloc関数などで確保する変数の配列ですよね…？（vectorコンテナも？
それはわかるのですが、構造体を一度宣言した後に構造体内の変数を動的に変化させることができるのですか？

[たいちう]

動的に変化させるのはあくまでもデータです。こんな感じ。

struct Hoge {
    int id;
    vector<Hoge> link;
};

[たいちう]

ポインタにしないと無駄が多すぎでした。失礼。
vector<Hoge*> link;

[yskey]

>>たいちろうさん、返信有難うございます。
やはりvectorコンテナですか。イメージがつかめました。有難うございます。
早速、書いてみたいと思います。

[yskey]

すいません、わからない所がまた一つ、、、
Wikipediaの「ダイクストラ法」のページにある画像のグラフ構造には枝に数字（距離の情報）がありますが、あれはどのように実装しているんでしょうか？
単純に他の構造体を参照するだけでは上手く行きません…
間に

struct node{
  int data;
  vector<node*> link;
};
struct branch{
  int data;
  int* link;
};

などとブランチ（枝）を別の構造体にする手を思いつきましたが、あまり最善策ではないような気がします。
何かよい方法はありますか？

[たいちう]

一例です。

struct Hoge {
    int id;
    vector<Hoge*> link;
    vector<int> distance;
};

> などとブランチ（枝）を別の構造体にする手を思いつきましたが、
> あまり最善策ではないような気がします。

提示された条件のみでは何が最善策かなど判断できません。
思いついた方法で実装し、何か問題があれば改善すれば良いのではないですか？

[yskey]

>>たいちろうさん、ご返信有難うございます。
実践あるのみということでしょうか？
よく考えたら、たいちろうさんが示された一例で十分実装できますね。
ありがとうございます。

戦略シミュレーションゲームは、土地、ユニット、国、、、
データ構造が複雑そうですが一つずつ消化していけばなんとかやっていけそうです。