题目

数据结构最小生成树可以重复连接吗?
我这里不能传图片,那我就举个简单例子吧~
例如：有一个三角形,三个角为ABC
AB=1 AC=2 BC=2
先不论这个三角形是否成立,我要问的是,这个最小生成树是先连接AB,然后BC对吧?那问题来了,是否还要连接AC?因为AC=2 按照最小生成树的定义,要走最近的路径,那么不连接AC的话,从A到c的距离就从2变成AB+BC=1+2=3了,这不就与定义相违背了吗?我想问的最重要一点就是可以这种相互连接吗?

提问时间：2021-03-06

答案

你理解错了,首先树必须是连通图并且无环,最小生成树也是树的一个特例,那么它也应该符合树的定义,如果你把AC也连起来的话,就生成了一个环.另外一点,所谓的最小路径,是指树的全路径（简单的说,就是所有边的权值之和,假...