graph - 如何使用 BFS 在无向二部图中找到最短循环？

Question

如何使用广度优先搜索在简单（非有向）二部图中找到最短循环？

Answer 1

在二分图中，最短的圆至少有 4 条边长。由于您使用的是广度优先搜索，只要您相应地增加您的旅行距离，您就会很快找到最佳选择。所有可能的 4 条边长路径，所有可能的 5 条边长路径，依此类推。当您找到一条圆形路径时，您就完成了，它是最短的，或者至少与该奖品并列。

保持探索所有路径，以便在每个搜索循环中仅将这些路径增加 1 个边缘。并使用 BFS 确保您已经探索了所有路径。