C++实现Prim算法求最小生成树

本文档主要介绍了图的最小生成树算法，这是一种在无向加权图中找到一棵包含所有顶点且总权重最小的树的问题。该算法通常被称为Prim算法，是解决最小生成树问题的一种经典方法。算法的核心思想是通过优先队列（这里使用了C++中的`priority_queue`）来维护当前未加入最小生成树的节点中距离最近的边，然后逐步添加这些边构建最小生成树。 首先，定义了一些必要的数据结构和变量： 1. `#define_CRT_SECURE_NO_WARNINGS`：取消编译器对可能的安全警告。 2. `n` 和 `m` 分别表示图中的顶点数和边数，`N` 和 `M` 是预设的最大值。 3. `st` 数组用于标记节点是否已加入最小生成树。 4. `dist` 数组记录每个节点到最小生成树的距离，初始化为极大值。 5. `h` 和 `e`、`ne`、`idx`、`w` 分别表示邻接表结构，存储图的边的信息，包括起点、终点、边的权重和指向下一个边的指针。 `add` 函数用于在邻接表中添加边，它将边的终点、权重和连接关系分别存储到相应的数组中。 `Prim` 函数是算法主体，步骤如下： 1. 初始化结果 `res` 为0（最小生成树的权值和），计数器 `cnt` 为0，创建一个优先队列 `heap` 以存储距离信息，并将节点1及其距离0放入堆中。 2. 当堆非空时，持续执行以下操作： a. 取出堆中距离最小的节点 `ver` 和其对应的距离 `destination`。 b. 检查 `ver` 是否已加入最小生成树，若已加入则跳过。 c. 将 `ver` 标记为已加入，更新最小生成树的权值和和边数。 d. 遍历 `ver` 的所有邻接边，更新未加入最小生成树的节点 `u` 的距离，如果新距离更小，则将其加入堆。 通过这个过程，Prim算法不断选择与当前生成树相连的边，使得整个过程结束后，我们得到的是一棵包含所有顶点且总权重最小的树。这种算法时间复杂度为O((V+E)logV)，其中V是顶点数，E是边数，是一种高效的求解最小生成树的方法。