构造最小生成树，就得依靠特定算法，其核心在于从完整的图里挑出边的成本最小的那个子集，如此一来，生成的图才能保证各个节点全部连通。查找图的最小生成树时，有个常用的方法叫 Prim 算法，这一算法可是由好些人各自独立琢磨出来的，其中就包括计算机科学家 R.C. Prim 以及数学家 Vojteˇch Jarník 。Prim 算法的运行流程，与 Dijkstra 算法颇有几分相似，都是围绕着未访问节点的集合展开运作，一步一步地逐个构建节点，进而形成最小生成树。
Prim 算法启动之初，面对的是一整套尚未被访问的所有节点，接着随机选定一个节点率先进行访问，而这个被率先访问的节点，就成了构建最小生成树的起始点。在后续的每一轮迭代当中，算法都会在那些还没被访问过的节点里头，找出边权重最小的那个节点，前提是这个节点的边权重必须小于之前已经访问过的任意节点的边权重。算法还会找出这类节点：“距离我们已有的节点集合边缘最近，能以最低成本添加入集合”。随后，算法就把这个新发现的节点从未访问节点集合里剔除出去，再把与之对应的那条边，添加到成本最低的生成树当中。就这样，算法持续不断地逐一添加节点与边，每一轮迭代完成一个操作，直至把所有节点统统访问完毕。
Prim 算法运行过程中，每个节点最多被访问一回，每条边最多被检测两次，也就是分别从边的两端各考虑一次。而且，针对每一个节点而言，当以标准heap来实现优先队列时，我们或许会看到有多达 |V| 次的节点插入或者更新操作。综合这些因素，该算法的总体成本大致为 （|V| + |E|）× log （|V |）。
不妨把 Prim 算法具象化地想象成这么一个场景：有一家建筑公司承接了一项工程，要对群岛之间的桥梁进行升级改造。这家公司打算把连接群岛的那些破旧腐朽的木桥，全都换成崭新的现代化桥梁。由于旧木桥根本承载不了施工设备的重量，站在建筑公司的角度来看，只有靠新建的桥梁连接起来的岛屿，才算是真正意义上实现了连通。并且，合同里明确规定，到最后，任意两座岛屿之间，都得能够通过一座新建的现代化桥梁顺利抵达。
在 Prim 算法具体推进的每一个环节当中，我们都得时刻留意那些尚未连接起来的节点，同时密切追踪连接它们时所能采用的最优边权重情况。为此，我们借助自定义的 PriorityQueue（优先队列）实现方式来管理、维护这些关键数据，这种自定义实现手段为我们提供了一套行之有效的机制，能够便捷地在队列里查找特定数值，还能灵活地对各项优先级进行调整修改。就当前这段涉及的代码而言，大家只需掌握几个基础操作就够了：将元素项目插入到优先级队列里，以及从优先级队列当中移除项目，还有就是修改元素的优先级。
def prims(g: Graph) -> Union[list, None]: pq: PriorityQueue = PriorityQueue(min_heap=True) last: list = [-1] * g.num_nodes mst_edges: list = [] pq.enqueue(0, 0.0) for i in range(1, g.num_nodes): pq.enqueue(i, float('inf')) while not pq.is_empty(): index: int = pq.dequeue() current: Node = g.nodes[index] if last[index] != -1: mst_edges.append(current.get_edge(last[index])) elif index != 0: return None for edge in current.get_edge_list(): neighbor: int = edge.to_node if pq.in_queue(neighbor): if edge.weight < pq.get_priority(neighbor): pq.update_priority(neighbor, edge.weight) last[neighbor] = index return mst_edges
