C语言实现最小生成树：Prim算法与示例

最小生成树是图论中的一个重要概念，它是指在一个加权无向图中找到一棵包含所有顶点且边权之和最小的树。在数据结构课程设计中，最小生成树问题通常作为算法实现的一部分，特别是用于解决诸如医院选址等实际优化问题，其中需要考虑成本效益和连通性。 本代码片段是用C语言实现的，主要涉及以下几个关键函数： 1. `CreateUDN(iGraph& G)`：此函数用于创建一个无向邻接矩阵（Undirected Adjacency Matrix）表示图G。用户首先输入顶点数量（vexnum）和边的数量（arcnum），然后存储顶点名称（vexs）以及每条边的连接顶点和权重（arcs）。通过遍历输入，为每个顶点分配存储空间，并构建边的连接信息。 2. `int LocateVex(iGraph G, char v)`：此函数可能是用于定位顶点的辅助函数，可能查找顶点在vexs数组中的索引。 3. `void PrintUDN(iGraph G)`：这可能是一个输出函数，用来显示无向邻接矩阵，帮助理解和验证图的结构。 4. `void MiniSpanTree_PRIM(iGraph G, closedge& minedge)`：Prim算法的核心部分，用于求解最小生成树。Prim算法是一种贪心算法，从一个起始顶点开始，逐步添加边，确保每一步都选择与当前树相连的、未加入的且权重最小的边，直到覆盖所有顶点。`closedge`结构体可能包含了顶点和对应的最低成本信息，minedge参数传递的是当前找到的最小边。 5. `void PrintMinEdge(iGraph G, closedge minedge)`：输出最小生成树中的一条边的信息，可能是边的两端顶点和对应的最低成本。 6. `int main()`：程序入口，初始化图G，调用CreateUDN函数创建图，接着执行Prim算法找到最小生成树，最后打印最小生成树的边。 这段代码提供了Prim算法在C语言中的应用示例，适合用于教学或作为实际项目的基础框架。通过运行这个程序，可以得到一个加权图的最小生成树，这对于理解和解决实际中的优化问题具有重要意义。例如，在医院选址问题中，最小生成树可以帮助确定如何以最小的成本连接所有医疗机构，同时保持良好的服务覆盖。