如何检查最小生成树

Question

如果给定树是MST，如何检查线性时间O（n）？

Answer 1

您是否熟悉过程Union-Find？ 如果你刚刚给出树你只需要检查它的连接图是否与。我的意思是只查询它是否只有一个组件。 否则保持一个映射[pair<int,int>，int]或类似的散列库来存储两个节点之间的最小权重，并比较给定树的每个边缘是否具有最小权重。 如果没有，那么你确定它不是MST，否则你会查找它是否连接。如果是，那么它的MST。

在Union Find中使用树缩短。并且查询树是否连接，你可以很容易地检查每个边在联合之前，如果它已经联合的原因，那么你肯定有一个循环，它根本不是树，所以不是MST。