algorithm - 可以使用二项式堆来查找图中的连通分量吗？

Question

二项式堆如何在查找图的连通分量时有用，它不能被使用，那为什么？

标签： algorithmmathgraphconnected-componentsbinomial-heap

Answer 1

我从未见过以这种方式使用二项式堆，因为通常使用深度优先搜索或广度优先搜索来找到图连接的组件，并且这两种算法都不需要您使用任何类型的优先级队列。当然，您可以通过将 DFS 或 BFS 的堆栈或队列替换为优先级队列来执行一种“优先级优先搜索”来查找连接的组件，但没有什么理由这样做。这会将查找连接组件的成本降低到 O(m + n log n)，而不是从普通 BFS 或 DFS 获得的 O(m + n)。

有一种方法可以让您轻描淡写地说二项式堆可能有用，那就是寻找连通分量的不同策略。或者，您可以使用不相交集森林来识别连接的组件。您从每个节点在其自己的分区中开始，然后为每个边调用联合操作以将节点链接在一起。完成后，您将得到一组树，每棵树代表一个连接的组件。

有许多策略可以确定如何在不相交的森林中链接树。其中之一是union-by-size，其中每当您需要选择要更改的代表时，您选择较小尺寸的树并将其指向较大尺寸的树。你可以证明可以用这种方式形成的最小的高度为 k 的树是秩为 k 的二叉树。这是通过配对所有节点，然后取出代表并将它们配对等形成的。（亲自尝试 - 不是很酷吗？）

但是，对我来说，这更像是一个巧合，而不是其他任何事情。这与二项式堆无关，而与二项式树有关，并且这种特殊形状仅在您正在寻找病态情况时才会出现，而不是在算法执行中理所当然地出现。

所以我最好的答案是“从技术上讲，你可以这样做，但你不应该这样做，从技术上讲，二叉树出现在与连接组件相关的其他上下文中，但这与使用二叉堆不同。”

希望这可以帮助！