tree - 最小スパニングツリーを確認する方法

Question

指定されたツリーがMSTである場合、線形時間O（n）をチェックインするにはどうすればよいですか？

Answer 1

Union-Findのプロセスに精通していますか？ツリーが与えられたばかりの場合は、その連結グラフかどうかを確認する必要があります。コンポーネントが1つしかない場合はクエリするだけです。それ以外の場合は、map [ pair<int,int>、int]または同様のハッシュライブラリを維持して、2つのノード間の最小の重みを格納し、指定されたツリーの各エッジが最小のワイトであるかどうかを比較します。そうでない場合は、MSTではないことを確認します。そうでない場合は、接続されているかどうかを調べます。はいの場合、そのMST。

ユニオン検索でツリーショートを使用します。また、ツリーが接続されているかどうかを問い合わせるには、結合する前に各エッジを簡単に確認できます。すでに結合されている原因があれば、サイクルがあり、ツリーがまったくないので、MSTはありません。