使用优先队列实现Prim算法与Dijkstra算法

"这篇资料主要讨论了最小生成树(MST)问题的一个扩展，并提供了一个用优先队列（prioirty_queue）实现Prim算法的代码示例。文章引用了北京大学郭炜教授以及郑聃崴的讲义内容。" 在图论中，最小生成树(Minimum Spanning Tree, MST)是一个重要的概念，它是指一个无向加权图中的一个子集，这个子集包含了图中的所有顶点，且其边的权重之和最小。在解决MST问题时，我们通常会使用几种经典算法，如Prim算法、Kruskal算法或Floyd算法等。 这里提到的是使用优先队列（prioirty_queue）来优化Prim算法。Prim算法是一种贪心算法，用于寻找连接图中所有顶点的最小生成树。算法的基本思想是从一个起点开始，逐步将未访问过的顶点加入到当前的生成树中，每次选择与当前生成树边权最小的边进行连接。 提供的代码`HeapPrim`函数实现了Prim算法。首先定义了一个结构体`XEdge`来存储边的信息，包括顶点`v`和权重`w`。接着，`<`运算符重载用于比较边的权重，使得优先队列总是保留权重较小的边。 在算法实现中，`G`是一个邻接列表，表示图的结构，`n`是顶点的数量。`vDist`数组存储每个顶点到已构建的树的距离，`vUsed`数组标记顶点是否已被加入到树中。初始时，所有顶点距离设为无穷大，未使用状态设为0。`nTotalW`用于累计最小生成树的总权重，`nDoneNum`记录已加入树的顶点数量。 算法的核心是一个循环，每次从优先队列中取出权重最小的边，如果该边的顶点尚未加入树中，则更新它的距离，并将与之相邻的、尚未加入树的顶点的边加入优先队列。直到所有顶点都被加入树中，或者优先队列为空，算法结束。 如果最后有顶点未被加入树中，说明图不连通，函数返回-1；否则返回最小生成树的权重和。 此外，资料还提到了使用优先队列实现Dijkstra算法的POJ3159题目，这表明优先队列在解决最短路径问题上也有广泛应用。Dijkstra算法是寻找图中单源最短路径的算法，而这里的实现可能是为了提高查找最短路径的效率。不过，Dijkstra算法的具体实现细节并未在这段摘要中展开。