优先队列实现prim算法

优先队列实现Prim算法的思想是每次选择权重最小的边来构建最小生成树。下面是使用优先队列实现Prim算法的步骤：

1. 创建一个优先队列，并定义一个自定义的比较器，用于比较边的权重。比较器应该使得权重最小的边在队列的前面。

2. 初始化一个布尔数组vIsChoose，用于标记顶点是否已经被选择。

3. 随机选择一个顶点作为初始节点，并将其标记为已选择。

4. 将初始节点的所有相邻边加入优先队列。

5. 进入循环，直到优先队列为空或者已选择的顶点数等于图的顶点数减一（最小生成树的边数等于顶点数减一）为止。

6. 从优先队列中取出权重最小的边，如果该边连接的顶点未被选择，则将该边加入最小生成树，并将该顶点标记为已选择。

7. 将新选择的顶点的所有相邻边加入优先队列。

8. 重复步骤6和步骤7，直到循环结束。

9. 最终得到的最小生成树即为Prim算法的结果。

下面是一个使用优先队列实现Prim算法的Python代码示例：

import heapq

def prim(graph):
    n = len(graph)  # 图的顶点数
    visited = [False] * n  # 记录顶点是否已经被选择
    min_span_tree = []  # 最小生成树的边集合
    pq = []  # 优先队列，用于存储边

    # 选择初始节点
    start_node = 0
    visited[start_node] = True

    # 将初始节点的所有相邻边加入优先队列
    for neighbor, weight in graph[start_node]:
        heapq.heappush(pq, (weight, start_node, neighbor))

    # 循环直到优先队列为空或者已选择的顶点数等于图的顶点数减一
    while pq and len(min_span_tree) < n - 1:
        weight, u, v = heapq.heappop(pq)

        # 如果边连接的顶点未被选择，则将该边加入最小生成树
        if not visited[v]:
            visited[v] = True
            min_span_tree.append((u, v, weight))

            # 将新选择的顶点的所有相邻边加入优先队列
            for neighbor, weight in graph[v]:
                heapq.heappush(pq, (weight, v, neighbor))

    return min_span_tree

# 示例图的邻接表表示
graph = [
    [(1, 2), (2, 3)],  # 顶点0的相邻边：(1, 2)和(2, 3)
    [(0, 2), (2, 4), (3, 3)],  # 顶点1的相邻边：(0, 2)、(2, 4)和(3, 3)
    [(0, 3), (1, 4), (3, 5)],  # 顶点2的相邻边：(0, 3)、(1, 4)和(3, 5)
    [(1, 3), (2, 5)]  # 顶点3的相邻边：(1, 3)和(2, 5)
]

min_span_tree = prim(graph)
print(min_span_tree)  # 输出最小生成树的边集合