prim和kruskal算法的时间复杂度

### Prim 和 Kruskal 算法时间复杂度分析

#### Prim算法的时间复杂度
Prim算法用于构建最小生成树(MST)，其基本操作是从任意一个顶点开始，逐步扩展到其他顶点直到覆盖整个图。当采用邻接矩阵表示时，原始版本的Prim算法每次寻找连接已选节点集合与未选节点之间的最短边需要遍历所有可能的边，这使得它的时间复杂度达到\( O(V^2) \)[^1]。

然而，通过引入优先队列（通常基于二叉堆实现），可以在很大程度上提高效率。具体来说，在这种情况下查找并更新最近距离的操作可以从线性的\( O(V)\)降低到对数级别的 \(O(\log V)\)，因此整体性能提升到了\( O((V+E)\cdot\log V)=O(E\cdot\log V)\)，这里假定图形是稀疏的即\( E<V^2\) 。

对于稠密图而言，如果使用斐波那契堆作为优先级队列，则可以进一步减少至接近于线性时间复杂度\[ O(E+\alpha (V))]\)，其中α代表阿克曼函数反向形式，几乎恒等于常数值[1]。

#### Kruskal算法的时间复杂度
Kruskal算法同样旨在找到给定加权无向图中的MST。该方法首先按照权重升序排列所有的边，接着依次选取不形成环路的新边加入当前正在生长的森林中。由于涉及到按重量排序以及后续处理过程中频繁查询两个端点所属的不同子集问题，所以主要开销来自于这两个方面：

- 排序阶段：利用高效的排序技术如快速排序或归并排序可使这部分工作量控制在\( O(E\cdot\log E)\)内；
- 并查集维护：为了高效判断新增边是否会构成回路，应用路径压缩启发式策略下的并查集结构能够保证单次查找/合并操作平均耗时不超过\( O(\alpha (E,V))\) ，此处α再次指代上述提到过的极低增长速度的逆阿克曼函数[3]。

综上所述，考虑到实际应用场景中多数情况满足\( |E|\leqslant|V|^2\)的关系成立，那么最终得到Kruskal算法的整体渐近界大约为\( O(E\cdot\log E)=O(E\cdot\log V)\) [^3]。

def kruskal_mst(graph):
    edges = sorted([(weight, u, v) for u in graph for v, weight in enumerate(graph[u]) if weight != 0])
    
    parent = list(range(len(graph)))
    rank = [0]*len(graph)

    mst = []

    def find(node):
        if parent[node]!=node:
            parent[node]=find(parent[node])
        return parent[node]

    def union(u,v):
        rootU=find(u)
        rootV=find(v)
        
        if rootU!=rootV:
            if rank[rootU]>rank[rootV]:
                parent[rootV]=rootU
            elif rank[rootU]<rank[rootV]:
                parent[rootU]=rootV
            else:
                parent[rootV]=rootU
                rank[rootU]+=1
                
            mst.append((u,v))
            
    for w,u,v in edges:
        if find(u)!=find(v):union(u,v)
                
    return sum([w for w,_ ,_ in mst]),mst