admin 管理员组

文章数量: 1184232


2024年3月19日发(作者：ascll解码)

前言

从学习《数据结构》这门课程开始，我已发现了学习算法的乐趣，在学习这门课的过程

中也学到了许多计算机应用基础知识，对计算机的机体也有了一个初步的了解，又在课余时

间阅读了大量有关算法设计与分析的图书，在此基础上，利用贪心算法，编写了一个用prim

和kruskal算法求解最小生成树，也以此检验自己一学期所学成果，加深对算法设计与分析

这门课程的理解，由于所学知识有限，难免有些繁琐和不完善之处，下面向大家介绍此程序

的设计原理，方法，内容及设计的结果。

本程序是在windows 环境下利用Microsoft Visual C++ 6.0所编写的，主要利用

贪心算法的思想，以及数组，for语句的循环，if语句的嵌套，运用以上所学知识编

写出的prim和kruskal算法求解最小生成树，在输入其边的起始位置，种植位置以及

权值后，便可分别输出此网的prim和kruskal算法最小生成树的边的起始位置，终止

位置以及权值。

正文

2.1 设计方法和内容

一.软件环境：Microsoft Visual C++ 6.0

二.详细设计思想：

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就

是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他

能产生整体最优解或者是整体最优解的近似解。

贪心算法的基本思路如下：

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

（普里姆）算法思想

无向网的最小生成树问题

此算法的思想是基于点的贪心，力求从源点到下一个点的距离最短，以此来构建临接矩

阵，所以此算法的核心思想是求得源点到下一个点的最短距离，下面具体解释如何求此最短

距离：

在图中任取一个顶点k作为开始点，令集合U={k},集合w=V-U,其中v为图中所

第 1 页 共 13 页

有顶点的集合，然后找出：一个顶点在集合U中，另一个顶点在集合W中的所有边中，

权值最短的一条边，，并将该边顶点全部加入集合U中，并从W中删去这些顶点，然

后重新调整U中顶点到W中顶点的距离，使之保持最小，在重复此过程，直到W为空

集为止，求解过程如下：

第 2 页 共 13 页


本文标签： 算法 问题 顶点 设计 求解

版权声明：本文标题：普里姆和克鲁斯卡尔算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1710855343a576462.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。