python - 检查是否存在包含一组 N 个节点的路径

Question

给定一个图g和一组N个节点my_nodes = [n1, n2, n3, ...]，我如何检查是否存在一条路径包含所有 N 个节点？

1. 随着图形的增长，在 all_simple_paths 中检查包含 my_nodes 中所有节点的路径在计算上会变得很麻烦

2. 上面的搜索可以仅限于 my_nodes 成对对之间的路径。这仅在很小程度上降低了复杂性。另外它需要大量的Python循环，这非常慢

有没有更快的解决方案？

Answer 1

你可以在这里尝试一些贪心算法，从所有节点开始进行路径查找检查来查找，并逐步探索你的图。无法提供一些真实的示例，但伪代码应该是这样的:

• 从所有 n 个节点中启动 n 个路径 stub 来查找
• 对于所有这些路径 stub ，由之前未检查过的所有邻居调整它们
• 如果路径 stub 之间有一些交集，那么您就会得到一个新路径 stub ，它包含比以前更多的所需节点
• 如果合并 stub 路径后您拥有覆盖所有所需节点的路径，那么您就完成了
• 如果仍有一些其他节点需要添加到路径中，请再次继续第二步
• 如果图中没有剩余节点，则路径不存在

此算法的复杂度为 O(E + N)，因为您以非递归方式访问边和节点。

但是，在有向图的情况下，“合并”会稍微复杂一些，但仍然可以完成，但在这种情况下，最坏的情况可能需要很多时间。

更新:

正如您所说，图是有向的，上述方法效果不佳。在这种情况下，您可以像这样简化您的任务:

• 查找strongly connected components在图中(我建议您自己实现它，例如 Kosaraju's algorithm )。复杂度为O(E + N)。您可以使用 NetworkX method for this ，如果您想要一些开箱即用的解决方案。
• 根据步骤 1 的信息创建图的压缩，并保存有关哪个组件可以从其他组件访问的信息。同样，有一个 NetworkX method为此。
• 现在您可以轻松地说，集合中的哪些节点位于同一组件中，因此肯定存在包含所有这些节点的路径。
• 之后，您需要检查的只是节点的不同组件之间的连接性。例如，您可以获得 topological sort of condensation并再次检查线性时间。