logo标签列表

Redis：实现加权有向图

graphredisgraph-theorysortedset
6

如何使用Redis实现带权图？

我们主要会在图上搜索最短路径（可能使用Dijkstra算法）

目前，我们考虑将边添加到Redis中。

对于每个节点，我们将节点ID作为键，参考节点的键的有序集合作为值，该节点在有序集合中的分数是边的权重。

您认为呢？请纠正我，但唯一的问题是，每次查询排序集合中的下一个节点都需要支付O(logn)而不是O(1)...

http://redis.io/commands/zrange

2个回答
3
获取排序集合中的下一项只有在逐个获取它们时才是O（log（n）），在这种情况下，与redis连接的延迟将比操作的复杂性更成问题。
对于大多数图形操作，您需要查看节点的所有边，因此在处理节点时将整个集合（或至少具有合适分数的集合）加载到本地内存中是有意义的。当然，这将意味着加载一些不会被跟随的边缘，因为您已经找到了合适的路径，但由于集合相当小，因此这样做的成本要比为每个需要的边缘制作新的redis调用低得多。
1

抱歉我来晚了:), 但我最近遇到同样的问题，我使用哈希模拟它。我同意Tom Clarkson的观点，即(几乎)所有东西应该被加载到本地内存中，并补充说，在空间效率方面的有效方法是使用哈希，将图形信息存储如下：

Graph = { node1 : { nodeX : edge_weight, nodeY : edge_weight, other_info: bla..},
          node2 : { nodeZ : edge_weight, nodeE : edge_weight, other_info: bla..},
          bla bla...
        }

如果您需要更多的空间和效率，可以压缩每个值（可以是JSON字符串...），然后在客户端代码中进行解压缩/导入/反序列化。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接