C++：为更大的图存储权重

Question

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

Answer 1

如果两个节点之间不能有多条边：

首先想到一些系统如何给每个现有的边缘一个唯一的数字。
例如。对于 N 个节点和节点编号 netween 0 和 N-1，节点 A 和节点 B 之间的边可以简单地具有 A*N+B（例如，在 uint64_t 变量中）

然后做一个std::map的边，以计算出的数为键，权重为值。那里的大多数操作都有对数时间，这不如二维数组好，但仍然不错，而且你需要的内存要少得多。

Answer 2

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

总结：

只占用与边缘一样多的内存（这是你想要的）但至少与节点一样多的内存。
易于遍历任何节点的 egdes，即始终每个邻居的恒定时间
要检查两个节点 i 和 j 是否相连，您需要遍历节点 i 的整个邻域列表 或 j。如果一个节点连接到几乎所有其他节点，这是不好的，如果连接到几个节点，则便宜
删除边缘对于大社区来说也是昂贵的（在节点邻居数量的最坏线性时间）并且对于小社区来说便宜。
插入边非常便宜（常数时间）

给大家举个例子（先用所有权重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;
}

Answer 3

不能将大小为 10^9 的数组分配为静态内存。您应该改用 malloc。更好的是，您可以使用 adjacency list 来存储图形。

Answer 4

通常有两种表示图形的方法。正如您所说，第一个是使用邻接矩阵。优点是您可以轻松查看两个节点 i 和 j 是否已连接。缺点是 space 复杂性（O(V²) 其中 V 是顶点数）。

另一个是邻接表：对于每个顶点，您存储一个邻接表，其中包含从该顶点出来的每条边。显然，空间复杂度为 O(V + E) 其中 V 是顶点数，E边数。

请注意，您可以将边存储在邻接图中而不是列表中。假设您给每条边一个唯一的整数键。如果您的图形稀疏，则 std::unordered_map 会很合适，因为碰撞几率很低。对于给定的边，这使您平均 O(1) 查找和插入复杂度。

如果您的图可以有大量的边，那么只需使用依赖于红黑树的常规 std::map。然后，您将拥有插入或查找节点的对数复杂度。

下面是一些示例代码：

struct Edge {
    int weight;
    int start, end;
}
struct Vertex {
    int key;
    std::unordered_map<int, Edge> adjacency_map;
}
struct Graph {
    std::vector<Edge> edges;
}

C++：为更大的图存储权重

C++ : Storing weight for larger Graph

c++

graph

shortest-path