C语言实现Prim最小生成树算法

"最小生成树的C语言实现——基于Prim算法" 在图论中，最小生成树（Minimum Spanning Tree, MST）是一个重要的概念，它指的是在一个加权无向图中，连接所有顶点的树形子图，其边的权重之和尽可能小。这个子图必须是连通的，并且没有环路。在实际应用中，最小生成树常用于网络设计、优化问题等领域。 本程序是使用C语言实现的Prim算法来寻找一个图的最小生成树。Prim算法是一种贪心算法，它的基本思想是从一个顶点开始，逐步添加边，每次添加一条与当前生成树连接的具有最小权重的边，直到包含所有顶点。 首先，定义了一个结构体`MGraph`来存储图的相关信息，包括顶点数组`vex`、邻接矩阵`arcs`、顶点数`vexnum`和边数`arcnum`。`LocateVex`函数用于在顶点数组中找到给定顶点的索引，便于后续操作。 接着，`CreatGraph`函数用于创建图。用户输入顶点数和边数，然后依次输入每个顶点的字符表示和每条边连接的两个顶点及对应的权重。邻接矩阵初始化为极大值`INT_MAX`，这样在遍历边时，可以将未连接的边视为权重无穷大。通过`LocateVex`函数获取边两端顶点在数组中的位置，更新邻接矩阵的权重，并保持邻接矩阵是对称的。 在Prim算法实现部分，程序首先定义了`closedge`结构体，用于存储顶点及其到已生成树的最低成本。`minimum`函数用于找出这些顶点中具有最小成本的顶点索引。在Prim算法的主循环中，初始时将起始顶点的低cost设为0，其他顶点设为无穷大。然后在每次迭代中，更新与当前生成树相邻的顶点的成本，如果找到更低的成本，就更新最小值并记录顶点索引。重复此过程，直到所有顶点都被包含在生成树中。 在实际运行时，需要先调用`CreatGraph`函数构建图，然后调用Prim算法实现的函数（这部分代码没有给出），最终输出最小生成树的边和总权重。 Prim算法的时间复杂度通常为O(V^2)，其中V是顶点的数量。虽然不是最高效的算法（Kruskal算法有更优的时间复杂度O(E log V)，E是边的数量），但对于稠密图（边数量接近于顶点数量的平方）Prim算法仍然是一个可行的选择，因为它不需要排序边。