c++ - クラスカルの組合を解決するにはどうすればよいですか

Question

グラフを調べて、ある ID のすべてのインスタンスを新しい ID に変更しようとしましたが、それでもサイクルが発生しました。非環式解を解く計画とは?

Answer 1

クラスカルのアルゴリズムで新しいエッジを追加するときに、サイクルが発生することはありません。同じコンポーネントをそれ自体に接続するエッジを追加する場合は、そのエッジをスキップします。最小スパニングツリーではないため、サイクルを取得することはありません。