给定一个无向连通图G=(V,E)，我们可能会需要寻找一个边的子集ST，这个子集组成的图仍然是连通的。如果我们要求ST中的边的权值总和最小，那么我们就遇到这个问题：最小生成树（MST）。
图6-19所示的Prim算法告诉我们如何从一个图中构造一个MST，这个方法使用一种贪心的策略，每一步，这个算法都朝着解前进，但是不会推翻之前的决定。在扩展一棵树T时，Prim算法每次添加一条边，直到生成MST（可以证明这是最小的）。它随机选择一个开始顶点s∈V，将s添加到一个集合S中，那么生成树T的根节点将会是s。Prim算法是贪心算法，每一次将一条边添加到T中，直到计算出MST。寻找一条权值最小的边（u,v），并且u∈S，v∈V-S，然后将这条边添加到MST中，将顶点v添加到集合S中。
图 6-19 Prim算法详解算法使用优先队列来存储V-S，V-S中的每个顶点v的优先级等于边（u,v）的最小值，其中u∈S。这个精心的设计得到了一个高效的实现。
解决方案
例6-9的C++实现是基于二叉堆的优先队列。一般来说，使用二叉堆会降低实现的效率，因为在主循环中检查是否一个顶点存在于优先队列（二叉堆不支持这个操作）将会很耗时间。但是，算法能够确保，顶点只会从优先队列中删除，所以我们只需要维护一个状态数组inQueue，这个数组在顶点从优先队列中取出时被更新。在另外一个优化实现版本中，我们维护一个外部数组key，记录队列中每一个顶点的优先级键值，这个值使得我们不需要从优先队列中寻找给定的顶点。
例6-9：基于二叉堆的Prim算法实现