prim最小生成树代码
时间: 2024-07-01 09:01:20 浏览: 13
Prim最小生成树算法是一种用于寻找无向加权图中一棵包含所有顶点且边权和最小的树的算法。下面是Prim算法的基本步骤:
1. 选择任意一个顶点作为起点(通常称为“初始顶点”),并将其加入到最小生成树中。
2. 对于起点的所有未加入的邻接顶点,计算它们到已加入树中最近顶点的距离(即边的权重)。
3. 选择距离最小的那个邻接顶点,并添加一条连接它们的边,将这个顶点加入到生成树中。
4. 更新所有新加入顶点的邻接顶点的距离,重复步骤3,直到所有顶点都被加入或者没有更优的选择。
5. 算法结束,生成的树就是最小生成树。
以下是一个简单的Python版本的Prim算法实现:
```python
import heapq
def prim(graph, start):
mst = {} # 存储最小生成树边及其权重
visited = {start: 0} # 记录已访问顶点及其到起点的距离
heap = [(0, start)] # 优先级队列,堆顶元素是距离最小的边
while heap:
current_weight, current_node = heapq.heappop(heap)
if current_node not in mst: # 如果节点首次访问
mst[current_node] = current_weight
for neighbor, weight in graph[current_node].items():
if neighbor not in visited or weight < visited[neighbor]:
visited[neighbor] = weight
heapq.heappush(heap, (weight, neighbor))
return mst
# 示例用法
graph = {
'A': {'B': 2, 'C': 3},
'B': {'A': 2, 'D': 4},
'C': {'A': 3, 'D': 1},
'D': {'B': 4, 'C': 1},
}
mst = prim(graph, 'A')