Prim算法和Kruskal算法的Matlab实现

计算机仿真最终任务Prim算法和Kruskal算法的Matlab实现05605刘玉050697(30)连接问题的应用示例：如果你想建造一条连接两个城市的高速公路，如果城市之间的高速公路的成本是，试着设计一张路线图，使总成本最低。连接问题的数学模型是图论中的支持树，它在连接的加权图上寻找最小的权重。用Matlab实现Prim算法和Krusal算法(避圈法)分别寻找最小支持数。一、基本要求：(1)绘制程序流程图；(2)解释关键算法、变量和步骤；(3)用下图验证算法的正确性。也就是说，输入图形的信息，并输出相应图形的最小支持树及其权重值。(4)分析了两种算法的实现复杂度。二。扩展要求：(1)提供一种评估算法效率(复杂度)的方法，并用实例进行验证，并与分析得到的算法复杂度结果进行比较；(2)从减少内存消耗和计算时间的角度优化算法。三。实验步骤一、用Prim算法寻找最小生成树算法分析、需求分析和程序设计prim算法的基本思想是：设G=(V，e)是一个无向连通网络，T=(U，te)是G的最小生成树。T的初始状态是U=v0(v0V)TE=，然后重复以下操作：在所有uU中，在vV-U的边中，找到代价最小的一个(U，V)合并到集合TE中，而V合并到U中，直到u=v显然，Prim算法的基本思想是通过局部优化来寻求全局优化，它还涉及到节点的启动问题。这个程序的功能是从图中的任何节点找到最小生成树。实施计划分析：Prim算法的关键是如何找到连接U和V-U的最短边来扩展生成树T。假设当前T中有k个点(即T的顶点集U中有k个顶点)，那么所有满足uU、vV-U的边最多有k(n-k)条，所以从这样大的边集中选择最短边是不经济的。利用MST性质，候选最小边集可以通过以下方法构造：对应于V-U中的每个顶点，保留从顶点到U中每个顶点的最短边，并将候选边最短边集作为与V-U中的n-k个顶点相关联的n-k个最短边的集合。为了表示候选最短边集，需要设置两个一维数组LoCost N和adjvexn。 其中，LoCost用于保存集合V-U中每个顶点的权重和集合U中顶点的最短边，LoCost V=0表示顶点V已添加到最小生成树； Adjvex用于保存与集合u中的边相连的顶点。例如，下面的公式表明顶点vi和顶点vk之间的权重为w低成本I=w；adj vexI=k；程序流程图关键代码描述：1.以邻接矩阵的形式保存用于验证算法正确性的两个图，并分别保存为文件Graph1.m、Graph2.m(注意：矩阵的对角元素设置为零。)并直接在主程序中调用。2.当进入起点时，程序的读者应该被提示图形的顶点数，否则用户可能会输入超出范围的下标。采用的方法如下len=长度(graph _ neighbor)；%一个图中有多少个顶点k=sprintf(请输入您想要开始的点，请记住它必须在1和%d之间，len)；起点=输入(k)；%输入最小生成树生成起点通过使用sprintf格式化字符串，程序员每次都无法输入图形的顶点。手动修改提示。效果如下：在第一幅图像的算法验证期间，以下输出：将在工作空间中输出请输入您想要开始的点，请记住它必须在1和7之间在第二幅图像的算法验证期间，工作区中将显示以下输出：请输入您想要开始的点，请记住它必须在1和8之间3.为了在输出结果时使结果在工作空间中输出清晰，还使用了sprintf格式的字符串方法。代码如下s=0；对于ii=1:len-1K=sprintf(最小生成树的边%d:(%d，% d)，权重% d，ii，树(ii，1)，树(ii，2)，图_邻近(树(ii，1)，树(ii，2)；显示(k)；disp()；s=s图_邻接(树(ii，1)，树(ii，2)；目标最小生成树的总成本：)显示(s)；4.算法的核心部分描述如下：在len-1循环中，每个循环应完成以下三项任务1.找到最小的边(低成本数组的最小非零值是必需的，因为0表示该边已添加到最小生成树中)因为最小值是非零的，所以最小函数不能直接使用。我采取的方法是：k=低成本0；%k是一个逻辑数组，与lowcost的维数相同。对于每个位，%如果低成本(i)0，则设置I，然后k(i)=1%否则k(I)=0；该阵列稍后将用于二次寻址。cost_min=min(低成本(k)；%查找低成本中除0以外的最小值索引=查找(低成本=成本_分钟)；%在低成本中找到该最小值的下标，即找到相应的节点指数=指数(1)；%由于最小值可能有一个以上的下标，第一个下标在此处进行处理。低成本(指数)=0；%表示节点已加入最小生成树。该方法不仅充分利用了matlab的内置函数，而且避免了编写代码本身(循环判断低成本v是否为0)寻找非零最小值的麻烦，提高了代码执行效率。2.更新低成本和adjvex，即设置新添加到最小生成树的顶点作为索引。比较u-v中每个顶点v:的低成本(v)和(v，索引)边的权重值，如果(v，索引)边的权重值很小，则低成本(v)的值成为边的权重值，adjvex(v)的值等于索引对于j=1:len如果低成本(j)图_相邻(j，索引)；低成本(j)=graph _ neighbor(j，索引)；adj vex(j)=索引；目标目标3.保存边缘树(I，)=阿德维克斯(指数)，指数；二。结果如下寻找第一个图形的最小生成树；寻找第二个图形的最小生成树；二。用Krusal算法(避圈法)寻找最小生成树算法分析、需求分析和程序设计Kruskal算法的基本思想是将无向连通网络设置为G=(V，e)，使G的最小生成树为T=(U，te)，其初始状态为U=V，TE=，从而T中的每个顶点形成一个连通分量。然后，按照边的权重从小到大的顺序，依次检查边集合E中的每条边。如果被检查的边的两个顶点属于T的两个不同的连通分量，则该边被添加到TE，并且两个连通分量同时被连接成一个连通分量；如果被检查的边的两个节点属于同一个连接的组件，则省略该边以避免导致循环。如果T中连通分量的个数是1，则连通分量是g的最小生成树显然，Kruskal算法比prim算法实现起来更复杂。选择合适的存储结构来存储图形并使用合适的排序算法来提高程序执行效率是非常重要的。使用简单明了的方法来判断一条边的两个端点是否在一个相连的分支上是特别重要的。一般来说，Kruskal算法大多使用边集数组作为图的存储结构。然而，考虑到matlab不能像C语言那样动态方便地生成数组和释放内存，它仍然采用邻接矩阵的形式来保存图形。用于测试的两个图被保存为图11.m和图22.m(注意：邻接矩阵的对角元素被设置为100)，这便于在两侧和相对侧的顶点上操作。使用邻接矩阵容易引起的问题有：由于邻接矩阵是对称矩阵，例如graph _ neighbor(1，2)和graph _ neighbor(2，1)代表同一条边，当一条边被选入最小生成树时，它的两个节点应该分别更新。整个过程是基于顶点的。由于一条边对应两个节点，标签较小的顶点作为主要处理对象，用于寻址与该边对应的另一个节点。这种标准化的优点是程序过程的每一步都有自己的预测误差，这很容易找到。让我们介绍一个matlab内置的排序函数排序。这个函数非常强大，正是因为这个函数，我的程序简洁高效。Y，I=排序(A)；其中a是矩阵。y是从小到大对a中的列进行排序的结果，I是原始矩阵a中y中元素的行号。示例如下为了判断两点是否在同一个连通分支中，我的方法如下：声明一个数组标记来存储每个节点所在的连接分支的标签，初始值是每个节点的标签。当两个连接的组件连接时，它们的标记值被设置为一致程序流程图：关键代码描述：1.如何判断两点是否在同一个连通分支中(1)将图中每个顶点的标签值设置为它自己的标签对于j=1:lentag(j)=j；%关联标志被初始化，每个顶点的关联标志被设置为自身。结束；(2)当确定两个顶点不在同一个连通分支中时，将它们相应的边添加到最佳边集中超边界，并修改一个顶点及其连接分支的每个点的标记值，使其与另一个连接分支具有相同的标记值。如果(标记(另一个点)=标记(索引)%当两个点不属于一个连通集时，这两个点之间的边就是最小生成树的边超高(I，)=指数，另一点；%将其添加到最小生成树的边集中I=I 1；%下标加1%以下语句的功能是将两个连接的分支变成一个连接的分支，也就是说，标记值是相同的。j=1:len%基于索引的标记值。如果(tag(j)=tag(another point)(j =another point)%搜索标记数组，首先将与另一个点标记值相同的点的标记值更改为索引的标记值。标签(j)=标签(索引)；目标目标标记(另一个点)=标记(索引)；%将另一个点的标记值更改为索引的标记值目标目标注意：在上面的红色团队部分，其他点的标记值以及分支必须首先更改为标记(索引)，最后更改标记(另一点)的标记值。如果在另一个点之后的点的标记值首先被改变，则在另一个点之后的点的标记值不能被正确地更新。2.找到最小的边Y，I=排序(临时)；%从小到大对每列温度进行排序。数组Y存储临时排序结果，数组I存储临时对应结果的下标成本_分=分(Y(1，)；%查找权重最小的边索引=查找(Y(1，)=成本_分钟)；%找到与权重最低的边相对应的顶点指数=指数(1)；%一条边对应两个节点，不同边的权重可能相同。这里，为了便于处理，手动指定顺序，取具有最小标签的顶点进行处理。另一个点=1(1，指数)；%找到了对应于该边的另一个顶点%将对应于边的权重修改为最大值，以防止边在下一个循环中再次被选为最佳边。温度(指数，另一点)=100；温度(另一点，指数)=100；3.显示组件使用的代码参见prim算法。二。结果如下A.第一个图的最小生成树B.第二张图片的最小生成树四.扩展功能的完成(1)提供一种评估算法效率(复杂度)的方法，并用实例进行验证，并与分析得到的算法复杂度结果进行比较；(1)理论分析假设图中的顶点数为N，那么Prim算法需要执行n-1个外环来寻找最小边，每个外环需要执行N个内环来更新低成本和adj凸数组。因此，Prim算法的时间复杂度为O(n2)，与网络中的边数无关，因此适合于寻找稠密网络的最小生成树。因为Kruskal算法对图中的边进行顺序运算，所以Kruskal算法的时间复杂度是O(elog2e)，其中E是无向连通网络中的边数。与Prim算法相比，Kruskal算法适用于寻找稀疏网络的最小生成树。(2)程序验证1.随机生成300300的对称密集矩阵，以观察Kruskal和Prim算法的运行时间。(添加tic和TIC，分别在最终的prim和最终的kruskal脚本文件中