最小生成树问题是一个经典的网络优化问题,目前已有高效的算法在多项式时间内对其进行求解,比如Prim算法与Kruskal算法。然而实际问题往往要求对生成树加上一定的限制,形成了一类带有约束的最小生成树问题。度约束最小生成树问题与直径限制最小生成树问题就是这类问题中的两个典型代表,并且在现实生活中具有广泛的应用,例如,通信网络,电路设计,管道铺设等方面。因此,对这两种问题求解算法的研究具有很好的现实意义。本文的主要工作概括如下:首先,针对度约束最小生成树问题,提出了一种新的快速算法。新的快速算法包括两个主要部分:第一部分描述如何构造一棵度约束树;第二部分针对度约束树的构造方式设计了一种改进策略。通过改进策略,获得了近似程度更高的结果。文中给出了算法的有效性证明及其复杂度分析。通过大量的数值实验表明新的快速算法性能良好。其次,针对直径限制的最小生成树问题,在序列编码的基础上设计了一种遗传算法。该算法采用了新的变异算子和局部搜索算子。新的变异算子有效的提高了种群的多样性;基于序列编码方式设计的局部搜索算子产生了适应度更好的个体序列。文中给出了局部搜索算子的有效性证明。大量的数值实验表明该算法是非常有效的。