Prime算法实现与最小生成树

"Prime算法的实现.docx" Prime算法，也称为普里姆算法，是一种在图论中用于寻找加权无向图的最小生成树的算法。此算法由捷克数学家Vojtěch Jarník于1930年提出，后由美国计算机科学家Edsger Dijkstra在1957年重新发现，并以普里姆的名字命名。该算法的核心思想是通过逐步合并两个顶点集，每次合并过程中选择权值最小的边，最终形成一个包含所有顶点的连通子图，即最小生成树。 在提供的代码中，可以看到Prime算法的C++实现。首先，定义了一个二维数组`edge`来存储无向图的边和它们的权重，以及一个一维数组`f`来表示每个顶点所属的集合。`f[i]`的值为负数表示顶点未被访问，正数表示已被访问。 `Find(int i)`函数用于查找顶点`i`所在的集合。如果`f[i]`为负，则表示顶点`i`还没有被访问，返回其值；如果是正数，则表示顶点已访问，返回1。 `Union(int i, int j)`函数用于合并两个顶点`i`和`j`所在的集合。当两个顶点属于不同集合时，将它们的标记值设为正数，表示它们现在属于同一个集合。 在`main`函数中，首先读取图的节点数`n`和边数`rout`，然后使用`memset`函数将`edge`数组的所有元素初始化为0。接着，循环读入每一条边的两个端点`a`和`b`以及它们之间的权重`c`，并将其存入`edge`数组中。 在寻找最小生成树的过程中，使用一个while循环，直到找到`(n - 1)`条边。每次循环，遍历所有边找到权值最小且未被使用的边`v1`到`v2`。这里，`s`变量记录已找到的边数，`min`变量存储当前找到的最小边的权重。如果这条边连接的两个顶点不在同一集合（通过`Find`函数判断），那么将这条边加入最小生成树，更新总权值`total`，输出边的连接信息，将边的权重设为负以表示已使用。 最后，输出所有边的总权值`total`，即最小生成树的权重。 举例来说，假设输出如下： ``` Output： 1--2 3 2--3 1 3--4 2 5--4 1 6--4 1 10 ``` 这表示找到了一个最小生成树，它包含了6条边，总权值为10。其中，边1-2的权值为3，边2-3的权值为1，边3-4的权值为2，边5-4的权值为1，边6-4的权值为1。这些边构成了一个加权最小的连通子图，覆盖了所有的节点。