最小生成树prim算法详解

最小生成树Prim算法是一种用于寻找无向加权图中最短路径连接所有顶点的算法。它是由秦尼斯·普里姆（Kruskal's Algorithm）提出的，但这里我们重点讨论Prim算法。

Prim算法的工作原理是这样的：
1. **初始选择**：从图中任意一个顶点（通常称为起点或根节点）开始，将该顶点标记为已访问，并将其与其他未访问顶点之间的边加入到当前“最小生成树”中。

2. **逐步扩展**：对于剩下的未访问顶点，从它们与已访问顶点相连的所有边中，找到一条最短边，将这条边所连接的新顶点添加到已访问集合，并更新最小生成树。

3. **重复步骤**：重复第二步，直到所有的顶点都被访问过。这个过程保证了每次新加入的边都是相对于当前已知树而言的最小权重边。

4. **最终结果**：最后得到的连通所有顶点的树就是最小生成树。

**伪代码示例**：

function Prim(graph):
    mst = {} # 初始化空最小生成树
    visited = set() # 已访问顶点集合
    start = choose_a_vertex(graph) # 选择起始顶点

    visited.add(start)
    for vertex in graph.vertices:
        if vertex not in visited:
            mst[vertex] = find_shortest_edge(vertex, start, graph)

    while len(visited) < len(graph.vertices):
        next_vertex = find_next_unvisited_min_edge(mst, graph)
        visited.add(next_vertex)
        update_mst(next_vertex, graph, mst)

    return mst