c++ - 计算二分图中的路径数（长度 N）

Question

我目前正在通过进行深度优先搜索（最多 10 个级别）来计算二分图中长度为 $n$ 的路径数。但是，我的实现需要 5 分钟以上的时间才能从具有 3000 多个元素的二部图中计算出 700 万条长度为 5 的路径。我正在寻找一种更有效的方法来解决这个计数问题，我想知道文献中是否有这样的算法。

这些是无向二部图，因此路径中可能存在循环。

我的目标是计算在一分钟内包含 100 万个元素的二分图中长度为 $n$ 的路径的数量。

提前感谢您提供任何建议的答案。

Answer 1

我同意第一个想法，但它并不完全是 BFS。在 BFS 中，您通过每个节点一次，在这里您可以进行很多次。
您必须保留 2 个数组（我们称其为 Cnt1 和 Cnt2，Cnt1 是您到达一个元素的次数并且您的路径长度为 i，Cnt2 相同，但长度为 i + 1）。第一次，所有元素在 Cnt2 中为 0，在 Cnt1 中为 1（因为从每个节点开始都有一条长度为零的路径）。

重复 N 次：
遍历所有节点
对于当前节点，您遍历所有连接的节点，并为每个您在 Cnt2 上的位置添加您到达 Cnt1 中当前节点的次数。
当您完成所有节点后，您只需将 Cnt2 复制到 Cnt1 并将 Cnt2 设为零。
最后，您只需添加 Cnt1 的所有数字，这就是答案。

Answer 2

转换为广度优先搜索，每当您有 2 条路径以相同长度通向同一节点时，只需跟踪有多少这样的路径，而不是如何到达那里。

这将避免大量重复工作，并且应该提供显着的加速。（如果n不小，有更好的加速，请继续阅读。）

n我的目标是计算一分钟内包含 100 万个元素的二分图中的长度路径数。

嗯，祝你好运？

另一种研究方法是，如果你取图的邻接矩阵，并将其提升到 n 次方，你得到的矩阵的所有条目都是从一个地方开始的长度 end 的路径数，结束在另一个。所以你可以走捷径，比如重复平方。方便，不是吗？

不幸的是，一百万个元素图会产生一个具有 10^12 个条目的邻接矩阵。用简单算法将两个这样的矩阵相乘应该需要 10^18 次操作。当然，我们有更好的矩阵乘法算法，但你仍然没有低于 10^15 次操作。这肯定不会在 1 分钟内完成。（如果您的矩阵足够稀疏，您可能会有机会，但您应该对该主题进行一些研究。）