如何檢查最小生成樹

Question

如果給定樹是MST，如何檢查線性時間O（n）？

Answer 1

您是否熟悉過程Union-Find？ 如果你剛剛給出樹你只需要檢查它的連接圖是否與。我的意思是隻查詢它是否只有一個組件。 否則保持一個映射[pair<int,int>，int]或類似的散列庫來存儲兩個節點之間的最小權重，並比較給定樹的每個邊緣是否具有最小權重。 如果沒有，那麼你確定它不是MST，否則你會查找它是否連接。如果是，那麼它的MST。

在Union Find中使用樹縮短。並且查詢樹是否連接，你可以很容易地檢查每個邊在聯合之前，如果它已經聯合的原因，那麼你肯定有一個循環，它根本不是樹，所以不是MST。