C++实现Kruskal与Prim算法：最小生成树

"这篇资源是关于使用C++编程语言实现最小生成树的Prim算法的程序。作者提供了完整的代码示例，包括创建图、Prim算法的实现以及主函数，旨在帮助对此感兴趣的学习者理解和实践。” 最小生成树是图论中的一个重要概念，它是在带权重的无向图中找到的一组边，这些边连接了所有的顶点，且总权重最小。在这个程序中，Prim算法被用来找到这样的树。Prim算法是一种贪心算法，它逐步地从一个初始顶点扩展到相邻的顶点，每次都添加一条与当前生成树边权最小的边。 在给出的代码中，首先定义了图的结构`MGraph`，包含顶点数组`vexs`、邻接矩阵`arcs`以及顶点数`vexnum`和边数`arcnum`。邻接矩阵`arcs`的每个元素`ArcCell`包含了边的权重（`adj`）和附加信息（`info`）。`closedge`结构体用于存储当前最小生成树中顶点的相邻顶点和低代价。 `CreateGraph`函数负责输入图的信息，包括顶点数、边数，以及每条边的权重。初始化邻接矩阵的所有边权重为88，然后从用户那里获取实际的边权重。 `MiniSpanTree_PRIM`是Prim算法的实现，它接受一个图`G`和一个起始顶点`u`作为参数。在这个函数中，Prim算法的核心是选择与当前生成树边权最小的边，并更新闭包表`closedge`，这个表记录了每个顶点的相邻顶点及其最低成本。 `LocateVex`函数用于根据顶点名找到其在图中的位置。`minimum`函数则找出闭包表中具有最小边权的边。 在`main`函数中，首先创建了图`G`，然后打印出图的邻接矩阵，最后调用Prim算法以顶点'a'开始构建最小生成树。 通过这段代码，学习者可以理解Prim算法的工作原理，也可以将此代码作为模板，根据自己的需求修改和扩展，例如实现Kruskal算法或者处理不同类型的图数据。同时，这也提供了一个实际应用C++编程解决图论问题的例子。