十亿节点无环无向图中从正k边源节点寻找目的节点的算法/方法

Question

假设我有一个由十亿个节点组成的邻接列表，使用哈希表按以下方式排列：

key=源节点
值=哈希表{node1，node2，node3}

输入值来自文本文件，格式为
从，到
1,2
1,5
1,11
... 以此类推

例如。 键='1'
值={2'，'5'，'11}
表示1连接到节点2、5、11

我想知道一个算法或方法来寻找目的地节点从源节点的正k边在一个无圈的十亿个节点的无向图

例如，从节点1开始，我只想找到节点50，直到深度3或直到3个边。

我的假设算法找到1-2-60-50这是最短的路径，但如何遍历是有效的使用上述邻接列表结构？ 我不想使用Hadoop/Map-Reduce。你知道吗

我在Python中提出了如下简单的解决方案，但效率不高。唯一的问题是哈希表搜索O（1）中的键，所以我可以直接搜索邻居和它们的十亿邻居来查找键。下面的算法需要很多时间。你知道吗

1. 从源节点开始
2. 使用哈希表搜索查找密钥
3. 使用邻居节点的哈希表再深入一层，找到目标节点的值，直到找到节点为止
4. 如果在k深度上找不到节点，则停止

&；nbsp1
&；nbsp  |
{2&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；5&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&  &；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp；nbsp&；nbsp&；nbsp；nbsp&；nbsp；nbsp&；nbsp&；nbsp&；nbsp&；nbsp {3,6,7}{节点}{节点}。。。。连接的节点
&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp&；nbsp；nbsp&；nbsp；nbsp&；nbsp；nbsp&；nbsp&；nbsp；nbsp&；nbsp&；nbsp；nbsp {节点}{节点}{节点}。。。。百万个连接节点。

请建议。上面实现的类似于BFS的算法需要3个多小时来搜索所有可能的键值关系。是否可以用其他搜索方法减少？你知道吗

Answer 1

正如您所暗示的，这在很大程度上取决于系统的数据访问特性。如果您被限制在单一元素访问，那么您将真正陷入困境，正如trincot观察到的那样。但是，如果您可以管理块访问，那么您就有机会进行并行操作。你知道吗

但是，我认为这超出了您的控制范围：hash函数拥有邻接特性，事实上，它很可能会“悲观”（与“optimize”相反）该特性。你知道吗

我确实看到了一个可能的希望：使用迭代而不是递归，维护要访问的节点列表。在列表中放置新节点时，获取其哈希值。如果可以按位置组织聚集的节点，则可以执行块传输，在一次读取操作中访问多个值。你知道吗