如何做到连通的代价最小

• 作者: 李晓明
• 来源期刊: 中小学教材教学
• 年，卷（期）: 2019,（11）
• 所属期刊栏目: 算法园地
• 页码范围: 76-80
• 页数: 5页
• 语种: 中文

摘要

在本刊第九期我们讨论了如何判断一个图(或者网络)是否连通的问题.这一期我们换个角度,研究如何让把一些节点连通起来的代价最小.可以想象这些节点是一些城市,它们之间的直飞航线是边,代价则是在它们之间开辟直航的成本. 如果有n个节点,两两之间都开辟直航线,我们当然可以在任何两个城市之间便捷地来往,但一共要有n(n-1)/2条航线,显然成本会很高.现实中,人们总是有选择性地使有些城市之间可以直航,有些则需要通过转机实现通达.也就是说,我们要的是一个图,有些节点之间可以没有边,但任何两个节点之间都存在路径,即一个连通图.