Prim算法的时间复杂度

Prim算法的时间复杂度取决于具体实现方式。朴素Prim算法的时间复杂度为O(V^2)，其中V为顶点数。堆优化的Prim算法的时间复杂度为O(VlogE)，其中V为顶点数，E为边数。在实际应用中，堆优化的Prim算法更常用，因为它的时间复杂度更低。

下面是基于最小堆数据结构实现Prim算法的Python代码，用于生成最小代价生成树：

import heapq

def prim(graph):
    # 初始化
    visited = set()
    min_heap = [(0, 0)]  # (cost, node)
    mst_cost = 0

    while min_heap:
        # 取出堆顶元素
        cost, node = heapq.heappop(min_heap)
        if node in visited:
            continue

        # 更新最小代价生成树的代价
        visited.add(node)
        mst_cost += cost

        # 将与当前节点相邻的未访问节点加入堆中
        for neighbor, cost in graph[node]:
            if neighbor not in visited:
                heapq.heappush(min_heap, (cost, neighbor))

    return mst_cost

该算法的时间复杂度为O(VlogE)，其中V为顶点数，E为边数。在最坏情况下，E可以达到V^2，此时时间复杂度为O(V^2logV)。