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

Question

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

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

2. 上面的搜索可以限制在 my_nodes 对之间的路径。这只会在很小的程度上降低复杂性。再加上它需要很多 python 循环，这很慢

有没有更快的解决方法？

Answer 1

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

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

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

然而，在有向图的情况下，"merge" 会稍微复杂一些，但仍然可以完成，但在这种情况下，最坏的情况可能会花费很多时间。

更新:

正如你所说的图是有向的，上面的方法是行不通的。在这种情况下，您可以像这样简化您的任务：

• 如果您需要一些开箱即用的解决方案，请找到 strongly connected components in graph (I suggest you to implement it by yourself, e.g., Kosaraju's algorithm). The complexity is O(E + N). You can use a NetworkX method for this。
• 根据步骤1的信息，创建图的浓缩，并保存有关可以从其他组件访问的信息。同样，这里有一个 NetworkX method。
• 现在你可以很容易地说，你的集合中的哪些节点在同一个组件中，因此肯定存在包含所有这些节点的路径。
• 之后，您需要检查的是节点的不同组件之间的连接性。例如，您可以获取 topological sort of condensation 并再次检查线性时间。