概念：普利姆（prim）算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。
1.1 规则
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
1.2 图例
上图为原始的加权连通图。每条边一侧的数字代表其权值。
（1）顶点a被任意选为起始点。从a出发，有b.d.f与其直连，权值分别为2、5、3，b是距离a 最近的顶点，因此将a与ab高亮表示
（2）下一个顶点为距离a或b最近的顶点 ，由图可知，e距离b为2，c距离b为3，d距离a为5，f距离a为3，所以选择距离最近的顶点e，并将e与be高亮表示
（3） 同理可得，下一个顶点为f（或者c或者h），在这里我们选择f ,并将其顶点及对应的边高亮表示
（4）重复上述步骤，直到所有顶点都被选中。即得到最小生成树
1.3 算法实现
import heapq
def prim(graph):
"""
:param graph: 图的邻接表表示，格式为 {顶点: [(邻居, 权重), ...]}
:return: 最小生成树的边列表和总权重
"""
if not graph:
return [], 0
# 获取起始顶点（任意选择一个顶点）
start_vertex = next(iter(graph))
# 初始化：已访问顶点集合、最小堆（存储(权重, 当前顶点, 前一顶点)）、最小生成树边列表
visited = set([start_vertex])
heap = []
mst_edges = []
total_weight = 0
# 将起始顶点的所有邻接边加入堆
for neighbor, weight in graph[start_vertex]:
heapq.heappush(heap, (weight, start_vertex, neighbor))
# 当堆非空且未访问所有顶点时
while heap and len(visited) < len(graph):
# 弹出当前权重最小的边
weight, u, v = heapq.heappop(heap)
# 如果目标顶点已访问，跳过
if v in visited:
continue
# 将目标顶点标记为已访问，记录此边
visited.add(v)
mst_edges.append((u, v, weight))
total_weight += weight
# 遍历新加入顶点的所有邻接边
for neighbor, w in graph.get(v, []):
if neighbor not in visited:
heapq.heappush(heap, (w, v, neighbor))
return mst_edges, total_weight
# 示例用法
if __name__ == "__main__":
# 图的邻接表表示（无向加权图）
graph = {
'A': [('B', 2), ('D', 5)],
'B': [('A', 2), ('C', 4), ('D', 1)],
'C': [('B', 4), ('D', 3)],
'D': [('A', 5), ('B', 1), ('C', 3)]
}
mst_edges, total = prim(graph)
print("最小生成树的边:")
for u, v, w in mst_edges:
print(f"{u} - {v} : {w}")
print("总权重:", total)运行结果显示：
