如何查找图中两个节点之间直到给定数量的中间节点之间的所有路径？

Question

我有一个巨大的有向图，约有一百万个节点和超过一千万条边。边缘未加权。该图是一个类似小世界的图。事实上，我看到每个节点（平均）通过三个中间节点连接到另一个节点。

给定这个图，你能想到一种快速算法，它返回起始节点和目标节点之间的所有路径（没有循环），但最多只能返回给定的最大数量 N 的中间节点（在我的情况下，N 大多数时候将是0 到 3 之间）？

Answer 1

如果您的图是无向的，您肯定会想要进行双向广度优先搜索。对于长度为 2 的路径，从起始节点和结束节点枚举边并查看它们相交的位置。对于长度为 3 的路径，从度数较小的终点开始 2 深度，在度数较大的节点上深度 1 层。

由于您的图是有向的，因此您可能还想保留反向边，以便可以执行相同的操作。

Answer 2

也许同时从两个方向呼吸第一？获取 A 的邻居和 B 的邻居。如果还没有找到链接，请将 A 添加到“a 的邻居”，将 B 添加到“B 的邻居”，然后查找两个集合之间的任何链接。

为了将其扩展至超过三个链接，“A/B 的邻居”列表需要包含更多内容。您将无法在内存中执行此操作 - 您需要一个临时表

whatever TRANSACTION_ID; (or use an ORACLE 1-per-session temp table)
boolean MY_BFS_WAS_ROOTED_AT_A;
int NODE_ID;
int previous_node_id;

（如果您在插入语句中检查循环，则不需要跟踪深度），

当存在任何

select from pathfinder a, pathfinder b
where a.taxn_id = foo and b.tnx_id=foo
and a.MY_BFS_WAS_ROOTED_AT_A = false
and b.MY_BFS_WAS_ROOTED_AT_A = true
and a.node_id = b.node_id

Don' 时，您已经找到了一条路径完成后别忘了清理桌子！将这一切作为一个事务完成并回滚可能是最简单的方法。