Prim算法：一种简单易懂的图算法
# Prim算法是一种广泛用于求解最小生成树的算法，它以一个节点作为起点，每次选择距离最短的边来扩展最小生成树，直到最小生成树包含所有的节点为止，下面我们将通过Python代码来介绍Prim算法的实现过程。
我们需要定义一个表示无向加权图的类，这个类包含一个表示节点列表和边列表的数据成员，以及一些用于操作图的方法，例如添加节点和边、查找节点和边等。
class Graph:
def __init__(self):
self.nodes = []
self.edges = []
def add_node(self, node):
if node not in self.nodes:
self.nodes.append(node)
def add_edge(self, edge):
u, v, w = edge
if u in self.nodes and v in self.nodes:
self.edges.append((u, v, w))
def get_node(self, node):
return self.nodes.index(node)
def get_edge(self, u, v):
for edge in self.edges:
if edge[0] == u and edge[1] == v:
return edge
return None接下来，我们来实现Prim算法，这个算法需要一个字典来存储已经访问过的节点和它们的最小距离，还需要一个列表来存储已经加入最小生成树的节点，我们首先从第一个节点开始，然后不断扩展最小生成树，直到所有的节点都被访问过。
import heapq
def prim(graph):
visited = {node: float('inf') for node in graph.nodes}
visited[0] = 0
mst = []
edges = [edge for edge in graph.edges if edge[0] in visited and edge[1] in visited]
heap = [(0, 0)] # (distance, node)
while heap:
distance, node = heapq.heappop(heap)
if distance > visited[node]: # 只处理距离更小的边
continue
visited[node] = distance
mst.append((node, distance))
for edge in graph.edges: # 查找所有与当前节点相邻的节点并计算距离
if edge[0] == node: # 只处理一条边即可，因为另一条边已经在visited字典中
neighbor = edge[1]
if neighbor not in visited or distance + graph.get_edge(node, neighbor)[2] < visited[neighbor]: # 只处理距离更小的边
visited[neighbor] = distance + graph.get_edge(node, neighbor)[2] # 更新距离
heapq.heappush(heap, (visited[neighbor], neighbor)) # 将新的节点加入堆中
return mst # 返回最小生成树和它的边的距离列表，按照距离从小到大排序，方便后续处理（例如输出）现在我们可以使用上面的代码来求解一个无向加权图的最小生成树，假设有一个包含5个节点和7条边的无向加权图，我们可以按照以下方式调用prim函数：
```python
