摘要
在实际应用中,我们常碰到实现最小连接的问题,这就归结到最小树问题.最小树问题在运筹学、图论、数据结构等课程都有涉及.解决最小树问题的算法有Kruskal算法和Prim算法等.Kruskal算法的思想是在不构成圈的前提下尽可能选权最小的边.其中考察边和已选的边集是否构成圈是影响算法复杂性的关键一步.本文先介绍实现无圈判断的标号方法,分析其本质需求,进而引入根树方法,并给出进一步改进的思路.本文从运筹学教学的角度阐述教学内容,有意识地引导学生进行深入思考,提升学生进行自主学习的意识和能力.
基金
山东大学(威海)重点教改项目《科研反哺教学的研究与实践》:A201805
山东大学(威海)教研项目《经管类探索性数学实验案例教学研究》:B201816。
