c++ - 加重グラフを実装する

Question

次の隣接行列があるとします。

  A B C D
A 0 9 0 5
B 9 0 0 0 
C 0 0 0 2
D 5 0 2 0

これは実際にどのように実装されますか？2D配列を使用して頂点間の重み付きエッジを表現できることはわかっていますが、頂点を表現する方法がわかりません。

int edges[4][4];
string vertices[4];  

これはそれを行う方法ですか？頂点配列のインデックスは、エッジ配列の行インデックスに対応します。

Answer 1

二次元で使えますstd::map

この方法を使用すると、必要に応じてマトリックスを拡大および縮小できます。

#include <map>
#include <string>
#include <iostream>

int main()
{
    std::map<std::string, std::map<std::string, int>> vertices;

    vertices["A"]["A"] = 0; vertices["A"]["B"] = 9; vertices["A"]["C"] = 0; vertices["A"]["D"] = 5;
    vertices["B"]["A"] = 9; vertices["B"]["B"] = 0; vertices["B"]["C"] = 0; vertices["B"]["D"] = 0;
    vertices["C"]["A"] = 0; vertices["C"]["B"] = 0; vertices["C"]["C"] = 0; vertices["C"]["D"] = 2;
    vertices["D"]["A"] = 5; vertices["D"]["B"] = 0; vertices["D"]["C"] = 2; vertices["D"]["D"] = 0;

    std::cout << vertices["A"]["A"] << std::endl;
    std::cout << vertices["A"]["B"] << std::endl;
}

Answer 2

グラフに固定数の頂点がある場合。頂点を列挙型として宣言し、列挙型の頂点名を使用して配列に直接インデックスを付けることができます。マッピングが少し明確になると思います。

enum VERTEX
{
    A = 0,
    B,
    C,
    D,
    LAST = D
};

int edge[LAST+1][LAST+1];
edge[A][A] = 0;
edge[A][B] = edge[B][A] = 9;
edge[A][C] = edge[C][A] = 0;
// etc.

これにより、ルックアップペナルティなしで配列を使用できるようになり、物事を理解しやすくすることで、物事をシンプルかつ迅速に保つことができます。

Answer 3

頂点として隣接行列のインデックスを使用することは、一般的な方法です。

Answer 4

ほとんどの意図と目的では、通常、グラフを隣接リストとして表現する方が効率的です。

std::vector< std::list<int> > graph;

したがって、graph[i] は i のすべての隣接頂点です。利点は、グラフを扱うとき、通常は i の隣人をトラバースしたいということです。また、大規模なスパース グラフの場合、スペースの複雑さははるかに低くなります。もちろん、これを拡張して、次のような重みを含めることもできます。

std::vector< std::list<std::pair< int, int> > > graph;

または、より複雑な型の場合は、頂点型を定義します...

編集:文字列としてインデックスが必要な場合は、std::vector の代わりに std::map を選択することで簡単に実行できます。

std::map< std::string, std::list<std::pair< std::string /*vertex*/, int/*weight*/> > > graph;

しかし、元の投稿から、インデックスを頂点名にマップしたいだけのようです。その場合、最初の解決策を使用しますが、頂点名をインデックスにマップしたままにします。

std::vector< std::pair< std::string/*name*/, std::list<std::pair< int /*index*/, int/*weight*/> > > > graph;