如何做到连通的代价最小

作者：李晓明

来源：中小学教材教学, 2019, (11): 76-80.

DOI：10.19878/j.cnki.zxxjcjx.2019.11.021

<正>在本刊第九期我们讨论了如何判断一个图(或者网络)是否连通的问题。这一期我们换个角度,研究如何让把一些节点连通起来的代价最小。可以想象这些节点是一些城市,它们之间的直飞航线是边,代价则是在它们之间开辟直航的成本。如果有n个节点,两两之间都开辟直航线,我们当然可以在任何两个城市之间便捷地来往,但