graph - BFSを使用して、無向2部グラフで最短のサイクルを見つけるにはどうすればよいですか？

Question

幅優先探索を使用して、単純な（指示されていない）2部グラフで最短のサイクルを見つけるにはどうすればよいですか？

Answer 1

2部グラフでは、可能な最短の円は少なくとも4つのエッジの長さです。幅優先探索を使用しているので、それに応じて移動距離を増やす限り、最適なものを非常に速く見つけることができます。すべての可能な4エッジの長いパス、すべての可能な5エッジの長いパスなど。あなたが円である道を見つけた瞬間、あなたは終わりです、それは可能な限り最短であるか、少なくともその賞に結びついています。

検索の各サイクルでこれらのパスを1エッジだけ増やすように、すべてのパスを探索し続けます。また、BFSを使用して、すべてのパスを探索したことを確認します。