如何在给定中间节点数量的情况下查找图中两个节点之间的所有路径？

Question

我有一个巨大的有向图，大约有一百万个节点和超过一千万条边。这些边没有权重。该图是一个类似于小世界的图。实际上，我看到每个节点（平均而言）与另一个节点相连需要通过三个中间节点。

鉴于这个图，您能否想出一种快速算法，返回起始节点和目标节点之间的所有路径（不包括循环），但只限于给定的最大中间节点数N（在我的情况下，N大多数时候将在0和3之间）？

- asmaier

Answer 1

如果你的图是无向图，你肯定希望进行双向广度优先搜索。对于长度为2的路径，枚举起始节点和结束节点的边，并查看它们的交点在哪里。对于长度为3的路径，从度数较小的终点深度为2，在度数较大的节点上深度为1。

由于您的图是有向图，您可能还希望保留反向边，以便可以使用相同的技巧。

- Rob Neuhaus

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

完成后不要忘记清空表格！将所有操作作为一个事务并回滚可能是最简单的方法。

- PaulMurrayCbr