前言

据说Boruvka算法是最古早的最短路算法，多半是真的。

为什么叫菠萝算法？不知道。多半是音译吧。

思路

这个算法需要执行多轮，直到生成最小生成树。

在每一轮中，对于每一个点（或者说，连通块），都找出以它为一个端点（或者说，一个端点在这个连通块中）的最短的边，并且将这条边加入最小生成树，并将其连接的两个点（连通块）合并。

每一轮中至少都可以使联通块数除二（因为每条边都连接了两个连通块，而最多只会有两条边重合。），故而时间复杂度是 \(O(logn)\) 的。

通常情况下，菠萝算法用于解决边特别多的情况，例如完全图。

细节以及模板暂缺

细节

模板

例题