给定具有x或y（其中x小于y且两者都是正整数）的成本边的未连通的连通图，在O（V + E）中找到MST
这个想法涉及使用两个DFS运行并将较低权重的节点折叠成超级节点（在第一次DFS运行之后），但我不完全确定。任何帮助表示赞赏。我已经看到这样的解决方案在几个答案中暗示，但无法在任何地方找到它的解释。
我认为你的直觉是正确的，可以找到一个无向连通图的MST，运行时间为O（V + E）。有一种称为Kruskal的算法可以计算O（V +Eα（V））中无向图的MST，α（V）是Ackermann函数的逆矩阵，其生长非常缓慢。 Kruskal算法达到O（V +Eα（V））的方式是使用union-find数据结构。 Union-find是一种数据结构，用于跟踪已分割为不相交子集的元素。当在该数据结构中搜索元素（find（x））时，树被压缩，使得根和X之间的每个节点的指针从其父节点切换到树的根节点。 union（x，y）函数使用find来确定节点是否属于压缩过程中的树的相同子集（如果它们是单独的树）则它们被组合。具有较低等级（树的高度）的树被移动以指向较大等级树的根。 Kruskal使用union-find数据结构来检查顶点是否已连接。一般来说，Kruskal的工作是将所有顶点添加到union-find数据结构中，然后连续添加最低边缘，假设它们按递增顺序排序。添加最低边时检查顶点是否连接，如果不添加该边并在两个顶点之间执行并集。