论文部分内容阅读
【摘要】在实际应用中，我们常碰到实现最小连接的问题，这就归结到最小树问题.最小树问题在运筹学、图论、数据结构等课程都有涉及.解决最小树问题的算法有Kruskal算法和Prim算法等.Kruskal算法的思想是在不构成圈的前提下尽可能选权最小的边.其中考察边和已选的边集是否构成圈是影响算法复杂性的关键一步.本文先介绍实现无圈判断的标号方法，分析其本质需求，进而引入根树方法，并给出进一步改进的思路.本文从运筹学教学的角度阐述教学内容，有意识地引导学生进行深入思考，提升学生进行自主学习的意识和能力.
【关键词】最小树;Kruskal算法;并查集;根树
【基金项目】山东大学（威海）重点教改项目《科研反哺教学的研究与实践》：A201805;山东大学（威海）教研项目《经管类探索性数学实验案例教学研究》：B201816
在实际应用中，我们常碰到实现最小连接的问题，例如交通网、电力网、电话网、管道网等网络设计，这些应用问题简而言之，即如何用最小的成本将一些对象连接起来.若把这些需要连接的对象对应一个个点（称为顶点），若两个对象能够直接建立联系（比如架设电线），则在对应的两点之间连一条线（称为边），两者建立联系的代价（比如架设电线成本）则为对应边的权.这样实际问题就以赋权图（也称网络）的形式展现出来，实际需求也就变成在对应网络里找最小权的连通所有顶点的子图（称为连通支撑子图）.最小连接问题可以转化为最小树问题，该问题在大学的许多课程中都有涉及，如运筹学、图论、组合优化、数据结构等.最小树问题在运筹学课程中属于网络优化部分.用网络分析的语言可以如下叙述该问题：给定一个赋权网络，找一个最小权的连通支撑子图.我们知道在所有边权非负的情况下，一定有一个支撑树，达到总权值最小.所以找最小权的连通支撑子图就是找最小权的支撑树（简称最小树），最小连接问题就是最小树问题.从算法复杂性的角度而言，最小树问题是简单问题，有多项式时间算法.现实中很多问题可以转化为网络优化问题，对它们的求解常常要用到最小树算法.最小树算法因其理论和应用价值，教师对其算法进行研究以及对学生进行知识的传授都是非常有意义的工作.
在大部分课程内容中，求解最小树问题都是贪心算法，如Kruskal算法和Prim算法.这些贪心算法能在多项式时间内找到最小树.Kruskal算法的时间复杂度为O（mlog n），Prim算法的时间复杂度为O（n2），其中m表示网络中的边数，n表示网络的顶点数.很显然，在顶点数大、边数相对较小的网络（即稀疏网络）中，Kruskal算法更胜一筹.本文就从运筹学教学的角度，介绍Kruskal算法，重点讲述其无圈判断的实现方法，通过算例演示使学生能较容易地掌握知识内容，又通过目的导向，引导学生深入思考，进而激发学生的研究兴趣.
Kruskal算法是一種贪心算法，其思想很简单，就是在所选边不构成圈的前提下依次选择权值最小的边.设给定网络G=（V，E;W），其中E和V分别是图（即所给网络）的边集和点集，W是定义在边集上的权值函数.令m=|E|，n=|V|，下面算法中，用S存放依次选中的边，|S|≤n-1.算法结束时，若|S|=n-1，则G[S]为最小树;否则，G[S]为最小权支撑森林.
求最小树的Kruskal算法的步骤如下.
第1步，把G中的边按权由小到大排列为a1，a2，…，am，即w（a1）≤w（a2）≤…≤w（am）.令i：=0，j：=0，S：=Φ.
第2步，令j：=j 1.若j
【关键词】最小树;Kruskal算法;并查集;根树
【基金项目】山东大学（威海）重点教改项目《科研反哺教学的研究与实践》：A201805;山东大学（威海）教研项目《经管类探索性数学实验案例教学研究》：B201816
在实际应用中，我们常碰到实现最小连接的问题，例如交通网、电力网、电话网、管道网等网络设计，这些应用问题简而言之，即如何用最小的成本将一些对象连接起来.若把这些需要连接的对象对应一个个点（称为顶点），若两个对象能够直接建立联系（比如架设电线），则在对应的两点之间连一条线（称为边），两者建立联系的代价（比如架设电线成本）则为对应边的权.这样实际问题就以赋权图（也称网络）的形式展现出来，实际需求也就变成在对应网络里找最小权的连通所有顶点的子图（称为连通支撑子图）.最小连接问题可以转化为最小树问题，该问题在大学的许多课程中都有涉及，如运筹学、图论、组合优化、数据结构等.最小树问题在运筹学课程中属于网络优化部分.用网络分析的语言可以如下叙述该问题：给定一个赋权网络，找一个最小权的连通支撑子图.我们知道在所有边权非负的情况下，一定有一个支撑树，达到总权值最小.所以找最小权的连通支撑子图就是找最小权的支撑树（简称最小树），最小连接问题就是最小树问题.从算法复杂性的角度而言，最小树问题是简单问题，有多项式时间算法.现实中很多问题可以转化为网络优化问题，对它们的求解常常要用到最小树算法.最小树算法因其理论和应用价值，教师对其算法进行研究以及对学生进行知识的传授都是非常有意义的工作.
在大部分课程内容中，求解最小树问题都是贪心算法，如Kruskal算法和Prim算法.这些贪心算法能在多项式时间内找到最小树.Kruskal算法的时间复杂度为O（mlog n），Prim算法的时间复杂度为O（n2），其中m表示网络中的边数，n表示网络的顶点数.很显然，在顶点数大、边数相对较小的网络（即稀疏网络）中，Kruskal算法更胜一筹.本文就从运筹学教学的角度，介绍Kruskal算法，重点讲述其无圈判断的实现方法，通过算例演示使学生能较容易地掌握知识内容，又通过目的导向，引导学生深入思考，进而激发学生的研究兴趣.
Kruskal算法是一種贪心算法，其思想很简单，就是在所选边不构成圈的前提下依次选择权值最小的边.设给定网络G=（V，E;W），其中E和V分别是图（即所给网络）的边集和点集，W是定义在边集上的权值函数.令m=|E|，n=|V|，下面算法中，用S存放依次选中的边，|S|≤n-1.算法结束时，若|S|=n-1，则G[S]为最小树;否则，G[S]为最小权支撑森林.
求最小树的Kruskal算法的步骤如下.
第1步，把G中的边按权由小到大排列为a1，a2，…，am，即w（a1）≤w（a2）≤…≤w（am）.令i：=0，j：=0，S：=Φ.
第2步，令j：=j 1.若j