2077


グラフ構造を実装しようとしています。

枝の距離をデータとして格納する方法はどの教科書を見ても詳細に記載されていましたが、節点の場合どうすればよいか分かりません。

> O'Reilly Japan - アルゴリズムクイックリファレンスP.154
>
> 隣接行列のデータ構造
[code]

>     int A[][]=
>     {
>        {0, 0, 0, 0, 0, 0},
>        {6, 0,18, 0, 0, 0},
>        {0, 0, 0, 0, 0, 0},
>        {0, 0, 0, 0, 0, 9},
>        {0, 0, 0, 0, 0, 0},
>        {0, 0, 0,12, 0, 0}
>     };
>  
[/code]

隣接リストのデータ構造 (書籍を頼りに多分このようなデータ構造だろうと推測しました):

[code]

    std::vector<std::list<std::pair<int,int>>>A;
    
[/code]

このようなグラフ構造で、節点に何らかのデータを入れたい場合どのようにしたらよいでしょうか？


CC BY-SA 3.0
2014-12-18T23:20:07.940
2065
2015-01-25T10:34:05.760
2015-01-25T10:34:05.760
30
question
c++ アルゴリズム
グラフ構造で節点にデータを入れたい


グラフの関心はノード間の位置と関係かと思います。ですので、各ノードはただのラベルがあれば良いはずです(該当本Figure
6-4の「v0」など)。まぁ実際にはインデックスで管理しますかね。

ですので、各ノードが何であるかについては、別の配列なりデータ構造などでラベルとの対応関係を管理するのはどうでしょうか。素直にするのであればインデックスで対応関係を取りますが、ハッシュテーブルなどを使っても良いのかもしれません。

どうしてもグラフ内に情報を持たせたいのでしたら、隣接行列に枝の距離を入れる代わりに、枝の距離と他の値を格納する構造体の参照を入れるということも考えられるのかなと思いました。(データを処理する部分では修正が必要となりますが）

隣接リストの場合は、素直に前者の戦略がよいように思います。(番号とデータを持った構造体で管理することも可能ですが、無駄に複雑になる気がします。)


CC BY-SA 3.0
2014-12-19T01:36:59.853
2077
2014-12-19T01:54:59.717
2014-12-19T01:54:59.717
3313
3313
2065
answer


隣接行列では,辺の情報を以下のように格納しました。

[code]

    int A[][]=
    {
         {0, 0, 0, 0, 0, 0},
         {6, 0,18, 0, 0, 0},
         {0, 0, 0, 0, 0, 0},
         {0, 0, 0, 0, 0, 9},
         {0, 0, 0, 0, 0, 0},
         {0, 0, 0,12, 0, 0}
    };
    
[/code]

ここで、接点の情報は以下のように表現できました。

[code]

    char B[][]=
    {
        {"v0"},
        {"v1"},
        {"v2"},
        {"v3"},
        {"v4"},
        {"v5"}
    };
    
[/code]

`B[3]`→`B[0]`の向でが繋がっているかを確認するには、`A[3][0]`を確認します。この方法でどうにかなりました。


CC BY-SA 3.0
2014-12-19T03:08:12.887
2086
2015-01-24T07:51:26.770
2015-01-24T07:51:26.770
2065
answer