注：文章内容来源于网络，真实性有待确认，请自行甄别。
求最小生成树问题，急！！！用Kruskal算法就一棵最小生成树！
发表于：2024-10-24 00:00:00浏览：4次
问题描述：用 Krual算法就一棵最小生成树！
题见下图！
将所有的边按照其上所带的权从小到大排序。
1、从边长1开始：
边长1，
边长2，（边长2与边长1构不成回路）
边长3，（边长3与边长2、边长1构不成回路）
边长5，（边长4与边长3、边长2、边长1构成回路，去掉。选择边长5）
边长7，（边长6与边长5、边长3、边长2、边长1构成回路，去掉。选择边长7）
一共有6个定点，生成树中有6－1＝5条边，完成。所以最小生成树由边长1、2、3、5、7五条边构成。
2、从三条边长1开始，再加入边长为2的边。生成树不唯一。
栏目分类全部>