C++ : Storing weight for larger Graph

Question

我正在解决一些关于图表的问题。它需要存储 N 个节点的权重(N<=50000)。我不能使用矩阵来存储图形的权重(因为无法分配 50000x50000)。你知道其他方法吗？谢谢。

Answer 1

我首选的存储不太密集图的方法是使用邻接表。然而，使用邻接表的缺点是您无法直接检查节点 i 是否连接到节点 j。相反，您遍历节点 i 的所有邻居(如果 j 与节点 i 连接，它最终会出现)。去除边缘也是不切实际的。我在对图进行广度优先或深度优先搜索时使用它，因为人们只对邻居集感兴趣，而不对两个特定节点是否连接感兴趣。

总结:

1. 占用的内存与边数(这是您想要的)一样多，但至少占用与节点数一样多的内存。
2. 易于遍历任何节点的 egdes，即总是每个邻居的恒定时间
3. 要检查两个节点 i 和 j 是否相连，您需要遍历节点 i 或 j< 的整个邻域列表/em>。如果一个节点连接到几乎所有其他节点，这是不好的，如果连接到几个节点，则便宜
4. 删除边对于大社区来说也是昂贵的(在最​​坏的线性时间内，一个节点的邻居数量)而对于小社区来说是便宜的。
5. 插入边非常便宜(常数时间)

给大家举个例子(先所有权重1)

using Graph = std::vector<std::vector<int>>;

现在您可以创建一个包含 n 个节点的图表:

Graph mygraph(n);

如果你想连接节点 i 和 j 就这样做

mygraph[i].push_back(j);
mygraph[j].push_back(i);

要遍历某个节点的所有边，你可以简单地做

for (int neighbor : mygraph[i]) {
    std::cout << i << " is connected with " << neighbor << std::endl;
}

现在是更难的一般权重问题:

using Graph = std::vector<std::vector<std::pair<int, double>>>;
Graph myWeightedgraph(n);

现在你可以很容易地插入边

double weight = 123.32424;
myWeightedgraph[i].push_back({j, w});
myWeightedgraph[j].push_back({i, w});

对于遍历:

for (auto& neighbor : myWeightedgraph[i]) {
    std::cout << i << " is connected with " << neighbor.first << " with weight " << neighbor.second << std::endl;
}