特定の加重グラフが O(ElogV) で一意の MST (最小スパニング ツリー) を持っているかどうかを判断するアルゴリズム (またはその他の方法) を探していますか?
重みについては何も知りません (例: weight(e1) != weight(e2))。アルゴリズムは、このグラフに固有の MST が 1 つしかない場合は True を返し、そうでない場合は False を返します。
Kruskal のアルゴリズムを使用して開始し、find-set(u)==find-set(v) をチェックして、MST に円があるかどうかを確認しましたが、この方法では、思ったようにすべてのシナリオをカバーするわけではありません :(
どうもありがとう！トマー。