普里姆(Prim)算法另解  

Another Statement on Prim Calculation

作　　者：刘平原[1] 张霓[1] 

机构地区：[1]湖南,株洲职业技术学院,412000

出　　处：《科学中国人》2007年第7期125-126,共2页Scientific Chinese

摘　　要：在《数据结构》有关图的章节中,对最小生成树两大算法的解释都是基于MST性质来说明的。由于MST性质每次是选取原图集中值最小两栖边来构造最小生成树,这个过程较为复杂,现可以反其道而行之,采用“破圈法”——每次删除权值最大的边,来产生最小生成树,过程简洁、结果相同,同时可以证明其正确性,不失为一好算法。In the chapters on graphs of Data Structure, the statement to the two on the MST nature, Because each time according to the MST nature, the minimal amphibious minimal produce we delete the can prove its trees and the maximal margin correctness calculation ways of the minimal produce 1 margin is chosen from the original atlas process is quite complicated Now we can do it vise versa, We can use ＂the breaking circle way＂ of weight to form the minimal produce tress, which is simple and can achieve the same result and at

关 键 词：无向连通图 有向连通图 连通子 生成树 最小生成树 MST性质 最小两栖边 普里姆算法 破圈法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP311.12[自动化与计算机技术—计算机科学与技术]