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

这将如何实施？我意识到我可以使用二维数组来表示顶点之间的加权边，但我不确定如何表示顶点。

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

将邻接矩阵的索引作为顶点是常见的做法。

Answer 3

如果图中有固定数量的顶点。您可以将顶点声明为枚举并使用枚举的顶点名称直接索引数组。我认为它使映射更加清晰。

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 4

对于大多数意图和目的，将图表示为附属列表通常更有效：

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

所以 graph[i] 是 i 的所有相邻顶点。优点是在处理图时，我们通常希望遍历 i 的邻居。此外，对于大型稀疏图，空间复杂度要低得多。当然，这也可以扩展到包括权重，例如：

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

或者对于更复杂的类型，定义一个类型 Vertex...

编辑：如果您需要索引作为字符串，这可以通过选择 std::map 而不是 std::vector 轻松完成：

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;