图的数据结构
Data structures for graphs
我目前正在写硕士论文。这是关于图表的。我的算法准备好了。但现在我必须考虑有用的数据结构来表示图形和良好运行时所需的其余部分。由于内存大，我不允许使用邻接矩阵。由于我必须在每次迭代中检查某条边是否存在，因此邻接表也没有意义。
首先，我想到了两个相互嵌套的散列 table。所有节点都存储在第一个 table 中，所有相邻节点都存储在第二个中。
但是由于我必须能够在我的算法中选择一个随机邻居，所以这也不是最优的。
此外，我必须能够在算法的每次迭代中保存边缘权重。
包含所有基本操作的列表：
- 我需要边的演示文稿，如果存在某个边，我可以在 O(1) 中检查
- 我必须能够在 O(1) 中选择一个固定节点的随机邻居
- 我需要能够为 O (1) 中的边分配权重
- 我还需要找出O(1)中结的度数
我可以对所有操作使用不同的数据结构。不幸的是，我 运行 没主意了。
希望这里有人能帮助我。
提前致谢！
丽莎
我建议使用地图，它可以快速查找稀疏图中的顶点和边（相对于顶点数量而言，边很少）
每个顶点存储其出边的映射，以目标顶点索引为键。该图存储在顶点映射中，以顶点索引为键。
有关此设计的详细说明：https://github.com/JamesBremner/PathFinder2/wiki/cGraph-Class-Design
存储库还存储了实现该设计的 C++ 代码以及使用该设计的图论算法的许多实现。
我建议如下：
一种地图数据结构，其中的键作为哈希表实现，为您提供 O(1) access/insert/delete 时间。此地图的键将是您的节点。
这个地图数据结构的值将是集合，也实现为哈希表，给你 O(1) access/insert/delete 时间。这些集合的成员是键的相邻节点。
对于边的权重，您有几种选择。您可以将元组插入到邻接列表的集合中，其中第一个值是相邻节点，第二个值是连接这两个节点的边的权重。权重可以在 O(1) 时间内更新，因为映射和集合都是作为哈希表实现的。
您可以将节点的度数存储在单独的地图数据结构中，其中键（作为哈希表实现）是节点，值是度数。这将为每个节点的度数提供 O(1) access/delete/update 时间。
要实现连接到节点的随机边的 O(1) 时间，您需要使用额外的数据结构。原因是存储在集合中的边（作为哈希表）不会为我们提供在 O(1) 中获取随机数的方法。但是如果我们将每个节点的边存储在类似 list/array 的数据结构中，我们可以在 O(1) 中获得一个介于 0 和该数组长度之间的随机索引，并在 O(1) 中访问该边。
此方法将通过增加所需的 space 来满足您的时间复杂度要求，尽管 space 复杂度不会增加。
您可以创建 类 将它们组合在一个地方，而不是单独的数据结构。
如有必要，我可以添加简化的实现。
I need a presentation of the edges where I can check in O (1) if there is a certain edge exists
I need to be able to assign weights to the edges in O (1)
这是一个从边到权重的哈希映射。关键就是一对顶点号。如果这是一个 无向 图形，则对中的数字进行排序，使较小的在前。
I must be able to choose a random neighbor of a fixed node in O(1)
I also need to find out what the degree of a knot is in O (1)
这是从每个顶点到其相邻顶点数组的映射——即图的邻接表表示，确保每个邻接表都在支持随机访问的结构中。
有关 Graph 的完整而全面的数据结构，您可以查看 CXXGraph 库。
是一个易于阅读的开源 Header-Only 库。
我目前正在写硕士论文。这是关于图表的。我的算法准备好了。但现在我必须考虑有用的数据结构来表示图形和良好运行时所需的其余部分。由于内存大，我不允许使用邻接矩阵。由于我必须在每次迭代中检查某条边是否存在，因此邻接表也没有意义。
首先，我想到了两个相互嵌套的散列 table。所有节点都存储在第一个 table 中，所有相邻节点都存储在第二个中。 但是由于我必须能够在我的算法中选择一个随机邻居，所以这也不是最优的。 此外，我必须能够在算法的每次迭代中保存边缘权重。
包含所有基本操作的列表：
- 我需要边的演示文稿，如果存在某个边，我可以在 O(1) 中检查
- 我必须能够在 O(1) 中选择一个固定节点的随机邻居
- 我需要能够为 O (1) 中的边分配权重
- 我还需要找出O(1)中结的度数
我可以对所有操作使用不同的数据结构。不幸的是，我 运行 没主意了。
希望这里有人能帮助我。
提前致谢！
丽莎
我建议使用地图，它可以快速查找稀疏图中的顶点和边（相对于顶点数量而言，边很少）
每个顶点存储其出边的映射，以目标顶点索引为键。该图存储在顶点映射中，以顶点索引为键。
有关此设计的详细说明：https://github.com/JamesBremner/PathFinder2/wiki/cGraph-Class-Design
存储库还存储了实现该设计的 C++ 代码以及使用该设计的图论算法的许多实现。
我建议如下：
一种地图数据结构，其中的键作为哈希表实现，为您提供 O(1) access/insert/delete 时间。此地图的键将是您的节点。
这个地图数据结构的值将是集合，也实现为哈希表，给你 O(1) access/insert/delete 时间。这些集合的成员是键的相邻节点。
对于边的权重，您有几种选择。您可以将元组插入到邻接列表的集合中，其中第一个值是相邻节点，第二个值是连接这两个节点的边的权重。权重可以在 O(1) 时间内更新，因为映射和集合都是作为哈希表实现的。
您可以将节点的度数存储在单独的地图数据结构中，其中键（作为哈希表实现）是节点，值是度数。这将为每个节点的度数提供 O(1) access/delete/update 时间。
要实现连接到节点的随机边的 O(1) 时间，您需要使用额外的数据结构。原因是存储在集合中的边（作为哈希表）不会为我们提供在 O(1) 中获取随机数的方法。但是如果我们将每个节点的边存储在类似 list/array 的数据结构中，我们可以在 O(1) 中获得一个介于 0 和该数组长度之间的随机索引，并在 O(1) 中访问该边。
此方法将通过增加所需的 space 来满足您的时间复杂度要求，尽管 space 复杂度不会增加。
您可以创建 类 将它们组合在一个地方，而不是单独的数据结构。
如有必要，我可以添加简化的实现。
I need a presentation of the edges where I can check in O (1) if there is a certain edge exists
I need to be able to assign weights to the edges in O (1)
这是一个从边到权重的哈希映射。关键就是一对顶点号。如果这是一个 无向 图形，则对中的数字进行排序，使较小的在前。
I must be able to choose a random neighbor of a fixed node in O(1)
I also need to find out what the degree of a knot is in O (1)
这是从每个顶点到其相邻顶点数组的映射——即图的邻接表表示，确保每个邻接表都在支持随机访问的结构中。
有关 Graph 的完整而全面的数据结构，您可以查看 CXXGraph 库。 是一个易于阅读的开源 Header-Only 库。