北大数据结构上机实践5.1题：最小生成树求解与验证

本题是关于北京大学数据结构课程的上机实践考试试题5.1，主要涉及图论中的最小生成树（Minimum Spanning Tree, MST）算法。题目提供了一个二维数组`a`来表示一个有向图，其中每个元素`a[i][j]`代表从顶点`i`到顶点`j`的权重。该图的特性是矩阵的对角线元素表示无边，即`a[i][i] = -1`，并且输入的边的权重满足`i, j >= 0`且`w > 0`，限制了图的边的存在范围。 代码定义了三个函数：`read`用于读取用户输入的边及其权重，`MST`函数实现了Prim算法来找到最小生成树，`main`函数是程序入口，用于初始化数组、获取用户输入并调用`MST`函数。 在`read`函数中，用户会输入一系列的顶点编号`i`, `j`以及边的权重`w`。如果输入的值不在规定的范围内或不符合规则，程序会提示错误并跳过该条输入。当输入结束时，数组`a`将存储完整的边及其权重。 `MST`函数通过Prim算法的迭代过程逐步构建最小生成树。首先，它将起点（通常选择第一个非孤立节点，这里为`a[0][0] = -1`）的邻接节点标记为已访问。然后，函数在一个循环中查找当前未连接的节点中与已访问节点连接的最短边，更新最小边值`min_v`、对应的顶点索引`min_i`和`min_j`，并将其加入最小生成树。这个过程持续到所有节点都被访问过或者无法找到更短的边。最后，计算并输出最小生成树的总权重。 在`main`函数中，首先创建一个`a`数组，然后调用`read`函数读入边的信息，接着调用`MST`函数求解最小生成树。若算法正常运行，程序会输出最小生成树的边以及它们的总权重；如果图不连通或存在负权环，则输出错误信息并退出程序。 这道题考察了学生对于图的表示、Prim算法的理解以及对数据结构和算法逻辑的实现能力，是数据结构课程中经典问题的实践应用。理解并正确实现Prim算法对于解决此类问题至关重要，同时还需要考虑边界条件和错误处理，确保程序的健壮性。