简述
Kruskal 重构树是图的一种生成树,主要解决一类路径边权限制问题。Kruskal 重构树有按深度单调的性质,所以很容易就可以解决边权的取值限制。
建法
Kruskal 重构树的建造方法和 Kruskal 算法建最小生成树的方法非常类似,但是结构有所不同:Kruskal 重构树将边权变成点权,点权依深度变小。我们假设有一张这样的图:
Kruskal 重构树是图的一种生成树,主要解决一类路径边权限制问题。Kruskal 重构树有按深度单调的性质,所以很容易就可以解决边权的取值限制。
Kruskal 重构树的建造方法和 Kruskal 算法建最小生成树的方法非常类似,但是结构有所不同:Kruskal 重构树将边权变成点权,点权依深度变小。我们假设有一张这样的图: