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 的所有数字相加即可得到答案。