Hi bobo 老师，

本节最后说 “Kruskal 算法的总体复杂度是 O(ElogE)，其中对边进行排序的复杂度是 O(ElogE)，从堆中取出边判断是否成环的复杂度是 O(ElogV)”。

不太明白“从堆中取出边判断是否成环”这个过程为什么是 O(ElogV) 的？这部分代码如下：

// 创建一个并查集, 来查看已经访问的节点的联通情况
UnionFind uf = new UnionFind(graph.V());
while( !pq.isEmpty() && mst.size() < graph.V() - 1 ){

    // 从最小堆中依次从小到大取出所有的边
    Edge<Weight> e = pq.extractMin();
    // 如果该边的两个端点是联通的, 说明加入这条边将产生环, 扔掉这条边
    if( uf.isConnected( e.v() , e.w() ) )
        continue;

    // 否则, 将这条边添加进最小生成树, 同时标记边的两个端点联通
    mst.add( e );
    uf.unionElements( e.v() , e.w() );
}

我的理解是：

• extractMin 本身的复杂度应该是 O(logE)，因为 while 循环执行了 graph.V() - 1 次，因此 graph.V() - 1 次 extractMin 就是 O(VlogE) 的复杂度。
• 带有路径压缩优化的并查集的复杂度接近 O(1)，那么 graph.V() - 1 次 isConnected 和 unionElements 就是 O(V) 的复杂度。
• 因此这部分代码总体复杂度应该是 O(VlogE) 。

不知道哪里分析的有问题？