Matlab版prim Kruskal算法实现文档

Matlab版Prim Kruskal算法实现文档 一、Prim算法 Prim算法是图论中的一种常用算法，用于求解最小生成树问题。其基本思想是以局部最优化谋求全局的最优化。该算法的实现步骤如下： 1. 设G=(V,E)是一个无向连通网，令T=(U,TE)是G的最小生成树。T的初始状态为U={v0}，TE={}。 2. 在所有uU，v V-U的边中找一条代价最小的边（u,v）并入集合TE，同时v并入U，直至U=V为止。 该算法的关键是如何找到连接U和V-U的最短边来扩充生成树T。为解决这个问题，可以用下述方法构造候选最小边集： 对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边，取候选边最短边集为V-U中n-k个顶点所关联的n-k条最短边的集合。 为表示候选最短边集，需设置两个一维数组lowcost[n]和adjvex[n]，其中lowcost用于保存集合V-U中的各顶点与集合U中的顶点的最短边的权值，lowcost[v]=0表示顶点v已经加入最小生成树中；adjvex用于保存依附于该边在集合U中的顶点。 二、Kruskal算法 Kruskal算法是另一种常用的图论算法，用于求解最小生成树问题。其基本思想是将图分解成若干个连通分量，然后逐步合并这些连通分量，直至整个图成为一个连通图。 该算法的实现步骤如下： 1. 将图分解成若干个连通分量。 2. 将每个连通分量的顶点按照权值从小到大排序。 3. 从排序后的顶点中选择最小的边，作为生成树的第一条边。 4. 重复步骤3，直至整个图成为一个连通图。 三、Matlab实现 在Matlab中实现Prim算法和Kruskal算法可以使用邻接矩阵表示图，分别保存为文件Graph1.m和Graph2.m。然后，在主程序finallyprim中直接调用这些文件，并使用sprintf格式化字符串的方法，避免了编程的人每次根据输入图的顶点数手动对提示作修改。 四、实验步骤 实验步骤可以分为三个部分： I. 用Prim算法求最小生成树 i. 算法分析及需求分析 ii. 程序设计 II. 用Kruskal算法求最小生成树 i. 算法分析及需求分析 ii. 程序设计 III. 实验结果分析 i. 对比Prim算法和Kruskal算法的实现复杂度 ii. 评估算法效率 五、结论 Matlab版Prim Kruskal算法实现文档提供了一种使用Matlab实现Prim算法和Kruskal算法的方法，通过实验步骤，可以对比两种算法的实现复杂度和效率，并根据实际情况选择合适的算法。