求最小树的Kruskal算法中无圈判断的进一步思考  

作　　者：宋慧敏 孙薇[1] 吴建良[2] 

机构地区：[1]山东大学数学与统计学院,山东威海264209 [2]山东大学数学学院,山东济南251000

出　　处：《数学学习与研究》2021年第13期151-153,共3页

基　　金：山东大学(威海)重点教改项目《科研反哺教学的研究与实践》:A201805;山东大学(威海)教研项目《经管类探索性数学实验案例教学研究》:B201816。

摘　　要：在实际应用中,我们常碰到实现最小连接的问题,这就归结到最小树问题.最小树问题在运筹学、图论、数据结构等课程都有涉及.解决最小树问题的算法有Kruskal算法和Prim算法等.Kruskal算法的思想是在不构成圈的前提下尽可能选权最小的边.其中考察边和已选的边集是否构成圈是影响算法复杂性的关键一步.本文先介绍实现无圈判断的标号方法,分析其本质需求,进而引入根树方法,并给出进一步改进的思路.本文从运筹学教学的角度阐述教学内容,有意识地引导学生进行深入思考,提升学生进行自主学习的意识和能力.

关 键 词：最小树 KRUSKAL算法 并查集 根树 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]