最小生成树-prim

Prim算法是一种用于构建最小生成树的贪心算法。它的基本思想是从一个点开始，每次选择一个与当前生成树距离最小的点加入生成树，直到生成树包含了所有的点。具体实现过程如下：

1. 任选一个起始点加入生成树中。
2. 找到与生成树相邻的所有边中权值最小的那条边，将其连接的点加入生成树中。
3. 重复第二步，直到生成树包含了所有的点。

下面是一个Python实现的例子：

def prim(graph):
    # 初始化
    nodes = list(graph.keys())
    visited = [nodes[0]]
    edges = []
    # 直到所有节点都被访问
    while len(visited) < len(nodes):
        # 找到所有与visited中的节点相邻的边
        candidate_edges = []
        for node in visited:
            for edge in graph[node]:
                if edge[0] not in visited:
                    candidate_edges.append((node, edge[0], edge[1]))
        # 找到权值最小的边
        min_edge = min(candidate_edges, key=lambda x: x[2])
        # 将连接的点加入visited中
        visited.append(min_edge[1])
        # 将边加入edges中
        edges.append(min_edge)
    return edges

其中，graph是一个字典，表示图的邻接表。字典的键是节点，值是一个列表，表示与该节点相邻的边。每条边是一个元组，包含两个元素，第一个是连接的节点，第二个是边的权值。