data-structures - 与えられたグラフから、最小ではないスパニング ツリーを見つけます

Question

グラフで最小ではないスパニング ツリーを見つける方法 (可能な場合)

Answer 1

最小かどうかに関係なく、任意のスパニング ツリーを見つけることが目標である場合は、プレーンなバニラ DFS または BFS をいつでも使用してグラフを検索し、新しく発見されたノードにエッジを追加してスパニング ツリーを構築できます。これは、グラフのサイズに比例して時間内に実行され、実際には高速であり、コーディングも簡単です。

特に MST ではないスパニング ツリーを見つけることが目標の場合は、通常の MST アルゴリズムを実行することを検討できますが、エッジの重みを比較するときは、常に比較の結果を逆にします。これにより、グラフ内のすべてのスパニング ツリーがたまたま最小でない限り、最小スパニング ツリーにはならない最大スパニング ツリーが見つかります。これには、通常の MST アルゴリズムを実行するのと同じ時間がかかるため、使用するアルゴリズムを選択できます。