Kurskal重构树
学习博客(推荐)
瓶颈
我们定义图上\(u \longrightarrow v\)路径的瓶颈为，这条路径上边权的最大值。
我们希望求出，一幅图上任意两点之间的最小瓶颈路。
由于，若两点之间存在至少一条路径，那么这两点间的最小瓶颈路至多只有一条。
最小瓶颈路
无向图\(G\)中\(x\) 到\(y\)的最小瓶颈路是这样一条简单路径，满足这条路径上的最大边权在所有\(x\)到\(y\)的简单路径中是最小的。
关键点:两个点之间所有简单路径上的最大边权的最小值。
Kruskal算法:
- 将所有边按照边权大小升序排序。
- 按上述升序遍历所有边，边的两点若存在至少一点不在最小生成树上，那么我们将该边加入最小生成树中。否则继续。
- 当加入树中的边数达到点数\(-1\)时，即可退出遍历，最小生成树构造成功。
思考一下上述实现过程，我们不难发现，加入边时我们用的操作是并查集的合并操作，即合并两个连通块。
此时，我们加入的这条边是按照上述算法找到的，那么按照\(kruskal\)的实现，我们能发现，此时的边权\(w_i\)一定大于等于之前的所有边，同时一定小于等于之后的所有边(按升序遍历的顺序)。
之前的边没有使得\(x和y\)连通，也就是说，\(w_i\)就是使\(x,y\)两点连通的最小瓶颈。
由此，我们能通过\(Kruskal\)从原图中找到\(n -1\)条边，这些边就是两两点之间的最小瓶颈路。
重构树
如果在合并两点的时候，我们建立一个新结点作为两点共同的父节点(像二叉树一样，该父节点的权值为边权)，这样子合并，我们最终会得到一颗叶子结点全为真结点\((n个来自原图得到点)\)，非叶子结\((有n-1条边所以有非叶子结点的数量也是n-1)\)就是边权点的二叉树。
重构树的性质：
我们定义\(f(x,y)\)表示\(x,y\)两点最小瓶颈路的瓶颈，\(w(x)\)表示结点\(x\)的权值，当然，叶子结点不是边转化而来，没有权值。
- \(f(x,y) = w(lca(x,y))\)。
\(lca(x,y)\)往下，二者之间没有路径。\(lca(x,y)\)往上，边权只会更大。
因为，先合并的连通块二者之间的边权肯定更小\((kruskal就是升序遍历)\)。