1． 掌握最优子结构性质的证明方法<br>2． 掌握贪心法的设计思想并能熟练运用<br>二． 实验内容<br>用prim算法实验最小生成树<br>三． 算法思想<br>1． 初始化两个辅助数组lowcost和adjvex;<br>2． U={u0};输出顶点u0; //将顶点u0加入生成树中<br>3． 重复执行下列操作n-1次；<br>在lowcost中选取最短边，取adjvex中对应的顶点序号k；<br>输出顶点k和对应的权值；<br>U=U+{k};<br>调整数组lowcost和adjvex;<br>
最小生成树是图论中的一个重要概念，特别是在网络优化问题中有着广泛应用。它的目的是找到一个无向加权图的边集合，使得这些边连接了图中的所有顶点，并且这个边集合的总权重尽可能小。这样的边集合就被称为最小生成树。
在给定的描述中，提到了Prim算法，这是一种用于寻找最小生成树的贪心算法。Prim算法的思想是逐步构造最小生成树，每次添加一条与当前生成树连接并且权重最小的边。这个过程可以按照以下步骤进行：
1. 初始化：创建两个辅助数组lowcost和adjvex。lowcost数组用于存储每个顶点到已生成树的最小成本，adjvex则记录对应最小成本边的另一端顶点序号。同时，设定一个初始顶点u0，将其加入生成树中。
2. 迭代过程：重复执行n-1次（n为顶点总数），在每次迭代中，从lowcost数组中选择当前未加入生成树的顶点中的最小权值边，然后将对应的顶点k加入生成树，并更新lowcost和adjvex数组以反映新加入顶点的影响。
3. 调整数组：在每次迭代中，根据新加入的边，可能需要更新其他顶点到生成树的最短路径。这一步骤通常涉及遍历邻接矩阵或邻接表，如果发现有更短的路径，就更新对应的lowcost和adjvex。
在提供的源代码中，可以看到Prim算法的具体实现。`minVertex`函数用来找出未访问过的顶点中具有最小距离的顶点，`Prim`函数则是Prim算法的核心，它维护了一个距离数组D来存储每个顶点到生成树的最短距离，并通过不断更新这个数组来逐步构建最小生成树。在主函数中，用户可以输入图的边信息，然后调用Prim算法计算最小生成树。
最优子结构是算法设计的一个重要性质，它意味着一个问题的最优解可以由其子问题的最优解构造出来。对于最小生成树问题，最优子结构体现在每次添加的边都是当前状态下连接生成树和非生成树的最小边，这样最终得到的树是全局最小的。
贪心法是解决这类问题的一种策略，它每次做出局部最优的选择，期望最终能够达到全局最优。Prim算法就是典型的贪心算法，每次选择最小的边来增加生成树，直到连接所有顶点。
在实际应用中，最小生成树算法如Prim和Kruskal（另一种贪心算法）常用于诸如网络设计、资源分配、交通规划等问题，以最小化成本或最大化效率。理解并熟练掌握这些算法，对于解决实际生活中的复杂问题有着重要的价值。
