如何在使用BFS的無向雙向圖中找到最短週期？

Question

如何使用廣度優先搜索在簡單（未定向）的二分圖中找到最短週期？

Answer 1

在二分圖中，最短可能的圓至少有四條邊。由於您正在使用廣度優先搜索，因此只要您相應地增加行程，就會發現最佳搜索速度。所有可能的4條邊長路徑，所有可能的5條邊長路，等等。當你找到一個圓圈的路徑的時候，你就完成了，它是最短的，或者至少與那個獎品並列的。

保留探索的所有路徑，以便在搜索的每個循環中只增加1個邊。並使用BFS確保您已探索過所有路徑。